Inspired by a thread over at the D forum, I'm wondering if there is a way to get stack allocated variable length arrays in Nimrod, or the rationale against them if there is not.
AFAIK, Nimrod's arrays have sizes given at compile time, while Nimrod's sequences can have run time determined length and are resizable. I'm asking about an intermediate thing, like C99's VLA or Ada's stack allocated arrays, who's size is determined at runtime but which is not resizable and so can potentially avoid the GC.
The main practical problem with stack-allocated arrays is that they can result in stack overflow unless their size is bounded. But if their size is bounded, you can generally just use a fixed-size array of the maximum length you can tolerate instead.
If you truly do need variable-length arrays, then you have the following options:
Almost everything I work on these days benefits from a GC, but I don't believe that even the most efficient GC is always a win against stack allocation. I also don't believe that escape analysis will always allow you to elide heap access better than explicitly using stack allocated collections. I agree that if it can, it would be best to leave them out. Having VLAs would better than another !@#$ing pragma for stack allocation :-).
Nimrod is not D, or C++, or Ada, but it should be competing with all of them. I'm glad to read that at least there's openness to VLAs at some point in the future.
Here's a basic implementation of VLAs (caution, there are no checks to make sure that you don't use them past their lifetime):
include system/ansi_c
proc alloca(n: int): pointer {.importc, header: "<alloca.h>".}
type
UncheckedArray{.unchecked.}[T] =
array[1, T]
VarLengthArray*[T] =
ptr object
size: int
data: UncheckedArray[T]
proc `[]`*[T](a: VarLengthArray[T], i: int): T =
assert i >= 0 and i < a.size
result = a.data[i]
proc `[]=`*[T](a: VarLengthArray[T], i: int, x: T) =
assert i >= 0 and i < a.size
a.data[i] = x
proc len*[T](a: VarLengthArray[T]): int =
a.size
template newVLA*(T: typedesc, n: int): expr =
let bytes = sizeof(int) + sizeof(T)*n
var vla = cast[VarLengthArray[T]](alloca(bytes))
c_memset(vla, 0, bytes)
vla.size = n
vla
proc toSeq*[T](a: VarLengthArray[T]): seq[T] =
result = newSeq[T](len(a))
for i in 0..len(a)-1:
result[i] = a[i]
With a bit more effort, one can probably also mirror the seq layout so that a VLA can be passed as an openarray parameter.
That said:
brianrogoff: I also don't believe that escape analysis will always allow you to elide heap access better than explicitly using stack allocated collections.
That case is actually fairly simple to check for. When a seq object is allocated locally, never assigned to another variable, never returned, never resized, and only passed as an openarray to other procedures, that's completely equivalent to having a local declaration of a variable length array.
I'll also still say that this is a case of premature optimization and even if you need to optimize it, it may not be the best way to optimize your code (especially if you're risking a stack overflow).
Thanks for the code Jehan, nice example of Nimrod extensibility!
How would I take your suggested next step, namely openarray compatibility for VarLengthArray? If you could point me in the direction of code to look at I'll give it a try; I didn't see anything in a quick pass through the docs.
You can find the layout of the seq header in lib/system.nim as TGenericSeq and PGenericSeq (various stuff that uses these types is in lib/system/sysstr.nim). PGenericSeq corresponds to the VarLengthArray[T] type that I defined above, it just has a different header and does not explicitly define a data attribute, though seq data is laid out similarly.
The len attribute in TGenericSeq is the same as size above; the reserved attribute contains the allocated space for data in its low-order bits (one per slot, not one per byte) and a flag in the most significant bit that determines whether sequence assignment should be shallow. You can probably just set reserved to the same size as len (same as newSeq in lib/system/gc.nim does, except that you'll be using alloca to get memory).
This should correctly mimic the layout of standard sequences. You cannot fully use the resulting type as a general sequence, since resizing or copying is likely to mess up the stack, the heap, or both. However, you can use it as an openarray, best via a template + cast, e.g.
# Untested code
template asArray[T](a: VarLengthArray[T]): openarray[T] =
cast[seq[type(a[0])]](a)