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: -------