On Fri, 09 Sep 2011 14:53:23 +0200, dsimcha <[email protected]> wrote:
Thanks for the review. Detailed comments below.
On 9/9/2011 2:38 AM, Martin Nowak wrote:
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
I am surprised there is any trailing whitespace. I use CodeBlocks which
usually gets rid of it. I think I disabled this because it was showing
up in diffs when I edited Phobos modules.
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();.
But RAII makes things simple and relatively safe. What would you
suggest as the alternative?
I don't suggest to drop RAII at all. It is totally needed and the right
thing
for every subprocedural use-case. But the RegionAllocator should have a
function
freeMe that will reset the stack to it's level and assert/enforce (depends
on price)
no stall RegionAllocators are alive. Afterwards the RegionAllocator would
be in an uninitialized
state again.
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.
Unfortunately, this leads to a fundamental disagreement that I have with
a large portion of this review. I want RegionAllocator to be high-level
enough to be easy to use right out of the box. You seem to be asking
for something lower level but more composable. The problem is that
low-level but composable often makes simple things complicated and
messy. Furthermore, if the allocator knows the type being allocated, it
can sometimes take that into account and do "special" things like GC
scanning, etc. Similarly, array() takes advantage of knowing the
implementation details of the allocator.
I hoped for a part of the leverage the range concept provides.
Needed information concerning behavior should be deducible from the
allocator traits/enums.
What allocation algorithms are not type agnostic?
OTOH I could think of auto free pools et.al., which would call finalizer or
allocators that return ref counted wrappers.
Still these should be composed/mixin behavior and not required for the
allocator
interface.
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.
This is also necessary to allow proper freeing of huge allocations
(bigger than a segment size). I really don't see much downside given
that the overhead is small. Furthermore, having tons of
RegionAllocators local to one function would get really messy really
fast.
{
auto al = newRegionAllocator();
al.newArray!(double[])(20_000);
}
vs.
alloc.newArray!(double[])(20_000);
alloc.freeLast();
This goes a little against your point that RAII is simple.
You can easily deallocate the wrong thing. It is tempting to call
this from a parent function and suddenly depend on child implementation.
The issue is that freeLast is relative to the stack while RegionAllocator
provides nice absolute freeing.
You also can't hardly use alloc.free(ary) because you might
not be able to obtain the correct pointer (sliced arrays, class interface).
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.
Creating a brand-new stack is expensive because it heap allocates and
incurs synchronization overhead. The stack is designed to make creating
a new RegionAllocator cheap (i.e. no synchronization overhead or heap
allocation in most cases). RegionAllocator mainly provides RAII freeing.
I think RegionAllocator would better be named
ScopedRegion/ScopedFree/AutoReleasePool.
Please have a look at https://gist.github.com/1204402 it uses a simple
save/restore
pattern and a scoped restore. I think this looses only little safety but
is simpler
to understand.
6. Allocating more bytes than the segment size could be an error.
This would reduce the complexity for handling big objects.
I really like the transparent "just works" design for big objects.
Again, this goes back to the high-level vs. simple point. You seem to
be calling for the Unix way (everything is simple, stupid and
composable, implementation simplicity is most important). I'd much
rather make the implementation more complicated but the interface
simpler/less error prone.
Yes you are right. Big objects should definitely be handled.
I totally share your usability concerns. But I'm also concerned that
not looking thoroughly at the building blocks we won't get a good ecosystem
(or any second allocator at all).
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).
This might not be a bad idea, especially if I make the malloc/free
allocator the default so most users don't need to think about this.
Yes LibcAllocator or GCAllocator should be default.
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.
Hmm, I guess my alignedMalloc/alignedFree could be made into
LibcAllocator.
Alignment should be a public enum and part of the allocator interface.
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.
I don't understand. If they have to set a flag to get it added, then I
fail to see how adding it manually is any more difficult.
If I wrote an allocator that separates scanned/not-scanned memory to avoid
locking the GC when addRanging the user had no way to do this.
Though similar as you did, having an optional fixed scan/no-scan setting
for
allocators seems to be enough.
10. Using a free list for the segments should be left to a
FreeListAllocator (see 7).
Maybe in the long run once we have a FreeListAllocator, but IMHO this is
an implementation detail that can be changed later. I definitely don't
want to expose the free list stuff in the API because I'd rather not
complicate the interface with these details.
I totally don't want you to expose this.
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.
Hmm, I really like the idea of the stack memory getting freed
automatically and deterministically by ref counting.
Fine for me, but please provide a clean()/deinitialize() method then.
12. Ideally RegionAllocator would be AlignedAllocator!(16,
RegionAllocator!(FreeListAllocator!(LibcAllocator))).
The alignment is taken care of internally to RegionAllocator in a way
that a generic AlignedAllocator wouldn't be able to handle as
efficiently. FreeListAllocator and the whole free list concept is an
implementation detail and shouldn't appear in the API at all. I think
you may have a good point about LibcAllocator being a template
parameter, though.
I'm really more into thinking of the whole allocator package.
And you are correct with that building a complete modular system
is not out biggest concern now.
In the long run I'd like to see something like this.
struct RegionAllocator(SegmentAllocator=LibCAllocator) {
mixin(newArraySupport!(rawAlloc));
mixin(newTSupport!(rawAlloc));
void* rawAlloc(size_t n) {
_allocator.alloc(n);
}
RegionAllocatorImpl!(AlignPolicy, SegementAllocator);
}
Smaller issues:
- In the constructor of RegionAllocatorStack you should enforce that
segmentSize is bigger than alignBytes instead of only catching 0.
Good point. Will fix.
- At a quick glance in alignedMalloc you only need to store an offset
smaller than alignBytes instead of a pointer (ubyte will suffice).
Good catch. I'll do this if I make a generic LibcAllocator with these
functions, but otherwise the savings are so small (a few bytes on the
multi-megabyte allocations that RegionAllocator does) that I'd rather
not change it just due to inertia and risk aversion.
- regionallocator.d(594): idempotent assertion
while (nLargeObjects > 0 && bookkeepIndex > regionIndex) {
assert(bookkeepIndex > regionIndex);
freeLast();
}
Another good catch. This is just cruft from when the second check in
the while statement wasn't there.
- regionallocator.d(939): something is missing/too much
static size_t alignBytes(size_t nBytes) {
return .alignBytes;
}
alignBytes() is a function that is part of the allocator interface.
.alignBytes is an enum that needs to be visible at the module level for
alignedMalloc/alignedFree.
You probably don't want a parameter then.
- Props for doing array, this might come in handy.
In arrayStackImpl the static if for choosing fast array copy
should be (hasLength!R || isSomeString!R).
I simply have to point out, that you used an alloc(0) => freeLast pattern
to save/restore yourself.
If that would be made absolute it could be an enrichment to the stack
interface.
SaveCount save();
void restoreCount(SaveCount);
martin
