So I have used RegionAllocator.
First of all, thanks for getting things like these into the std library.
I didn't even know segmented stacks before and they were the perfect
solution to my use case.
Since first reading about this I've used a TLS Appender which I cleared
occasionally.
Performance is top. For me it's on par with statically allocating a
huge chunk and draw from this with memset initalization.
The Use Case:
I have implemented a wavelet rasterizer. It uses a sparse quadtree.
Bezier curves are recursively sliced into each child quadrant.
I lazily allocate 4 child nodes when recursing into a quadrant.
After all bezier curves are added the coverage for pixels can be
calculated and used for blitting.
Afterward the whole tree is disposed.
Details for this pretty neat and simple rasterizer at
http://josiahmanson.com/research/wavelet_rasterization/.
Criticism of regionallocator:
1. Please M-x delete-trailing-whitespace
2. Using RAII for the allocator also pushes RAII onto the user.
To avoid having to pass the allocator around I had to add another
static
variable holding the allocator.
This doesn't work well, because there is no explicit freeAll function
for the allocator.
Furthermore assigning a newRegionAllocator to an initialized
allocator is not possible as it breaks the LIFO order. So I had
to resort to sAlloc = RegionAllocator.init; sAlloc =
newRegionAllocator();.
3. All initialization (newArray, newUnitializedArray, newT) should
not be part of an allocator interface.
We should instead create a templated Initializer or free functions
that will do this using one of the new allocators providing void*
memory.
4. I don't appreciate all the bookkeeping involved with every
allocation, mainly just to provide freeLast.
RegionAllocator should be such lightweight that you can use one
for each allocation that you want individual freeing for.
5. Separating the stack from the allocator creates mental/code bloat.
It suggest the wrong association with allocating from the
allocator while in reality your allocating off the stack using
kind of a cookie.
I had a simpler interface in mind https://gist.github.com/1204402.
Can you elaborate a little why/what additional complexity is needed.
6. Allocating more bytes than the segment size could be an error.
This would reduce the complexity for handling big objects.
Allocator interface:
7. Instead of using malloc/free you should use an malloc/free version of
the allocator interface.
This way RegionAllocator can be used for other memory (e.g. shared
memory).
8. The allocator interface should provide means to do aligned allocations.
As this would arguably complicate implementations alternatively
requiring
all allocators to return 16-Byte aligned memory seems reasonable.
Still another possibility is having an enum flag for alignment and
provide an
allocator wrapper that does aligned allocations.
9. The allocator interface should have a flag to advice GC range adding.
Could be:
alloc(size_t nbytes, GCScan scan = GCScan.no)
RegionAllocator could deduce it's scan flag from the first use and
enforce it never changes afterwards. I'm not to sure about this,
but requiring the user to add memory to the GC seems error prone and
reduce the design space for allocators.
10. Using a free list for the segments should be left to a
FreeListAllocator (see 7).
11. I'm really much in favor of using classes (final) for such long living
objects (the stack).
This allow simpler lazy static initialization and has scope new for
stack variables.
But most important you don't need to have unitialized structs. Which
at the
end of the day use a ref counted impl (see 2). OTOH classes are more
complicated
for templated decoration.
12. Ideally RegionAllocator would be AlignedAllocator!(16,
RegionAllocator!(FreeListAllocator!(LibcAllocator))).
Smaller issues:
- In the constructor of RegionAllocatorStack you should enforce that
segmentSize is bigger than alignBytes instead of only catching 0.
- At a quick glance in alignedMalloc you only need to store an offset
smaller than alignBytes instead of a pointer (ubyte will suffice).
- regionallocator.d(594): idempotent assertion
while (nLargeObjects > 0 && bookkeepIndex > regionIndex) {
assert(bookkeepIndex > regionIndex);
freeLast();
}
- regionallocator.d(939): something is missing/too much
static size_t alignBytes(size_t nBytes) {
return .alignBytes;
}
