TempAlloc: Request for Review For Inclusion in core.memory

dsimcha dsimcha at yahoo.com
Tue Apr 19 06:34:43 PDT 2011


My TempAlloc module's been ready for review for a while, but 
std.net.isemail and std.parallelism were ahead of it in the review 
queue.  Now that the reviews for both are done (I doubt running a review 
concurrently with a vote is problematic), I want to put this next in 
line.  I'd like to get it in druntime soon because Don wants to use it 
in BigInt and I also have some things I want to contribute to Phobos 
that TempAlloc would be useful for.

TempAlloc is a segmented stack for allocating and freeing temporary 
buffers efficiently.  It works by allocating memory in large chunks 
(currently 4 MB, but this number may be revised) at a time from the C 
heap, and parceling them out with the standard last in first out stack 
restriction.  The proposal also contains a few small helper functions 
that I think would be useful, but these can be made private or removed 
if people don't like them.

TempAlloc has the following advantages compared to allocation on the
call stack:

1. Pointers to memory allocated on the TempAlloc stack are still
valid when the function they were allocated from returns.
Functions can be written to create and return data structures on the
TempAlloc stack.

2. Since it is a segmented stack, large allocations can be performed 
with no danger of stack overflow errors.

It has the following advantages compared to heap allocation:

1. Both allocation and deallocation are extremely fast. Most allocations
consist of verifying enough space is available, incrementing a pointer 
and a performing a few cheap bookkeeping operations. Most deallocations
consist decrementing a pointer and performing a few cheap bookkeeping
operations.

2. The segmented stack is thread-local, so synchronization is only 
needed when a segment needs to be allocated or freed.

3. Fragmentation is not an issue when allocating memory on the
TempAlloc stack, though it can be an issue when trying to allocate
a new segment.

Code:

https://github.com/dsimcha/TempAlloc/blob/master/tempalloc.d

Docs:

http://cis.jhu.edu/~dsimcha/d/phobos/core_tempalloc.html


More information about the Digitalmars-d mailing list