http://d.puremagic.com/issues/show_bug.cgi?id=5348
Summary: Variable Length Arrays
Product: D
Version: D2
Platform: Other
OS/Version: Windows
Status: NEW
Severity: enhancement
Priority: P2
Component: DMD
AssignedTo: nob...@puremagic.com
ReportedBy: bearophile_h...@eml.cc
--- Comment #0 from bearophile_h...@eml.cc 2010-12-13 01:31:41 PST ---
This is an enhancement request for a new feature. It's a purely additive change
(fully backwards compatible with D2), so it may wait for later stages of D2
development, or even for D3.
I suggest to add the Variable Length Arrays (VLA) of C99 to D, using the same
syntax used in C99.
How D VLAs are represented on the stack: they are represented with an immutable
size_t length field followed by a (possibly aligned) contiguous block of data
(the pointer to the data is not necessary because the data is in-place). The
length field is necessary because the contents of the variable used to define
the array length may later change. Multi dimensional VLAs too are accepted.
When a VLA array is allocated the D compiler tests that there is enough free
stack left, and otherwise throws a runtime exception/error (like stack
overflow).
As in C99 "VLAarray.sizeof" is not a compile time constant, it returns the
length field * item.sizeof.
How VLAs are returned: they may be returned by value (creating a new VLA in the
function where the return value is received), or by reference as normal dynamic
array (by automatic copy on the heap). Both solutions have advantages and
disadvantages. The return by dynamic array is simpler for the programmer
because it changes less things in the language and it requires no syntax
changes.
Currently (DMD 2.050) this code:
void foo(int len) {
int[len] arr;
}
void main() {
foo(1);
}
DMD shows four times the same error:
test.d(2): Error: Integer constant expression expected instead of len
test.d(2): Error: Integer constant expression expected instead of cast(uint)len
test.d(2): Error: Integer constant expression expected instead of cast(uint)len
test.d(2): Error: Integer constant expression expected instead of cast(uint)len
Some of the disadvantages of this idea are:
- It adds some complexity to both the language and the compiler. The programmer
probably has to remember that there is another kind of array in D.
- It may encourage more usage of the stack, but the stack space is limited
compared to the heap space, so it may lead to more stack overflows. But see
below for an alternative view on this.
- Unlike C99, D already has dynamic arrays that cover part of the needs of
dynamic length arrays.
- It introduces a special case in the sizeof.
- Like fixed-sized arrays, the VLAs are managed by value, so a not careful
usage of them may lead to reduced performance caused by long array copies.
- D already allows to use alloca() for variable length stack allocation (unlike
C where alloca() is a common but non-standard function). alloca() usage is
probably uncommon in D code.
- I may have missed or underestimated some disadvantages of VLAs in D, in this
case please add a comment below.
Despite such disadvantages I think that the advantages outweigh them:
- VLAs lead more elegant and readable code.
- Both its syntax (and part of its semantics) is present in C99 already, and
it's a natural syntax, so programmers probably will have no significant
troubles in using them.
- VLAs cover most usage cases of alloca(), and the introduction of VLAs don't
removes the alloca() from Phobos, so this is a backward compatible change.
- It is safer than alloca() because its syntax is more clean than alloca().
- Compared to alloca() it leads to safer code because a VLA is a true array, so
the D compiler is able to enforce array bounds in non-release mode. This is
possible with alloca() too, taking a slice of the return value of alloca(), but
it requires explicit code, while in a VLA there is no need of this extra code.
- VLA require less code that may contain bugs. This is an important difference
for D, that's a language designed to be quite less bug-prone than C. There is
no need of pointer usage, cast(), sizeof, memset() (or assignment to .init),
slicing the stack pointer [], and the manual management of the situation when
alloca() returns a null. This is code that shows the difference, first using
alloca():
import core.stdc.stdlib: alloca;
import std.stdio: writeln;
import std.conv: to;
struct Foo {
int x = 10;
string toString() { return to!string(x); }
~this() { /* something here */ }
}
void bar(int len) {
Foo* ptr = cast(Foo*)alloca(len * Foo.sizeof);
if (ptr == null)
throw new Exception("alloca failed");
Foo[] arr = ptr[0 .. len];
foreach (ref item; arr)
item = Foo.init;
// some code here
writeln(arr);
foreach (ref item; arr)
item.__dtor();
}
void main() {
bar(20);
}
And then equivalent code using VLAs:
void bar(int len) {
Foo[len] arr;
// some code here
writeln(arr);
}
As you see the D compiler is aware that 'arr' is an array, to it calls the
destructors of Foo when the scope of 'arr' ends. If you use alloca() I think
this needs to be done manually.
If the VLA 'arr' array is 2D like this, then the code using alloca() gets more
complex:
Foo[len][len*2] arr;
The semantics of VLA is defined better and more easy to remember, because it's
the same as every other variable. The memory of the VLA is deallocated when the
variable scope ends. With alloca() the situation is different and less clear,
see bug 3822 . Maybe the alloca() used by DMD frees memory as soon as the
current scope is left, instead of deferring all deallocation until function
exit. See:
http://compilers.iecc.com/comparch/article/91-12-079
Compared to dynamic arrays, the allocation of a VLA may be (and often are) more
efficient, especially until D doesn't gain an advanced generational GC that has
an "Eden" (that allows allocation of short lived objects in a stack-like memory
area).
I have seen several times people ask for, or just obliviously use (not knowing
it doesn't work, DMD 2.050 doesn't refuse it), a syntax like this in D2:
scope arr = new int[100];
The VLAs replace such need with a more semantically defined situation (because
VLAs are more like fixed-sized arrays. While scoped dynamic arrays share some
of the faults of scoped object allocation that has being deprecated in D2).
Despite D has a GC, in a system language stack is an important resource,
because it decreases the work of the GC reducing the garbage to clean, makes
deallocation (and destructor calling) more deterministic (RAII), and often
increases performance. So it's positive to offer something better that replaces
the usage of alloca() and allows safer stack allocations. In some situations
stack allocation leads to clean forms of code too.
While encouraging too much the usage of the stack may lead to more frequent
stack overflows, the usage of VLA may even reduce the stack space needed. If
VLA are not available often alloca() is not used anyway because its usage is
not very natural and it's not clean. So the programmer often allocates on the
stack a fixed-sized array that's "large enough" for most cases. If such
function is called some times in some recursive way and such large enough
arrays build on each other, the total stack memory used may be higher than
using VLAs that allow to use only the minimum needed memory for each function
call. Reducing stack size often increases the performance too, because the less
stack memory is used, the less CPU cache misses there are (I have seen that
reducing the length of stack allocated arrays increases performance. Also
because DMD initializes arrays, so the shorter they are the less items to
initialize there are).
I have implemented an efficient function that computes the Levenshtein distance
between two strings, that need one or two temporary arrays to store the dynamic
programming table. The arrays are allocated on the stack if they are small (it
means small input strings), and on the heap if they are larger. A program calls
this Levenshtein distance function millions of times because it's needed to
build a particular tree that uses distances among keys to allow certain very
efficient queries over the key space. I have seen that in this program using
alloca() speeds up the code significantly over both dynamic allocation of
arrays and initialization of a fixed-sized array of a "large enough" array for
the small string case. Even defining the stack allocated array with "=void" is
not as fast as using alloca) in this situation.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
