AAs [was Re: bigfloat]

dsimcha dsimcha at yahoo.com
Wed Apr 8 19:00:43 PDT 2009


== Quote from bearophile (bearophileHUGS at lycos.com)'s article
> Andrei Alexandrescu:
> dsimcha:
> >Also, does anyone besides me have a use for an AA implementation that is
designed to be used with a second stack-based allocator (TempAlloc/SuperStack as
discussed here previously)?<
> The default AA has to be flexible, even if it's not always top performance. Your
implementation may be useful in a std lib, and not as built-in.

Of course.  I had not meant to suggest that this be the standard implementation.
It's a performance hack, but a very useful one IMHO given how often an algorithm
needs a really fast AA implementation that does not escape the function's scope.

> From the code comments:
> >Allocate a StackHash with an array size of nums.length / 2. This is the size of
the array used internally, and is fixed.<
> Do you use the alloca() function for this?

No.  It wouldn't work well w/ alloca(), see stack overflows, and the fact that
alloca-allocated memory can't escape a function scope, meaning that if the array
needed to allocate more memory on a call to opIndexAssign(), there would be no way
to do so in the caller's stack frame.  It uses TempAlloc, which was an idea
proposed by Andrei under the name SuperStack, and later implemented by me.

TempAlloc basically grabs big chunks of memory from the GC, and manages them in
last in, first out order like a stack.  Also, like a stack, it is thread local,
and therefore the only time there is possibility for contention is when a new
chunk needs to be allocated.  On the other hand, if you use too much memory, it
allocates another chunk from the heap instead of overflowing and crashing your
program.  Freeing memory is explicit, though with mixin(newFrame) you can tell
TempAlloc to free all TempAlloc memory allocated after that point at the end of
the scope.




More information about the Digitalmars-d mailing list