Formal Review of region allocator begins

[Jonathan M Davis]

Okay. Onto the next item in the review queue. I'm going to be the review
manager this time around, and we're going to be reviewing dsimcha's region
allocator. The review starts now and will end on 2011-09-21 at midnight in UTC
(so about 2 weeks from now, when the 21st begins). Assuming that we're ready
to vote at that point, I'll start a thread for voting for inclusion in Phobos,
and the vote will last a week. If it's not ready to be voted on for some
reason (such as dsimcha needing to go back and make a bunch of changes that
are going to need to be reviewed), then voting will be postponed and it'll be
put back in the review queue once it's ready for review again.

Docs:

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

Code:

https://github.com/dsimcha/TempAlloc

Description (from docs):

RegionAllocator is a memory allocator based on segmented stacks. A
segmented stack is similar to a regular stack in that memory is
allocated and freed in last in, first out order. When memory is
requested from a segmented stack, it first checks whether enough space
is available in the current segment, and if so increments the stack
pointer and returns. If not, a new segment is allocated. When memory is
freed, the stack pointer is decremented. If the last segment is no
longer in use, it may be returned to where it was allocated from or
retained for future use.


Some additional issues that dsimcha wants to mention for the review:

1. This is both a proposal for RegionAllocator and a proposal for a more
general allocator API in Phobos. The allocator API will be a structural
interface that includes the intersection of gcallocator and regionallocator
functionality. I don't have a more precise definition yet. Hopefully the
review process will hammer out whatever ambiguities remain.

2. Should we put this stuff in a std.allocators package, in a single
std.allocators module, or something else?

3. We definitely want a reap (combination region and heap) eventually, though
I don't have one yet. I want RegionAllocator to be reviewed for anything that
would make it unnecessarily hard to write other allocators on top of it, most
importantly reaps but also free lists, etc.


This is the first code to be reviewed which implements Andrei's proposed
allocator API, and several projects (including the GSoC projects) rely on it,
so it is critical that this code get a thorough review. It will have a large
impact on D for years to come. So, review away!

- Jonathan M Davis

[Vladimir Panteleev]

On Tue, 06 Sep 2011 22:53:31 +0300, Jonathan M Davis <jmdavisProg at gmx.com>

Post by Jonathan M Davis
So, review away!

When the allocated region is not scanned by the GC (which is the default
for the default thread-local RegionAllocatorStack instance), I think it
would be appropriate for the newArray and uninitializedArray methods to
statically check if the type doesn't have any pointers.

[Timon Gehr]

Post by Vladimir Panteleev
On Tue, 06 Sep 2011 22:53:31 +0300, Jonathan M Davis

Post by Jonathan M Davis
So, review away!

When the allocated region is not scanned by the GC (which is the default
for the default thread-local RegionAllocatorStack instance), I think it
would be appropriate for the newArray and uninitializedArray methods to
statically check if the type doesn't have any pointers.

That is way too restrictive. Pointers do not always point to GC
allocated memory.

[Vladimir Panteleev]

Post by Timon Gehr

Post by Vladimir Panteleev
On Tue, 06 Sep 2011 22:53:31 +0300, Jonathan M Davis

Post by Jonathan M Davis
So, review away!

When the allocated region is not scanned by the GC (which is the default
for the default thread-local RegionAllocatorStack instance), I think it
would be appropriate for the newArray and uninitializedArray methods to
statically check if the type doesn't have any pointers.

That is way too restrictive. Pointers do not always point to GC
allocated memory.

I'm not saying there shouldn't be a way to override it. Overriding this
check would be the user's way to say "Yes, I know what I'm doing, I'm not
going to put the only references to live heap objects into this region
allocator".

I'd be happy with either this, or "big red warnings" saying that careless
use of this module can lead to hard-to-track memory corruption bugs :)

[dsimcha]

Post by Vladimir Panteleev
I'd be happy with either this, or "big red warnings" saying that
careless use of this module can lead to hard-to-track memory corruption
bugs :)

The big red warning in the docs is do-able and probably a good idea.
However, I really don't want to force any casts or anything like that
because such restrictiveness would get in the way instead of helping way
too often. As mentioned previously, not all pointers are to
GC-allocated memory. Furthermore, having pointers from unscanned memory
to GC-allocated memory is safe as long as that's not the **only**
pointer you have to the object. This is important, for example, when
making a temporary copy of an array of pointers to GC-allocated objects
to sort it: The original is still keeping the objects alive.

[dsimcha]

BTW, forgot to mention it. This proposal also includes a gcallocator
allocator struct that just wraps stuff from core.memory and std.array.
The docs are at
http://cis.jhu.edu/~dsimcha/d/phobos/std_gcallocator.html and the source
is at the same place as for regionallocator.

[Alix Pexton]

1. The last part of the module description [lines 57-59 in the source]
is a little hard to follow.

2. The description of out of memory behaviour in the ddoc for
RegionAllocatorException [100-104] should be just one sentence, not two.

3. There is too much whitespace between the values of the GCScan enum ^^

4. I think there is a comma missing (or something) from the first XREF
in the description of RegionAllocatorStack [131]

5. In the example for RegionAllocatorStack [152-174], I suspect it might
be easier to follow if there were a comment highlighting that fun1
passes stack to fun2.

NB I also keep getting muddled between RegionAllocator and
RegionAllocatorStack, as if my brain only differentiates identifiers by
the first 15 characters, probably more an issue with me than the module ^^

6. ddoc for RegionAllocatorStack's constructor [84-186] should mention
that it throws when passed 0 as the segment size.

7. docs for scanThreadLocalStack is vague about exception type (source
on git hub appears to be correct, so I'll assume they are just out of
sync, from here on I'll review the ddoc straight from the source).

8. examples for struct RegionAllocator [448-508] Is it possible to split
this into 2 or 3 sub examples, to make it more clear that foo and bar
are interdependent, but independent from the rest?

9. Note about large allocations [512-520] the last sentence about time
considerations is a little clumsy, don't be afraid to to use big-O
notation to make it clear what effects what.

10. resize [825...] Not sure if I like it returning a bool to denote
success/failure, I think I'd prefer it to throw if the resize fails.

11. uninitializedArray [909...] ddoc seems a bit misleading, should
perhaps be something like...
"Same as newArray, except skips initialization of elements for
occasions when greater performance is required."

12. alignBytes [939...] just has me stumped, the introduction says that
16 byte alignment is guaranteed, so shouldn't this always return 16? I
tried to follow the breadcrumbs through the source, but couldn't find
where the value it returns is defined, only places where it is used/checked.

13. array [990...] I think this needs a more elaborate example that
shows a full use case. Also, what happens if it is passed an infinite range?

And your GCAllocator bonus

14. The macro for array [137] is incomplete so nothing shows up in the
ddoc output.

On the whole I think this module goes way over my head! I think some of
my confusion originates from the naming of RegionAllocatorStack which,
if I'm finally up to speed, is not a stack of RegionAllocators, but the
actual stack which is being allocated from, in segments. I can
understand why the module is not named SegmentAllocator, but nowhere is
the term Region explained.

Is the restriction that only the most recently created RegionAllocator
(for a given stack) can be used going to be universal across all
allocator implementations? It doesn't seem to be the case for the
GCAllocator, which makes me worry that some (future) Allocators will not
be interchangeable, even though they share the same API. That being
said, the only problematic scenarios that I can think of are rather
contrived.

I hope some of that made sense, I suspect much of it may not ><

A...

[Alix Pexton]

Post by Alix Pexton
12. alignBytes [939...] just has me stumped, the introduction says that
16 byte alignment is guaranteed, so shouldn't this always return 16? I
tried to follow the breadcrumbs through the source, but couldn't find
where the value it returns is defined, only places where it is
used/checked.

Found it! 'twas just as I suspected, no idea how I missed it the first
time ><

A...

[Michel Fortin]

Every time I read std.regionallocator, I read "regional locator" and I
find it hillarious. :-)

[Andrei Alexandrescu]

Post by Michel Fortin
Every time I read std.regionallocator, I read "regional locator" and I
find it hillarious. :-)

Yes. That is part of my upcoming review. region_allocator please.

Andrei

[dsimcha]

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article

Post by Andrei Alexandrescu

Post by Michel Fortin
Every time I read std.regionallocator, I read "regional locator" and I
find it hillarious. :-)

Yes. That is part of my upcoming review. region_allocator please.
Andrei

I was thinking std.allocators.region.

[Robert Clipsham]

Post by dsimcha
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article

Post by Andrei Alexandrescu

Post by Michel Fortin
Every time I read std.regionallocator, I read "regional locator" and I
find it hillarious. :-)

Yes. That is part of my upcoming review. region_allocator please.
Andrei

I was thinking std.allocators.region.

+1

[Jacob Carlborg]

Post by dsimcha
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article

Post by Andrei Alexandrescu

Post by Michel Fortin
Every time I read std.regionallocator, I read "regional locator" and I
find it hillarious. :-)

Yes. That is part of my upcoming review. region_allocator please.
Andrei

I was thinking std.allocators.region.

Same here.

[dsimcha]

Post by Andrei Alexandrescu

Post by Michel Fortin
Every time I read std.regionallocator, I read "regional locator" and I
find it hillarious. :-)

Yes. That is part of my upcoming review. region_allocator please.
Andrei

I'm heavily anticipating your review, since I know your reviews tend to
be very thorough and prompt lots of changes. I want to start addressing
the issues raised by others in the community, as well as a few I've
thought of myself, but I'm hesitant to do so until The Official Andrei
Review comes out and I can plan to work those changes in, too.

[Christophe]

I am not experienced in the d programming langage, so rather than
writing a real review, I will just ask questions when I am confused. I
may be confused because I am not very experienced, but I may also
valuables hints to make things clearer to other experienced or not so
experienced d programmers.

Concerning the gcallocator API, why is there no template method that
forwards to new T? Is the user obliged to call allocate, and then
initialise the object manually?

Would it not be useful if all Allocators use Exceptions that derives
from the same Exception subtype ?

Now about RegionAllocator... I took me a lot of time to understand how
it works, and I am not 100% sure about how it works. I had to rewrite my
review when I understood something new and discovered what I had
understood before was false.

This is how I think it works now: Several copies of a RegionAllocator
works just the same. When the last is destroyed, all the memory
allocated is cleared. You can build a RegionAllocator that uses the same
stack as the previous RegionAllocator. This "pauses" all the copies of
the previous allocator: they can no longer allocate or free memory until
all the copies of the new RegionAllocator are destroyed.

Is this "pause" behavior really a desirable functionnality? This makes
the whole behavior of RegionAllocator very confusing, because you have
to make the disctinction between copies of a RegionAllocator and
RegionAllocator that shares the same Stack. Well... copies of a
RegionAllocator do share the same Stack, so it is confusing.

Moreover, it is rather dangerous to use. What if a copy of a
RegionAllocator sharing the same stack as a previous RegionAllocator is
kept unexpectedly alive somewhere while the previous RegionAllocator
goes back into action? What happens if all copies of a RegionAllocator
dies when a RegionAllocator using the same Stack and created later is
still alive? I use 'die' and 'alive' to emphasize the fact that when you
copy those objects you don't control everything that happens to them.
Those allocators are supposed to be put in containers or things like
that, aren't they ? They might really have a life of their own (I would
rather have them being classes that you eventually make scope classes,
but that is not the main point). This behavior is IMO too dangerous to
be desirable in the standard library, especially if users just start to
make newRegionAllocator and do not realize they prevent each other from
working fine.

If I admit that the behavior of RegionAllocator sharing the same stack
but are not direct copies of each other is really what expert users
want, this is badly documented:
- regionAllocatorStack.newRegionAllocator does not tell it invalidates
the use of previously created newRegionAllocators.
- Same for .newRegionAllocator. Moreover, the name of this function is
very confusing. One could think it is brand new, whereas it reuses the
same thread-local stack.
- Introduction of RegionAllocator comment do not tell that copies of a
RegionAllocator are different from RegionAllocators sharing the same
stack (but that do not share the same correctRegionIndex).
- regionAllocator.allocate do not tell it checks it is the lastly
created RegionAllocator that shares the same stack (but not the same
correctRegionIndex).

Now, do the users of RegionAllocator really want memory to be
automatically freed when the RegionAllocator is destructed with no
explicit request, and no way to prevent this?

Important point:
opAssigns seems not to support self assignment of a unique copy of a
RegionAllocator.

I am really sorry if I sound too agressive, and make it sound like all
these functionality are not useful. This RegionAllocator may have
applications and advantages that I am not aware of. I just tought when I
started to read the documentation and the code that this allocator would
bring to the standard library an easy and rather safe way to allocate
memory on a stack by moving a pointer up and down when memory is
requested or discarded, whereas this allocator is much more complicated
than that.

[dsimcha]

Thanks for taking the time to do this review. I appreciate the effort and the
constructive criticism.

== Quote from Christophe (travert at phare.normalesup.org)'s article

Post by Christophe
Concerning the gcallocator API, why is there no template method that
forwards to new T? Is the user obliged to call allocate, and then
initialise the object manually?

Several people have asked this and I think it needs to be added. It's obviously
trivial to implement, but I'm not really sure what to call it yet.

Post by Christophe
Would it not be useful if all Allocators use Exceptions that derives
from the same Exception subtype ?

Hmm, this might get messy in terms of catching other exceptions when forwarding to
e.g. std.array.array() and having to throw a new type of exception. It would be
nice but I'm skeptical about whether it's worth it.

Post by Christophe
Now about RegionAllocator... I took me a lot of time to understand how
it works, and I am not 100% sure about how it works. I had to rewrite my
review when I understood something new and discovered what I had
understood before was false.
This is how I think it works now: Several copies of a RegionAllocator
works just the same. When the last is destroyed, all the memory
allocated is cleared. You can build a RegionAllocator that uses the same
stack as the previous RegionAllocator. This "pauses" all the copies of
the previous allocator: they can no longer allocate or free memory until
all the copies of the new RegionAllocator are destroyed.

Right.

Post by Christophe
Is this "pause" behavior really a desirable functionnality? This makes
the whole behavior of RegionAllocator very confusing, because you have
to make the disctinction between copies of a RegionAllocator and
RegionAllocator that shares the same Stack. Well... copies of a
RegionAllocator do share the same Stack, so it is confusing.

It is a little confusing but it has to be this way for efficiency. If every call
to newRegionAllocator() had to allocate a new block from the heap, this would
largely defeat the purpose in cases where you need, e.g., a temporary array or two.

Post by Christophe
Moreover, it is rather dangerous to use. What if a copy of a
RegionAllocator sharing the same stack as a previous RegionAllocator is
kept unexpectedly alive somewhere while the previous RegionAllocator
goes back into action?

A RegionAllocatorError is thrown. This gives you a decent diagnostic about what
went wrong. This is checked for and you won't get stuck spending an entire
afternoon debugging something silly like this.

Post by Christophe
What happens if all copies of a RegionAllocator
dies when a RegionAllocator using the same Stack and created later is
still alive?

A RegionAllocatorError **should** be thrown here too, though I might have
forgotten about this case.

Post by Christophe
Those allocators are supposed to be put in containers or things like
that, aren't they ? They might really have a life of their own (I would
rather have them being classes that you eventually make scope classes,
but that is not the main point). This behavior is IMO too dangerous to
be desirable in the standard library, especially if users just start to
make newRegionAllocator and do not realize they prevent each other from
working fine.

I see your point but this is a fundamental limitation of the design and is
absolutely necessary for efficiency. If you want to prevent this, give each
container a RegionAllocator with its own RegionAllocatorStack.

Post by Christophe
If I admit that the behavior of RegionAllocator sharing the same stack
but are not direct copies of each other is really what expert users
- regionAllocatorStack.newRegionAllocator does not tell it invalidates
the use of previously created newRegionAllocators.

I thought this was clear from the documentation of the RegionAllocator struct,
though it may be important enough to beat people over the head with a little more
instead of just saying it once or twice.

Post by Christophe
- Same for .newRegionAllocator. Moreover, the name of this function is
very confusing. One could think it is brand new, whereas it reuses the
same thread-local stack.
- Introduction of RegionAllocator comment do not tell that copies of a
RegionAllocator are different from RegionAllocators sharing the same
stack (but that do not share the same correctRegionIndex).

Again, the semantics are unavoidably somewhat complicated and delicate. The only
good way I could think of to document them was through examples.

Post by Christophe
- regionAllocator.allocate do not tell it checks it is the lastly
created RegionAllocator that shares the same stack (but not the same
correctRegionIndex).

correctRegionIndex is just a unique identifier for each RegionAllocator instance
within each stack, and is an implementation detail. I don't understand the
problem here.

Post by Christophe
Now, do the users of RegionAllocator really want memory to be
automatically freed when the RegionAllocator is destructed with no
explicit request, and no way to prevent this?

This is the whole point of scoped allocators. I can't think of a less dangerous
way of implementing something like this. If you want to return
RegionAllocator-allocated memory, take a RegionAllocator as a parameter instead of
creating one.

Post by Christophe
opAssigns seems not to support self assignment of a unique copy of a
RegionAllocator.

This is a bug that needs to be fixed. Thanks for reporting it.

Post by Christophe
I am really sorry if I sound too agressive, and make it sound like all
these functionality are not useful. This RegionAllocator may have
applications and advantages that I am not aware of. I just tought when I
started to read the documentation and the code that this allocator would
bring to the standard library an easy and rather safe way to allocate
memory on a stack by moving a pointer up and down when memory is
requested or discarded, whereas this allocator is much more complicated
than that.

This review contains nothing but perfectly reasonable, constructive criticism. I
appreciate it. My only concern is that I can't think of how to simplify
RegionAllocator without making it less powerful, and since it's an advanced
feature anyhow, I think power needs to be more important than simplicity.

[Timon Gehr]

Post by dsimcha
Thanks for taking the time to do this review. I appreciate the effort and the
constructive criticism.
== Quote from Christophe (travert at phare.normalesup.org)'s article

Post by Christophe
Concerning the gcallocator API, why is there no template method that
forwards to new T? Is the user obliged to call allocate, and then
initialise the object manually?

Several people have asked this and I think it needs to be added. It's obviously
trivial to implement, but I'm not really sure what to call it yet.
[snip.]

'create' has been suggested and seems reasonable.
(personally I would prefer 'New' though.)

Another thing: I sometimes write code like the following:

T[] x;
while(some_condition(...)) {
some_processing();
x ~= some_function(...);
}

i.e. the length of the array is not known exactly in advance. I think
that is a legitimate use case for an allocator, and the GC supports it
natively. (but using std.array.appender can make it faster in some cases)

Shouldn't this be part of the allocator interface? RegionAllocator would
probably be really efficient on that.

Also, if we have a GCAlloc and a RegionAlloc, a simple MallocAlloc could
be useful too.

[dsimcha]

== Quote from Timon Gehr (timon.gehr at gmx.ch)'s article

Post by Timon Gehr

Post by dsimcha
Thanks for taking the time to do this review. I appreciate the effort and the
constructive criticism.
== Quote from Christophe (travert at phare.normalesup.org)'s article

Post by Christophe
Concerning the gcallocator API, why is there no template method that
forwards to new T? Is the user obliged to call allocate, and then
initialise the object manually?

Several people have asked this and I think it needs to be added. It's obviously
trivial to implement, but I'm not really sure what to call it yet.
[snip.]

'create' has been suggested and seems reasonable.
(personally I would prefer 'New' though.)

Sounds good.

Post by Timon Gehr
T[] x;
while(some_condition(...)) {
some_processing();
x ~= some_function(...);
}
i.e. the length of the array is not known exactly in advance. I think
that is a legitimate use case for an allocator, and the GC supports it
natively. (but using std.array.appender can make it faster in some cases)
Shouldn't this be part of the allocator interface? RegionAllocator would
probably be really efficient on that.

Hmm, I'll think about that. When it comes to the balance between making
allocators powerful vs. simple, focused and easy to write, I think array appending
is borderline. It would also get messy in the case of RegionAllocator because you
could only append to the last allocated array.

Post by Timon Gehr
Also, if we have a GCAlloc and a RegionAlloc, a simple MallocAlloc could
be useful too.

This is a todo for eventually. I was going to do it, but ran into some issues
about not knowing things like what alignment different platforms' malloc guarantees.

[Timon Gehr]

Post by dsimcha
== Quote from Timon Gehr (timon.gehr at gmx.ch)'s article

Post by Timon Gehr

Post by dsimcha
Thanks for taking the time to do this review. I appreciate the effort and the
constructive criticism.
== Quote from Christophe (travert at phare.normalesup.org)'s article

Post by Christophe
Concerning the gcallocator API, why is there no template method that
forwards to new T? Is the user obliged to call allocate, and then
initialise the object manually?

Several people have asked this and I think it needs to be added. It's obviously
trivial to implement, but I'm not really sure what to call it yet.
[snip.]

'create' has been suggested and seems reasonable.
(personally I would prefer 'New' though.)

Sounds good.

Post by Timon Gehr
T[] x;
while(some_condition(...)) {
some_processing();
x ~= some_function(...);
}
i.e. the length of the array is not known exactly in advance. I think
that is a legitimate use case for an allocator, and the GC supports it
natively. (but using std.array.appender can make it faster in some cases)
Shouldn't this be part of the allocator interface? RegionAllocator would
probably be really efficient on that.

Hmm, I'll think about that. When it comes to the balance between making
allocators powerful vs. simple, focused and easy to write, I think array appending
is borderline. It would also get messy in the case of RegionAllocator because you
could only append to the last allocated array.

The last allocated one is the array I append to in 80% or more of all
cases. A simple implementation in terms of resize should be really easy
in case an allocator cannot provide specially optimized code.
Would there be a way to implement an efficient appender on top of
RegionAlloc that would match the efficiency of having it in the interface?

Post by dsimcha

Post by Timon Gehr
Also, if we have a GCAlloc and a RegionAlloc, a simple MallocAlloc could
be useful too.

This is a todo for eventually. I was going to do it, but ran into some issues
about not knowing things like what alignment different platforms' malloc guarantees.

Does the standard allocator interface guarantee 16-byte alignment?

[Jonathan M Davis]

Post by Timon Gehr

Post by dsimcha
Thanks for taking the time to do this review. I appreciate the effort
and the constructive criticism.
== Quote from Christophe (travert at phare.normalesup.org)'s article

Post by Christophe
Concerning the gcallocator API, why is there no template method that
forwards to new T? Is the user obliged to call allocate, and then
initialise the object manually?

Several people have asked this and I think it needs to be added. It's
obviously trivial to implement, but I'm not really sure what to call it
yet. [snip.]

'create' has been suggested and seems reasonable.
(personally I would prefer 'New' though.)

New breaks Phobos' naming conventions for functions. create does not.

- Jonathan M Davis

[Christophe]

Post by dsimcha
Right.

OK, I'm glad I got the way RegionAllcator works right.

Post by dsimcha

Post by Christophe
Would it not be useful if all Allocators use Exceptions that derives
from the same Exception subtype ?

Hmm, this might get messy in terms of catching other exceptions when forwarding to
e.g. std.array.array() and having to throw a new type of exception. It would be
nice but I'm skeptical about whether it's worth it.

Why catching other exceptions? This could apply to exceptions thrown by
the allocator itself only. If std.array.array() throws, it is not the
problem of RegionAllocator. But it was a minor comment.

Post by dsimcha
It is a little confusing but it has to be this way for efficiency. If every call
to newRegionAllocator() had to allocate a new block from the heap, this would
largely defeat the purpose in cases where you need, e.g., a temporary array or two.

Having a RegionAllocator with no shared stack does not prevent you from
using a default thread-local RegionAllocator that you use for a
temporary array or two. You're implementation adds the functionality to
throw if two instances of the same RegionAllocator with different
correctRegionIndex are competing, which I agree is a good thing for
debuging.

Post by dsimcha

Post by Christophe
What happens if all copies of a RegionAllocator
dies when a RegionAllocator using the same Stack and created later is
still alive?

A RegionAllocatorError **should** be thrown here too, though I might have
forgotten about this case.

;)

Post by dsimcha

Post by Christophe
- regionAllocator.allocate do not tell it checks it is the lastly
created RegionAllocator that shares the same stack (but not the same
correctRegionIndex).

correctRegionIndex is just a unique identifier for each RegionAllocator instance
within each stack, and is an implementation detail. I don't understand the
problem here.

There is nothing wrong with not telling about correctRegionIndex,
but there are 2 problems:
- allocate tells nothing about checking for the existence of a competing
RegionAllocator and eventually throwing, but it does check and throw (as
it should).
- even if you told you checked for the existence of a competing
allocator, like you did with free, talking about a possible
RegionAllocator that shares the same RegionAllocatorStack is confusing,
because a direct copy of a RegionAllocator is also an instance of
RegionAllocator that shares the same RegionAllocatorStack, but
fortunately do not induce exception throwing. This needs clarification.

Post by dsimcha
This is the whole point of scoped allocators. I can't think of a less dangerous
way of implementing something like this. If you want to return
RegionAllocator-allocated memory, take a RegionAllocator as a parameter instead of
creating one.

OK, there could be another kind of RegionAllocator that is not a scoped
allocator, but it would not be as powerful as a scoped RegionAllocator.

Post by dsimcha

Post by Christophe
opAssigns seems not to support self assignment of a unique copy of a
RegionAllocator.

This is a bug that needs to be fixed. Thanks for reporting it.

;)

Post by dsimcha
This review contains nothing but perfectly reasonable, constructive criticism. I
appreciate it. My only concern is that I can't think of how to simplify
RegionAllocator without making it less powerful, and since it's an advanced
feature anyhow, I think power needs to be more important than simplicity.

Ok, don't drop this feature then. But the API is too complicated. I
think you can keep the same functionality with an API that is much
easier to understand:
- Make RegionAllocatorStack private. This is implementation detail no
one has to know about.
- Create a method for RegionAllocator that is called something like
"invalidatingCopy", which is the same as creating a new regionAllocator
with the same regionAllocatorStack. Tell about the fact that the
invalidatingCopy make the calls to the RegionAllocator being copied
throw until all instances of the invalidatingCopy go out of scope.
- Make a function to call "invalidatingCopy" on the default thread-local
RegionAllocator, to replace newRegionAllocator, but I insist, please use
a different name since it is confusing: it makes you think the allocator
is breand new, whereas it reuses a common stack.
- Make a function to create a brand new allocator with its own stack,
and specifies that the previous function may be more efficient.

With this, I think everybody will understand easily what is an
invalidatingCopy of your allocator. You can explain in allocate,
free and other methods that you check for the existence of an
invalidatingCopy without having to tell anything about
sharing RegionAllocatorStack with other RegionAllocators.

I hope this helps.
Regards.

[Timon Gehr]

Post by Christophe
Ok, don't drop this feature then. But the API is too complicated. I
think you can keep the same functionality with an API that is much
- Make RegionAllocatorStack private. This is implementation detail no
one has to know about.
- Create a method for RegionAllocator that is called something like
"invalidatingCopy", which is the same as creating a new regionAllocator
with the same regionAllocatorStack. Tell about the fact that the
invalidatingCopy make the calls to the RegionAllocator being copied
throw until all instances of the invalidatingCopy go out of scope.
- Make a function to call "invalidatingCopy" on the default thread-local
RegionAllocator, to replace newRegionAllocator, but I insist, please use
a different name since it is confusing: it makes you think the allocator
is breand new, whereas it reuses a common stack.

It is a brand new allocator which operates on an existing stack.

Post by Christophe
- Make a function to create a brand new allocator with its own stack,
and specifies that the previous function may be more efficient.
With this, I think everybody will understand easily what is an
invalidatingCopy of your allocator. You can explain in allocate,
free and other methods that you check for the existence of an
invalidatingCopy without having to tell anything about
sharing RegionAllocatorStack with other RegionAllocators.

Actually, I think the current semantics are a lot less confusing than
the invalidatingCopy proposal:

alloc2 = alloc1.invalidatingCopy();
alloc3 = alloc1.invalidatingCopy();

now alloc2 is invalid, even though you called the invalidatingCopies on
alloc1 only. To get why this is the case, the programmer has to
understand that there is an underlying stack structure, confusingly
hidden away. Therefore, hiding the RegionAllocStack is a leaky
abstraction and does not help. It even hurts, because with it you cannot
pass around a RegionAllocStack without a RegionAlloc operating on it.

[Christophe]

Post by Timon Gehr

Post by Christophe
Ok, don't drop this feature then. But the API is too complicated. I
think you can keep the same functionality with an API that is much
- Make RegionAllocatorStack private. This is implementation detail no
one has to know about.
- Create a method for RegionAllocator that is called something like
"invalidatingCopy", which is the same as creating a new regionAllocator
with the same regionAllocatorStack. Tell about the fact that the
invalidatingCopy make the calls to the RegionAllocator being copied
throw until all instances of the invalidatingCopy go out of scope.
- Make a function to call "invalidatingCopy" on the default thread-local
RegionAllocator, to replace newRegionAllocator, but I insist, please use
a different name since it is confusing: it makes you think the allocator
is breand new, whereas it reuses a common stack.

It is a brand new allocator which operates on an existing stack.

Well, then a simple copy of a RegionAllocator is also brand new, isn't
it ? As is a copy of a File, etc.

Post by Timon Gehr

Post by Christophe
- Make a function to create a brand new allocator with its own stack,
and specifies that the previous function may be more efficient.
With this, I think everybody will understand easily what is an
invalidatingCopy of your allocator. You can explain in allocate,
free and other methods that you check for the existence of an
invalidatingCopy without having to tell anything about
sharing RegionAllocatorStack with other RegionAllocators.

Actually, I think the current semantics are a lot less confusing than
alloc2 = alloc1.invalidatingCopy();
alloc3 = alloc1.invalidatingCopy();
now alloc2 is invalid, even though you called the invalidatingCopies on
alloc1 only. To get why this is the case, the programmer has to
understand that there is an underlying stack structure, confusingly
hidden away. Therefore, hiding the RegionAllocStack is a leaky
abstraction and does not help.

You are right, this is a problem. The documentation of invalidatingCopy
should tell that previously created invalidatingCopies are also
invalidated, and that they should be destroyed in the right order. The
documentation could (and should) tell about the fact that an internal
stack is shared between invalidating copy, that is not the point.
This is the same explanations that what you have to explain carefully in
dsimcha's API.

The point is that you gave an explicit name to invalidatingCopy. With
this API, a user can start to use a RegionAllocator easily, without
knowing about the possibility of the powerful but dangerous idea sharing
stacks. But then, this user see or type this method called
invalidatingCopy, the "invalidating" in the name sounds dangerous and
rings an alarm bell, and he reads carefully the documentation of
invalidatingCopy. All information about stack sharing is gathered in the
documentation of invalidatingCopy. Now, the user may remember having
read in the documentation of allocate, free, etc, that these methods
could throw an exception if an invalidatingCopy had been created, but
having also decided not to use this dangeroursly looking
invalidatingCopy. When he reads the documentation of allocate again, he
now understand quite well what is an invalidating copy.


With dsimcha's API, the user want a RegionAllocator, and types
newRegionAllocator. When he wants a second RegionAllocator, he calls
newRegionAllocator again, but still think he can use the first
allocator. Nothing let him think calling this method twice was so
dangerous. The error message make him look at the documentation of
RegionAllocator.free (if it is the method that threw). He looks at that,
gets confused, does not manage to understand that "an instance of
RegionAllocator using the same RegionAllocatorStack" is something
different than a simple copy of the RegionAllocator structure. He tries
to read a bit further but rails at the documentation being spread
between the introduction of the package, RegionAllocator,
RegionAllocatorStack, and newRegionAllocator, and swears he will not use
RegionAllocator again...

I, as a "new user", understood how RegionAllocator worked only because I
wanted to help in the review process by trying to find out what went
wrong. And I really thought simple copies of a RegionAllocator would
invalidate each other because they used the same RegionAllocatorStack,
until I went down in the code to see how the correctRegionIndex field
worked.

Post by Timon Gehr
It even hurts, because with it you cannot
pass around a RegionAllocStack without a RegionAlloc operating on it.

How is this a problem ?
If it really is, you could still make RegionAllocatorStack available,
but just further down in the documentation, so the user do not have to
read it all if he do not want to use it.

[Timon Gehr]

Post by Christophe

Post by Timon Gehr

Post by Christophe
Ok, don't drop this feature then. But the API is too complicated. I
think you can keep the same functionality with an API that is much
- Make RegionAllocatorStack private. This is implementation detail no
one has to know about.
- Create a method for RegionAllocator that is called something like
"invalidatingCopy", which is the same as creating a new regionAllocator
with the same regionAllocatorStack. Tell about the fact that the
invalidatingCopy make the calls to the RegionAllocator being copied
throw until all instances of the invalidatingCopy go out of scope.
- Make a function to call "invalidatingCopy" on the default thread-local
RegionAllocator, to replace newRegionAllocator, but I insist, please use
a different name since it is confusing: it makes you think the allocator
is breand new, whereas it reuses a common stack.

It is a brand new allocator which operates on an existing stack.

Well, then a simple copy of a RegionAllocator is also brand new, isn't
it ? As is a copy of a File, etc.

Post by Timon Gehr

Post by Christophe
- Make a function to create a brand new allocator with its own stack,
and specifies that the previous function may be more efficient.
With this, I think everybody will understand easily what is an
invalidatingCopy of your allocator. You can explain in allocate,
free and other methods that you check for the existence of an
invalidatingCopy without having to tell anything about
sharing RegionAllocatorStack with other RegionAllocators.

Actually, I think the current semantics are a lot less confusing than
alloc2 = alloc1.invalidatingCopy();
alloc3 = alloc1.invalidatingCopy();
now alloc2 is invalid, even though you called the invalidatingCopies on
alloc1 only. To get why this is the case, the programmer has to
understand that there is an underlying stack structure, confusingly
hidden away. Therefore, hiding the RegionAllocStack is a leaky
abstraction and does not help.

You are right, this is a problem. The documentation of invalidatingCopy
should tell that previously created invalidatingCopies are also
invalidated, and that they should be destroyed in the right order. The
documentation could (and should) tell about the fact that an internal
stack is shared between invalidating copy, that is not the point.
This is the same explanations that what you have to explain carefully in
dsimcha's API.
The point is that you gave an explicit name to invalidatingCopy. With

Basically, what you are trying to do is hiding the underlying reason for
why the function behaves in a way that in your eyes has to result in an
explicit name for it. There are no 'invalidating' semantics. There are
*stack* semantics, and removing the part of the API that is explicit
about that (RegionAllocStack) is not going to help.

Post by Christophe
this API, a user can start to use a RegionAllocator easily, without
knowing about the possibility of the powerful but dangerous idea sharing
stacks. But then, this user see or type this method called
invalidatingCopy, the "invalidating" in the name sounds dangerous and
rings an alarm bell, and he reads carefully the documentation of
invalidatingCopy. All information about stack sharing is gathered in the
documentation of invalidatingCopy. Now, the user may remember having
read in the documentation of allocate, free, etc, that these methods
could throw an exception if an invalidatingCopy had been created, but
having also decided not to use this dangeroursly looking
invalidatingCopy. When he reads the documentation of allocate again, he
now understand quite well what is an invalidating copy.

Well, I don't really want dangerously looking stuff in my codebase, but
I definitely am going to use the region allocator. BTW invalidatingCopy
is a bad name because:

1. nothing is invalidated, the other allocators are just 'suspended'.
2. nothing is copied, the result is a new region allocator.

It is just like a function that is lower on the call stack cannot make
any stack allocations until the function it has called returns.

Post by Christophe
With dsimcha's API, the user want a RegionAllocator, and types
newRegionAllocator. When he wants a second RegionAllocator, he calls
newRegionAllocator again, but still think he can use the first
allocator. Nothing let him think calling this method twice was so
dangerous. The error message make him look at the documentation of
RegionAllocator.free (if it is the method that threw). He looks at that,
gets confused, does not manage to understand that "an instance of
RegionAllocator using the same RegionAllocatorStack" is something
different than a simple copy of the RegionAllocator structure. He tries
to read a bit further but rails at the documentation being spread
between the introduction of the package, RegionAllocator,
RegionAllocatorStack, and newRegionAllocator, and swears he will not use
RegionAllocator again...

This is biased in that it assumes that the documentation will magically
be more understandable if the API changes from a (imo) comprehensive and
powerful one to a dangerously-looking one.

I do not think an user who does not understand the region allocator will
make effective use of it anyways. But I agree that maybe the
documentation should provide some more examples how to make effective
use of the RegionAllocator. Eg. at synopsis, currently a part of the
allocator interface is presented. Probably it would be better to have
synopsis before the comparisons to call stack and heap and to have it
use a larger part of the API that is exclusive to RegionAlloc.

Post by Christophe
I, as a "new user", understood how RegionAllocator worked only because I
wanted to help in the review process by trying to find out what went
wrong. And I really thought simple copies of a RegionAllocator would
invalidate each other because they used the same RegionAllocatorStack,
until I went down in the code to see how the correctRegionIndex field
worked.

Post by Timon Gehr
It even hurts, because with it you cannot
pass around a RegionAllocStack without a RegionAlloc operating on it.

How is this a problem ?

Creating a new RegionAlloc is not free. I don't want overhead for stuff
I don't need.

Post by Christophe
If it really is, you could still make RegionAllocatorStack available,
but just further down in the documentation, so the user do not have to
read it all if he do not want to use it.

Again, making the stack semantics obscure by trying to not show it to
the user as good as possible is not going to help anyone understanding
the stack semantics.

[Christophe]

Post by Timon Gehr
Well, I don't really want dangerously looking stuff in my codebase, but
I definitely am going to use the region allocator. BTW invalidatingCopy
1. nothing is invalidated, the other allocators are just 'suspended'.
2. nothing is copied, the result is a new region allocator.
It is just like a function that is lower on the call stack cannot make
any stack allocations until the function it has called returns.

I prefer to see dangerously looking stuff in the code when one is
performing dangerously looking operations. invalidatingCopy may not be
the right name. suspendingCopy of exclusiveCopy are already two better
names. The point is to give an better name than "RegionAllocator that
share a common RegionAllocatorStack (but are not direct copies of the
RegionAllocator)".

Post by Timon Gehr
This is biased in that it assumes that the documentation will magically
be more understandable if the API changes from a (imo) comprehensive and
powerful one to a dangerously-looking one.

Giving a name to stuff, so that the user is always refered to the same
point in the documentation that you take particularly care to make
understandable, makes the documentation more understandable than spread
documentation. It's not magic.

After more thoughts, this can be achieve by keeping the
RegionAllocatorStack semantic:

auto stack = RegionAllocatorStack(...); // or RegionAllocator.Stack() or
std.region_allocator.Stack()
auto alloc = stack.instanciateAllocator();

The documentation is improved so that instanciateAllocator gives
information about stack sharing and suspension of previous allocators.
Now, in allocate(), free(), etc, the documentation refer to
"RegionAllocators that were instanciated from the same Stack".
Now you have a name that refers to instanciateAllocator.

This can be another name, but not newRegionAllocator. I though about
instanciate because the documentation reads for example in allocate:

| The last block allocated from this RegionAllocator instance can be
| freed by calling RegionAllocator.free or RegionAllocator.freeLast or
| will be automatically freed when the last copy of this RegionAllocator
| instance goes out of scope.

Here the word "instance" is used, but is not defined. The user may think
that a new instance is created when a simple copy of the RegionAllocator
is performed, which is perfectly true, but do not apply to what is meant
in this documentation. If the user was made to type
instanciateAllocator, he could no longer say he had no idea what the
word "instance" could mean in the documentation. newAllocator does not
fulfill this.

In the end you are right, the confusion does not comes from the Stack
semantics, it comes from the fact that newRegionAllocator is not
documented at all, and has a confusing name.

Post by Timon Gehr
I do not think an user who does not understand the region allocator will
make effective use of it anyways.

He will be able to optimize code when a stack allocator is better, even
if he does not know about the possibility to create a new allocator from
the same stack.

Post by Timon Gehr
Creating a new RegionAlloc is not free. I don't want overhead for stuff
I don't need.

Well, it's not free, but its rather cheap. You will not create
RegionAllocatorStack only once in a while. Actually, you want to create
a stack only once per thread. And this stack is created in a library
function in which you can avoid to create the expensive RegionAllocator.

Post by Timon Gehr
Again, making the stack semantics obscure by trying to not show it to
the user as good as possible is not going to help anyone understanding
the stack semantics.

Ok, that's a point.

That should not prevent the RegionAllocator to give a way to instanciate
another RegionAllocator from the same stack, which is more powerful
than having to carry an extra copy of the RegionAllocatorStack, even
it requires calling myAlloc.stack.instanciateAllocator().

[dsimcha]

Post by Christophe
Here the word "instance" is used, but is not defined. The user may think
that a new instance is created when a simple copy of the RegionAllocator
is performed, which is perfectly true, but do not apply to what is meant
in this documentation. If the user was made to type
instanciateAllocator, he could no longer say he had no idea what the
word "instance" could mean in the documentation. newAllocator does not
fulfill this.

Again, the semantics of RegionAllocator and RegionAllocatorStack are
amazingly hard to describe formally but amazingly easy to illustrate by
example. This is all demonstrated in the example code.

[Marco Leise]

Post by Timon Gehr

Post by Christophe
Ok, don't drop this feature then. But the API is too complicated. I
think you can keep the same functionality with an API that is much
- Make RegionAllocatorStack private. This is implementation detail no
one has to know about.
- Create a method for RegionAllocator that is called something like
"invalidatingCopy", which is the same as creating a new regionAllocator
with the same regionAllocatorStack. Tell about the fact that the
invalidatingCopy make the calls to the RegionAllocator being copied
throw until all instances of the invalidatingCopy go out of scope.
- Make a function to call "invalidatingCopy" on the default thread-local
RegionAllocator, to replace newRegionAllocator, but I insist, please use
a different name since it is confusing: it makes you think the allocator
is breand new, whereas it reuses a common stack.

It is a brand new allocator which operates on an existing stack.

Post by Christophe
- Make a function to create a brand new allocator with its own stack,
and specifies that the previous function may be more efficient.
With this, I think everybody will understand easily what is an
invalidatingCopy of your allocator. You can explain in allocate,
free and other methods that you check for the existence of an
invalidatingCopy without having to tell anything about
sharing RegionAllocatorStack with other RegionAllocators.

Actually, I think the current semantics are a lot less confusing than
alloc2 = alloc1.invalidatingCopy();
alloc3 = alloc1.invalidatingCopy();
now alloc2 is invalid, even though you called the invalidatingCopies on
alloc1 only. To get why this is the case, the programmer has to
understand that there is an underlying stack structure, confusingly
hidden away. Therefore, hiding the RegionAllocStack is a leaky
abstraction and does not help. It even hurts, because with it you cannot
pass around a RegionAllocStack without a RegionAlloc operating on it.

alloc2 = alloc1.exclusiveCopy();
alloc3 = alloc1.exclusiveCopy();

Exclusive sounds like it goes beyond the boundaries of the instance you
call it on. I'm all for speaking names if a function does more than what
is common sense. ;)

The sole purpose of GCScan is to feed additional, potential pointers to
the garbage collector, right?

[Timon Gehr]

Post by Marco Leise

Post by Timon Gehr

Post by Christophe
Ok, don't drop this feature then. But the API is too complicated. I
think you can keep the same functionality with an API that is much
- Make RegionAllocatorStack private. This is implementation detail no
one has to know about.
- Create a method for RegionAllocator that is called something like
"invalidatingCopy", which is the same as creating a new regionAllocator
with the same regionAllocatorStack. Tell about the fact that the
invalidatingCopy make the calls to the RegionAllocator being copied
throw until all instances of the invalidatingCopy go out of scope.
- Make a function to call "invalidatingCopy" on the default thread-local
RegionAllocator, to replace newRegionAllocator, but I insist, please use
a different name since it is confusing: it makes you think the allocator
is breand new, whereas it reuses a common stack.

It is a brand new allocator which operates on an existing stack.

Post by Christophe
- Make a function to create a brand new allocator with its own stack,
and specifies that the previous function may be more efficient.
With this, I think everybody will understand easily what is an
invalidatingCopy of your allocator. You can explain in allocate,
free and other methods that you check for the existence of an
invalidatingCopy without having to tell anything about
sharing RegionAllocatorStack with other RegionAllocators.

Actually, I think the current semantics are a lot less confusing than
alloc2 = alloc1.invalidatingCopy();
alloc3 = alloc1.invalidatingCopy();
now alloc2 is invalid, even though you called the invalidatingCopies
on alloc1 only. To get why this is the case, the programmer has to
understand that there is an underlying stack structure, confusingly
hidden away. Therefore, hiding the RegionAllocStack is a leaky
abstraction and does not help. It even hurts, because with it you
cannot pass around a RegionAllocStack without a RegionAlloc operating
on it.

alloc2 = alloc1.exclusiveCopy();
alloc3 = alloc1.exclusiveCopy();
Exclusive sounds like it goes beyond the boundaries of the instance you
call it on. I'm all for speaking names if a function does more than what
is common sense. ;)

speaking name: RegionAllocator*Stack*

auto alloc = *stack*.newRegionAllocator();

;)

Post by Marco Leise
The sole purpose of GCScan is to feed additional, potential pointers to
the garbage collector, right?

Yes, if GCScan is off and your RegionAlloc allocated memory contains
exclusive pointers to the GC heap, those will get collected, which may
result in memory corruption. But turning it on will feed a large portion
of uninitialized memory to the conservative GC, therefore it is better
avoided.

[Martin Nowak]

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;
}

[dsimcha]

Thanks for the review. Detailed comments below.

Post by Martin Nowak
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.
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/.
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.

Post by Martin Nowak
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?

Post by Martin Nowak
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.

Post by Martin Nowak
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.

Post by Martin Nowak
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.

Post by Martin Nowak
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.

Post by Martin Nowak
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.

Post by Martin Nowak
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.

Post by Martin Nowak
9. The allocator interface should have a flag to advice GC range adding.
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.

Post by Martin Nowak
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.

Post by Martin Nowak
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.

Post by Martin Nowak
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.

Post by Martin Nowak
- In the constructor of RegionAllocatorStack you should enforce that
segmentSize is bigger than alignBytes instead of only catching 0.

Good point. Will fix.

Post by Martin Nowak
- 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.

Post by Martin Nowak
- 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.

Post by Martin Nowak
- 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.

[Christophe]

Post by dsimcha
But RAII makes things simple and relatively safe. What would you
suggest as the alternative?

I guess from the rest of his post to make the allocator a class,
scoped on demand, and provide a freeAll function.

Personally, I like to have structs and templates rather than classes and
interfaces in phobos.

Post by dsimcha
Hmm, I really like the idea of the stack memory getting freed
automatically and deterministically by ref counting.

Just an idea, such class could provide a little refCounter to make it
possible to enclose it in a RAII struct, or it could be allowed to
be derived to the same class with a refCounter.

Post by dsimcha
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 think a std lib should provide simple, stupid and composable tools
first, before it provide "just working" big objects (#). That does not
remove any value to your work, but I think your RegionAllocator may come
a little early. IMO, one reason of the disagreement is that People
expect a simple stupid region allocator, and what you provide is a
complexe "shared region allocator".

I must say I come from Unix world, and I am also in favor of
composition.

# At the moment, and with the current documentation your allocator is
not really a "just work" object, since it still creates mental
codebloat.

Post by dsimcha

Post by Martin Nowak
9. The allocator interface should have a flag to advice GC range adding.
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.

I don't really see the point of this either (your implementation of
regionAllocator.alloc does not use GCscan, so we can hardly get how it
is supposed to work).

Post by dsimcha

Post by Martin Nowak
12. Ideally RegionAllocator would be AlignedAllocator!(16,
RegionAllocator!(FreeListAllocator!(LibcAllocator))).

That's maybe composition power pushed a bit far, but that's a good
analysis of what dsimcha provides.
This composition, with an alias to make it more friendly, has some
kind of beauty...

[Timon Gehr]

Post by Christophe

Post by dsimcha
But RAII makes things simple and relatively safe. What would you
suggest as the alternative?

I guess from the rest of his post to make the allocator a class,
scoped on demand, and provide a freeAll function.
Personally, I like to have structs and templates rather than classes and
interfaces in phobos.

Post by dsimcha
Hmm, I really like the idea of the stack memory getting freed
automatically and deterministically by ref counting.

Just an idea, such class could provide a little refCounter to make it
possible to enclose it in a RAII struct, or it could be allowed to
be derived to the same class with a refCounter.

Usually you want RAII. So that should be the simpler thing to have, not
the other way round.

Post by Christophe

Post by dsimcha
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 think a std lib should provide simple, stupid and composable tools
first, before it provide "just working" big objects (#). That does not
remove any value to your work, but I think your RegionAllocator may come
a little early. IMO, one reason of the disagreement is that People
expect a simple stupid region allocator, and what you provide is a
complexe "shared region allocator".
I must say I come from Unix world, and I am also in favor of
composition.

I come from an Unix world, and I don't care about the implementation of
a tool if it is simple to use, efficient and correct. ;)

Post by Christophe
# At the moment, and with the current documentation your allocator is
not really a "just work" object, since it still creates mental
codebloat.

Basically, if it stops to just work for big objects, users have to be
aware of the fact that it might not work, even if there is plenty of
memory available. What does that add in value?

Post by Christophe

Post by dsimcha

Post by Martin Nowak
9. The allocator interface should have a flag to advice GC range adding.
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.

I don't really see the point of this either (your implementation of
regionAllocator.alloc does not use GCscan, so we can hardly get how it
is supposed to work).

Post by dsimcha

Post by Martin Nowak
12. Ideally RegionAllocator would be AlignedAllocator!(16,
RegionAllocator!(FreeListAllocator!(LibcAllocator))).

That's maybe composition power pushed a bit far, but that's a good
analysis of what dsimcha provides.
This composition, with an alias to make it more friendly, has some
kind of beauty...

Beautiful compositions usually come with an overhead that can be avoided.

Example 1: FreeListAllocator!(LibcAllocator) has to be able to handle
allocations of all possible sizes, while the RegionAllocator only needs
a free list for allocated chunks of one fixed size.

But I agree that the internal free list could be opt-out, so that the
allocator is still usable for composing.

Example 2: The AlignedAllocator has to allocate size+alignment bytes
from the RegionAllocator (composeable?) to guarantee the correct
alignment, while if it is built-in, the region allocator can be much
more efficient.

[dsimcha]

== Quote from Timon Gehr (timon.gehr at gmx.ch)'s article

Post by Timon Gehr
Usually you want RAII. So that should be the simpler thing to have, not
the other way round.

Yeah, this sums up the meta-disagreement quite nicely. I and apparently you think
that it's generally better to make what the user probably wants in the most common
cases the easiest thing to get. This is also generally the D, Python and Perl way
of doing things (though I do think Perl takes it a bit too far). Martin and
Christophe are of the opinion that whatever has the least overhead, is simplest to
describe and implement, has the least implicit behavior, etc. should be the
default and let the user compose to get what he/she really wants. This is the
Unix/C and to a lesser extent the C++ way.

While composability is often a good thing, too much of it at the expense of making
the common cases "just work" isn't, IMHO. If the user has to learn to compose
zillions of tiny objects just to handle the most common case properly, this is a
violation of the "make simple things simple" maxim. Java's file I/O API comes to
mind here. Furthermore, if the project is open-source, someone with very
specialized needs can always just fork it and hack the source code to customize
it. This is another argument for "just working" in the common cases at the
expense of being infinitely composable and flexible.

[Martin Nowak]

Post by Christophe

Post by Martin Nowak
12. Ideally RegionAllocator would be AlignedAllocator!(16,
RegionAllocator!(FreeListAllocator!(LibcAllocator))).

That's maybe composition power pushed a bit far, but that's a good
analysis of what dsimcha provides.
This composition, with an alias to make it more friendly, has some
kind of beauty...

I even found a beautiful bug trying this out.
http://d.puremagic.com/issues/show_bug.cgi?id=6630

But especially with classes any thing like that is completely unusable.
You can't pass parameters to the individual constructors and loose track
of function hiding. The long-time direction might use such things behind
the facade.

[Martin Nowak]

Post by dsimcha
Thanks for the review. Detailed comments below.

Post by Martin Nowak
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.
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/.
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.

Post by Martin Nowak
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.

Post by dsimcha

Post by Martin Nowak
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.

Post by dsimcha

Post by Martin Nowak
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).

Post by dsimcha

Post by Martin Nowak
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.

Post by dsimcha

Post by Martin Nowak
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).

Post by dsimcha

Post by Martin Nowak
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.

Post by dsimcha

Post by Martin Nowak
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.

Post by dsimcha

Post by Martin Nowak
9. The allocator interface should have a flag to advice GC range adding.
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.

Post by dsimcha

Post by Martin Nowak
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.

Post by dsimcha

Post by Martin Nowak
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.

Post by dsimcha

Post by Martin Nowak
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);
}

Post by dsimcha

Post by Martin Nowak
- In the constructor of RegionAllocatorStack you should enforce that
segmentSize is bigger than alignBytes instead of only catching 0.

Good point. Will fix.

Post by Martin Nowak
- 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.

Post by Martin Nowak
- 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.

Post by Martin Nowak
- 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

[Martin Nowak]

Post by Martin Nowak

Post by dsimcha

Post by Martin Nowak
- 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.

Sorry for that one I missed that it is part of the allocator interface.

[Andrei Alexandrescu]

Post by Jonathan M Davis
Okay. Onto the next item in the review queue. I'm going to be the review
manager this time around, and we're going to be reviewing dsimcha's region
allocator. The review starts now and will end on 2011-09-21 at midnight in UTC
(so about 2 weeks from now, when the 21st begins). Assuming that we're ready
to vote at that point, I'll start a thread for voting for inclusion in Phobos,
and the vote will last a week. If it's not ready to be voted on for some
reason (such as dsimcha needing to go back and make a bunch of changes that
are going to need to be reviewed), then voting will be postponed and it'll be
put back in the review queue once it's ready for review again.
http://cis.jhu.edu/~dsimcha/d/phobos/std_regionallocator.html

Unfortunately my review is incomplete because I don't see the allocator
interface.

In theory it should be possible to first define the region allocator and
then the allocator interface. The other way around is also valid.
However, clearly it's best to define the general allocator interface
_together_ with the region allocator.

Containers will need an allocator, and I think it's best to make it a
straight dynamic interface. In that design, the region allocator would
offer the scoped structs PLUS factory methods in those structs that
return implementations for those interfaces.

* It's region_allocator or region.allocator, not regionallocator.
Ironically a good example of why is in this very name - is it "region
allocator" or "regional locator"?

* Use "bumped up" and "bumped down" or something instead of
"incremented" and "decremented", which imply 1 as the unit.

* Enumerated paragraphs are not visually distinguished.

* Synopsis should go before the textual intro.

* Exception should be at the bottom, not the top of the dox.

* There's a problem with "std.regionallocator
RegionAllocator.regionallocator RegionAllocator" - i.e. a macro that
didn't expand to what it should have.

* I didn't understand from the dox what the relationship between
RegionAllocator and RegionAllocatorStack is, mainly because
RegionAllocator is used before having been defined. (This is a difficult
problem in general.)

* The GCScan enum is defined uncomfortably far from the places where
it's relevant. (Another difficult matter.)

* I think "scanThreadLocalStack" should be "threadLocalStackIsScannable"
so as people don't confuse it with an action.

* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

* In fact new(Uninitialized)Array should not be a member as its workings
are not specific to this allocator. It should be a free function taking
an allocator as a parameter.

* The documentation for resize() is the first time "allocator interface"
is mentioned (without having been defined). Wait a minute. I was
hungrily looking for this since I opened the doc.

* I think alignBytes should be a compile-time computable property, and
that the documentation should mention that.

* isAutomatic, isScoped, freeIsChecked should also be static and
statically computable properties (perhaps not freeIsChecked).


Andrei

[dsimcha]

Post by Andrei Alexandrescu

Post by Jonathan M Davis
Okay. Onto the next item in the review queue. I'm going to be the review
manager this time around, and we're going to be reviewing dsimcha's region
allocator. The review starts now and will end on 2011-09-21 at midnight in UTC
(so about 2 weeks from now, when the 21st begins). Assuming that we're ready
to vote at that point, I'll start a thread for voting for inclusion in Phobos,
and the vote will last a week. If it's not ready to be voted on for some
reason (such as dsimcha needing to go back and make a bunch of changes that
are going to need to be reviewed), then voting will be postponed and it'll be
put back in the review queue once it's ready for review again.
http://cis.jhu.edu/~dsimcha/d/phobos/std_regionallocator.html

Unfortunately my review is incomplete because I don't see the allocator
interface.
In theory it should be possible to first define the region allocator and
then the allocator interface. The other way around is also valid.
However, clearly it's best to define the general allocator interface
_together_ with the region allocator.

I mostly took your proposal from a few months ago and doctored it
slightly. Basically, my theory was to define the allocator interface by
example (both RegionAllocator and GCAllocator being examples) and
resolve any ambiguities through the review process before creating more
formal documentation of the allocator interface. I'll probably create a
std.allocator.allocator, which would be similar to the top of
std.container and contain documentation of the general allocator interface.

Post by Andrei Alexandrescu
Containers will need an allocator, and I think it's best to make it a
straight dynamic interface. In that design, the region allocator would
offer the scoped structs PLUS factory methods in those structs that
return implementations for those interfaces.

"Dynamic" as in using the `interface` keyword? My concern with this is
that a major purpose of RegionAllocator is to avoid the GC and its
global lock like the plague. I think it would be a **terrible** misuse
of things if you had to perform a heap allocation to get at the dynamic
interface. I'll think about this, though. There may be an easy
workaround.

My other concern is that dynamic interfaces would break ref counting of
RegionAllocator instances because the GC frees things in an undefined
order, and I guess you'd have to rely on the GC to free a region. Maybe
I'm completely misunderstanding your suggestion, though.

Post by Andrei Alexandrescu
* It's region_allocator or region.allocator, not regionallocator.
Ironically a good example of why is in this very name - is it "region
allocator" or "regional locator"?

You mean for the module name? I was thinking std.allocators.region.
Are you ok with this, too?

Post by Andrei Alexandrescu
* Use "bumped up" and "bumped down" or something instead of
"incremented" and "decremented", which imply 1 as the unit.

Good point.

Post by Andrei Alexandrescu
* Enumerated paragraphs are not visually distinguished.

If you mean the lists of advantages/disadvantages at the top of the
module, I'd like to distinguish them better but don't know how to in
DDoc. Any advice?

Post by Andrei Alexandrescu
* Synopsis should go before the textual intro.

Ok.

Post by Andrei Alexandrescu
* Exception should be at the bottom, not the top of the dox.

Makes sense. I'm also thinking it should be derived from Error, not
Exception and be renamed RegionAllocatorError, since it's only thrown on
API misuse, i.e. bugs in client code. I could also use asserts, but I
decided not to because I've made it so that everything can be checked
cheaply and measured to make sure the checking doesn't lead to
performance problems, and because certain misuses of the API would be
virtually impossible to debug without the exception error messages.

Post by Andrei Alexandrescu
* There's a problem with "std.regionallocator
RegionAllocator.regionallocator RegionAllocator" - i.e. a macro that
didn't expand to what it should have.

I noticed this, too, but have no idea how to fix it.

Post by Andrei Alexandrescu
* I didn't understand from the dox what the relationship between
RegionAllocator and RegionAllocatorStack is, mainly because
RegionAllocator is used before having been defined. (This is a difficult
problem in general.)

Hmm, maybe I should move RegionAllocator before RegionAllocatorStack and
focus on the thread-local default instantiation first, since this is
what people should use for most simple use cases. Creating explicit
RegionAllocatorStack instances is a more advanced use case.

Anyhow, the explanation FYI is that a RegionAllocatorStack is a large
chunk of memory and can be allocated from by the RegionAllocator that's
conceptually at the top of the stack. When the last instance of the
RegionAllocator at the top of the stack goes out of scope (this is kept
track of via reference counting), the RegionAllocatorStack is freed up
to the memory used by the next RegionAllocator down on the stack.
Conceptually, you can think of this as a "stack of simple regions" where
"simple regions" are the canonical ones described in the literature
rather than the somewhat embellished ones in this module.

Post by Andrei Alexandrescu
* The GCScan enum is defined uncomfortably far from the places where
it's relevant. (Another difficult matter.)

I agree, but I don't really see any easy way to fix this. I could put
GCScan inside RegionAllocatorStack, but who wants to type
RegionAllocatorStack.GCScan.yes just to get a simple flag?

Post by Andrei Alexandrescu
* I think "scanThreadLocalStack" should be "threadLocalStackIsScannable"
so as people don't confuse it with an action.

Sounds good.

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Post by Andrei Alexandrescu
* In fact new(Uninitialized)Array should not be a member as its workings
are not specific to this allocator. It should be a free function taking
an allocator as a parameter.

My concern about this is that some allocators might want to do some
"special" things based on knowing the type. A good example is that
GCAllocator decides whether to scan for pointers based on knowing the
type. RegionAllocator has a completely different method for determining
this policy. When/if I make a std.allocators.allocator (which would
contain documentation of the general allocator interface, etc.) I can
make a mixin template that provides default implementations of things
that have obvious implementations in terms of lower-level allocator
features. (I think array() would also be included here.) This could be
mixed in and overridden if need be, but would provide the defaults to
save on code duplication across allocators.

Post by Andrei Alexandrescu
* The documentation for resize() is the first time "allocator interface"
is mentioned (without having been defined). Wait a minute. I was
hungrily looking for this since I opened the doc.

Yeah, see above about documentation of the allocator interface.

Post by Andrei Alexandrescu
* I think alignBytes should be a compile-time computable property, and
that the documentation should mention that.

Good point.

Post by Andrei Alexandrescu
* isAutomatic, isScoped, freeIsChecked should also be static and
statically computable properties (perhaps not freeIsChecked).

I think they are (actually, I think they're enums) and DDoc just doesn't
reflect this. If not, then I'll definitely fix it.

Post by Andrei Alexandrescu
Andrei

[dsimcha]

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions,
it's a compile time error, not a runtime error. For example:

auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

[Timon Gehr]

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

It is possible to determine the number of dimensions automatically
during compile time, eg like this:

template NumDim(T){enum NumDim=0;}
template NumDim(T:T[]){enum NumDim=NumDim!T+1;}

unittest{
static assert(NumDim!int==0);
static assert(NumDim!(int[])==1);
static assert(NumDim!(int[][])==2);
static assert(NumDim!(int[][][])==3);
}

[dsimcha]

Post by Timon Gehr

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

It is possible to determine the number of dimensions automatically
template NumDim(T){enum NumDim=0;}
template NumDim(T:T[]){enum NumDim=NumDim!T+1;}
unittest{
static assert(NumDim!int==0);
static assert(NumDim!(int[])==1);
static assert(NumDim!(int[][])==2);
static assert(NumDim!(int[][][])==3);
}

IIUC you misunderstood. I think Andrei was suggesting the following
signature:

auto newArray(T)(size_t[] dims...);

You can't get the size of dims at compile time.

[Timon Gehr]

Post by Timon Gehr

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

It is possible to determine the number of dimensions automatically
template NumDim(T){enum NumDim=0;}
template NumDim(T:T[]){enum NumDim=NumDim!T+1;}
unittest{
static assert(NumDim!int==0);
static assert(NumDim!(int[])==1);
static assert(NumDim!(int[][])==2);
static assert(NumDim!(int[][][])==3);
}

IIUC you misunderstood. I think Andrei was suggesting the following
auto newArray(T)(size_t[] dims...);
You can't get the size of dims at compile time.

I think he meant

auto new Array(T,A...)(A dims) if(NumDim!T==A.length);

[Timon Gehr]

Post by Timon Gehr

Post by Timon Gehr

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

It is possible to determine the number of dimensions automatically
template NumDim(T){enum NumDim=0;}
template NumDim(T:T[]){enum NumDim=NumDim!T+1;}
unittest{
static assert(NumDim!int==0);
static assert(NumDim!(int[])==1);
static assert(NumDim!(int[][])==2);
static assert(NumDim!(int[][][])==3);
}

IIUC you misunderstood. I think Andrei was suggesting the following
auto newArray(T)(size_t[] dims...);
You can't get the size of dims at compile time.

I think he meant
auto new Array(T,A...)(A dims) if(NumDim!T==A.length);

sry:

auto new Array(T,A...)(A dims) if(NumDim!T>=A.length);

[dsimcha]

Post by Timon Gehr

Post by Timon Gehr

Post by Timon Gehr

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

It is possible to determine the number of dimensions automatically
template NumDim(T){enum NumDim=0;}
template NumDim(T:T[]){enum NumDim=NumDim!T+1;}
unittest{
static assert(NumDim!int==0);
static assert(NumDim!(int[])==1);
static assert(NumDim!(int[][])==2);
static assert(NumDim!(int[][][])==3);
}

IIUC you misunderstood. I think Andrei was suggesting the following
auto newArray(T)(size_t[] dims...);
You can't get the size of dims at compile time.

I think he meant
auto new Array(T,A...)(A dims) if(NumDim!T==A.length);

auto new Array(T,A...)(A dims) if(NumDim!T>=A.length);

No, that's roughly what I have now.

[Timon Gehr]

Post by dsimcha

Post by Timon Gehr

Post by Timon Gehr

Post by Timon Gehr

Post by Andrei Alexandrescu
* newArray could only take the element type as a template
parameter;
the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

It is possible to determine the number of dimensions automatically
template NumDim(T){enum NumDim=0;}
template NumDim(T:T[]){enum NumDim=NumDim!T+1;}
unittest{
static assert(NumDim!int==0);
static assert(NumDim!(int[])==1);
static assert(NumDim!(int[][])==2);
static assert(NumDim!(int[][][])==3);
}

IIUC you misunderstood. I think Andrei was suggesting the following
auto newArray(T)(size_t[] dims...);
You can't get the size of dims at compile time.

I think he meant
auto new Array(T,A...)(A dims) if(NumDim!T==A.length);

auto new Array(T,A...)(A dims) if(NumDim!T>=A.length);

No, that's roughly what I have now.

Oh k. Then I don't understand what his remark was about.

[Andrei Alexandrescu]

Post by Timon Gehr

Post by Timon Gehr

Post by Timon Gehr

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

It is possible to determine the number of dimensions automatically
template NumDim(T){enum NumDim=0;}
template NumDim(T:T[]){enum NumDim=NumDim!T+1;}
unittest{
static assert(NumDim!int==0);
static assert(NumDim!(int[])==1);
static assert(NumDim!(int[][])==2);
static assert(NumDim!(int[][][])==3);
}

IIUC you misunderstood. I think Andrei was suggesting the following
auto newArray(T)(size_t[] dims...);
You can't get the size of dims at compile time.

I think he meant
auto new Array(T,A...)(A dims) if(NumDim!T==A.length);

auto new Array(T,A...)(A dims) if(NumDim!T>=A.length);

No, T would be the element type.

Andrei

[Andrei Alexandrescu]

Post by Timon Gehr

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

It is possible to determine the number of dimensions automatically
template NumDim(T){enum NumDim=0;}
template NumDim(T:T[]){enum NumDim=NumDim!T+1;}
unittest{
static assert(NumDim!int==0);
static assert(NumDim!(int[])==1);
static assert(NumDim!(int[][])==2);
static assert(NumDim!(int[][][])==3);
}

IIUC you misunderstood. I think Andrei was suggesting the following
auto newArray(T)(size_t[] dims...);

Instead:

auto newArray(T, Args...)(Args dims) if (suitable_constraint);


Andrei

[Andrei Alexandrescu]

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

If you just require

auto foo = alloc.newArray!int(8, 6, 7, 5, 3, 0, 9);

there's never an error, the array is created with as many dimensions as
numbers. A mistake in choosing that number will never get unnoticed
because the array type will be screwed up.


Andrei

[dsimcha]

Post by Andrei Alexandrescu

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

If you just require
auto foo = alloc.newArray!int(8, 6, 7, 5, 3, 0, 9);
there's never an error, the array is created with as many dimensions as
numbers. A mistake in choosing that number will never get unnoticed
because the array type will be screwed up.
Andrei

Yeah, but I prefer (admittedly subjective) the way I have. It's
consistent with and looks roughly the same as the standard D syntax:

auto foo = new int[][](3);
auto bar = new int[][](3, 2);

It also makes it easy to create, e.g., an int[][] and only initialize
the first dimension.

[Timon Gehr]

Post by Andrei Alexandrescu

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

If you just require
auto foo = alloc.newArray!int(8, 6, 7, 5, 3, 0, 9);
there's never an error, the array is created with as many dimensions as
numbers. A mistake in choosing that number will never get unnoticed
because the array type will be screwed up.
Andrei

The current interface allows to only initialize the first 1 to
nDimensions!T dimensions:

auto foo = alloc.newArray!(int[][])(2); // OK

assert(foo.length==2);
assert(foo[0] is null);

[Timon Gehr]

Post by Timon Gehr

Post by Andrei Alexandrescu

Post by Andrei Alexandrescu
* newArray could only take the element type as a template parameter; the
number of dimensions in unequivocally determined from the number of
arguments.

Good point. Actually, this can probably be changed in
std.array.uninitializedArray, too. There was some reason why I did it
the way I did, but I don't remember why. I'll look into it.

Ok, now I remember. It was so that if you give too many dimensions, it's
auto foo = alloc.newArray!(int[][])(8, 6, 7, 5, 3, 0, 9); // Error

If you just require
auto foo = alloc.newArray!int(8, 6, 7, 5, 3, 0, 9);
there's never an error, the array is created with as many dimensions as
numbers. A mistake in choosing that number will never get unnoticed
because the array type will be screwed up.
Andrei

The current interface allows to only initialize the first 1 to
auto foo = alloc.newArray!(int[][])(2); // OK
assert(foo.length==2);
assert(foo[0] is null);

Well, your proposal does too:

auto foo = alloc.newArray!(int[])(2);

But I think that really looks like the creation of a one-dimensional array.

[Andrei Alexandrescu]

Post by dsimcha
I mostly took your proposal from a few months ago and doctored it
slightly. Basically, my theory was to define the allocator interface by
example (both RegionAllocator and GCAllocator being examples) and
resolve any ambiguities through the review process before creating more
formal documentation of the allocator interface. I'll probably create a
std.allocator.allocator, which would be similar to the top of
std.container and contain documentation of the general allocator interface.

Then I think we all need to defer reviews to that time.

Post by dsimcha

Post by Andrei Alexandrescu
Containers will need an allocator, and I think it's best to make it a
straight dynamic interface. In that design, the region allocator would
offer the scoped structs PLUS factory methods in those structs that
return implementations for those interfaces.

"Dynamic" as in using the `interface` keyword?

Yes.

Post by dsimcha
My concern with this is
that a major purpose of RegionAllocator is to avoid the GC and its
global lock like the plague. I think it would be a **terrible** misuse
of things if you had to perform a heap allocation to get at the dynamic
interface. I'll think about this, though. There may be an easy workaround.

A possibility is to allocate the interface's implementation not with
new, but instead straight in your own allocator.

Containers will need to use an interface-based allocator. It's not a
lightly-taken decision, but it's the least of many evils. If we can't
get a scoped allocator to give back interfaces, we won't be able to use
containers with scoped allocators.

Post by dsimcha
My other concern is that dynamic interfaces would break ref counting of
RegionAllocator instances because the GC frees things in an undefined
order, and I guess you'd have to rely on the GC to free a region. Maybe
I'm completely misunderstanding your suggestion, though.

The types as you define them stay put. All we need is a method
getAllocatorInterface() that returns an interface. It would be simplest
to allocate that interface's implementation on the heap because it makes
things safe. But then safety is not this allocator's stronghold.

Post by dsimcha

Post by Andrei Alexandrescu
* It's region_allocator or region.allocator, not regionallocator.
Ironically a good example of why is in this very name - is it "region
allocator" or "regional locator"?

You mean for the module name? I was thinking std.allocators.region. Are
you ok with this, too?

Yah, I just emphasized the convention.

Post by dsimcha

Post by Andrei Alexandrescu
* Enumerated paragraphs are not visually distinguished.

If you mean the lists of advantages/disadvantages at the top of the
module, I'd like to distinguish them better but don't know how to in
DDoc. Any advice?

$(OL ...)

Post by dsimcha

Post by Andrei Alexandrescu
* I didn't understand from the dox what the relationship between
RegionAllocator and RegionAllocatorStack is, mainly because
RegionAllocator is used before having been defined. (This is a difficult
problem in general.)

Hmm, maybe I should move RegionAllocator before RegionAllocatorStack and
focus on the thread-local default instantiation first, since this is
what people should use for most simple use cases. Creating explicit
RegionAllocatorStack instances is a more advanced use case.

I see two possibilities among many others:

1. Motivate properly both, then introduce them in their logical order.

2. Motivate one in ways independent from the other, introduce it,
motivate the second by distinguishing from the first, introduce it.

See what fits this case best.

Post by dsimcha

Post by Andrei Alexandrescu
* The GCScan enum is defined uncomfortably far from the places where
it's relevant. (Another difficult matter.)

I agree, but I don't really see any easy way to fix this. I could put
GCScan inside RegionAllocatorStack, but who wants to type
RegionAllocatorStack.GCScan.yes just to get a simple flag?

Cue that long discussion about yesno, named parameters etc. :o)

Post by dsimcha

Post by Andrei Alexandrescu
* In fact new(Uninitialized)Array should not be a member as its workings
are not specific to this allocator. It should be a free function taking
an allocator as a parameter.

My concern about this is that some allocators might want to do some
"special" things based on knowing the type. A good example is that
GCAllocator decides whether to scan for pointers based on knowing the
type. RegionAllocator has a completely different method for determining
this policy. When/if I make a std.allocators.allocator (which would
contain documentation of the general allocator interface, etc.) I can
make a mixin template that provides default implementations of things
that have obvious implementations in terms of lower-level allocator
features. (I think array() would also be included here.) This could be
mixed in and overridden if need be, but would provide the defaults to
save on code duplication across allocators.

All good points, which suggest that, again, we need some more design,
code, and review time for the region allocator. I don't think we should
approve region allocator as a tentative implementation of an interface
that hasn't been decided yet.

Generally it would be great to avoid type parameterization of the
allocator. It's been in the STL since forever and it hasn't anything
good. But you're making a good point about scanning. It would be perfect
if generally the GC knew for most or all pieces of memory their type.


Andrei

[dsimcha]

Post by Andrei Alexandrescu
All good points, which suggest that, again, we need some more design,
code, and review time for the region allocator. I don't think we should
approve region allocator as a tentative implementation of an interface
that hasn't been decided yet.

Ok, well then I'll get busy creating a more formal description of the
allocator interface, possibly tomorrow. It exists in my head and
apparently the lack of formal documentation for it is more of a problem
than I thought it would be.

Post by Andrei Alexandrescu
Generally it would be great to avoid type parameterization of the
allocator. It's been in the STL since forever and it hasn't anything
good.

You mean type parametrization as in RegionAllocator!(someType) or
parametrization of just individual methods?

[dsimcha]

Post by Andrei Alexandrescu

Post by dsimcha
My concern with this is
that a major purpose of RegionAllocator is to avoid the GC and its
global lock like the plague. I think it would be a **terrible** misuse
of things if you had to perform a heap allocation to get at the dynamic
interface. I'll think about this, though. There may be an easy workaround.

A possibility is to allocate the interface's implementation not with
new, but instead straight in your own allocator.

Good idea.

Post by Andrei Alexandrescu
Containers will need to use an interface-based allocator. It's not a
lightly-taken decision, but it's the least of many evils. If we can't
get a scoped allocator to give back interfaces, we won't be able to use
containers with scoped allocators.

Post by dsimcha
My other concern is that dynamic interfaces would break ref counting of
RegionAllocator instances because the GC frees things in an undefined
order, and I guess you'd have to rely on the GC to free a region. Maybe
I'm completely misunderstanding your suggestion, though.

The types as you define them stay put. All we need is a method
getAllocatorInterface() that returns an interface. It would be simplest
to allocate that interface's implementation on the heap because it makes
things safe. But then safety is not this allocator's stronghold.

Another issue is that templated methods (e.g. newArray) can't be virtual
functions. This means they would have to be final in the Allocator
dynamic interface, meaning I couldn't allow the allocator to specialize
on types.

Also, how do you recommend freeing RegionAllocator-allocated memory
allocated via a dynamic interface? The obvious answer is when the
RegionAllocator that the dynamic interface was obtained from goes out of
scope, but I'm not quite sure.

[Martin Nowak]

RegionAllocator should have a dup function (better name required),
which will call newRegionAllocator on it's stack.
This is needed to create a nested scope without knowing the used stack.

martin

[dsimcha]

Post by Martin Nowak
RegionAllocator should have a dup function (better name required),
which will call newRegionAllocator on it's stack.
This is needed to create a nested scope without knowing the used stack.
martin

Good idea. This does suggest a little refactoring, though, because I
really don't want to add a **third** way to create a RegionAllocator.

[dsimcha]

Post by Martin Nowak
RegionAllocator should have a dup function (better name required),
which will call newRegionAllocator on it's stack.
This is needed to create a nested scope without knowing the used stack.
martin

Good idea. This does suggest a little refactoring, though, because I
really don't want to add a **third** way to create a RegionAllocator.

Hmm, just off the top of my head, this might solve tons of problems:

1. Take RegionAllocatorStack out of the public API. It would still
exist conceptually, though.

2. newRegionAllocator() -> newRegionAllocator(newStackSize = 0); If
newStackSize == 0, return a RegionAllocator that uses the thread-local
stack. If newStackSize > 0, create a new stack (hidden from the user)
and return a new RegionAllocator on that stack.

3. Add dup(). Maybe call it newInstance() instead, or even just
newRegionAllocator(). Someone please suggest a good name. If using
explicit stacks the workflow would be:

void fun() {
// The whole stack is freed on exiting from fun, along with arr.
auto baseAlloc = newRegionAllocator(42 * 1024);
auto arr = baseAlloc.newArray!(int[])(666);
gun(baseAlloc);
}

void gun(RegionAllocator alloc) {
auto alloc2 = alloc.dup();

// arr2 is allocated on alloc2, freed on exit.
auto arr2 = alloc2.newArray!(int[])(42);
}

[Martin Nowak]

Looks good.

Maybe nesting is a good name for the whole concept.
This would require further introductory explanation at the module header.
Possibly this can be partly merge with the explanation of stack pointer
bumping.

/*
* ...
* Multiple instances of RegionAllocator may use the same stack in which
case
* they are nested instances.
* When a nested RegionAllocator is destroyed, all memory allocated by it
* is returned to its stack.
* Memory may only be allocated by the most nested RegionAllocator.
*/

/*
* Creates a RegionAllocator using a thread local stack.
* If the thread local stack is already used by a RegionAllocator
* the returned RegionAllocator will be nested.
*/
newRegionAllocator();

/*
* Creates a RegionAllocator using a new stack.
* The stack will be freed when the returned RegionAllocator is destroyed.
*/
newRegionAllocator(size_t segmentSize, GCScan scan = GCScan.no);

struct RegionAllocator
{
/*
* Returns a new RegionAllocator using the same stack as this instance.
* When the nested allocator is destroyed all memory allocated by
* it will be freed. Memory allocated by this instance is unaffected.
* You may only allocate memory using the most nested instance.
*/
RegionAllocator nestedAllocator();
}

[dsimcha]

I like it. Thanks for the idea.

Post by Martin Nowak
Looks good.
Maybe nesting is a good name for the whole concept.
This would require further introductory explanation at the module header.
Possibly this can be partly merge with the explanation of stack pointer
bumping.
/*
* ...
* Multiple instances of RegionAllocator may use the same stack in which
case
* they are nested instances.
* When a nested RegionAllocator is destroyed, all memory allocated by it
* is returned to its stack.
* Memory may only be allocated by the most nested RegionAllocator.
*/
/*
* Creates a RegionAllocator using a thread local stack.
* If the thread local stack is already used by a RegionAllocator
* the returned RegionAllocator will be nested.
*/
newRegionAllocator();
/*
* Creates a RegionAllocator using a new stack.
* The stack will be freed when the returned RegionAllocator is destroyed.
*/
newRegionAllocator(size_t segmentSize, GCScan scan = GCScan.no);
struct RegionAllocator
{
/*
* Returns a new RegionAllocator using the same stack as this instance.
* When the nested allocator is destroyed all memory allocated by
* it will be freed. Memory allocated by this instance is unaffected.
* You may only allocate memory using the most nested instance.
*/
RegionAllocator nestedAllocator();
}

[dsimcha]

Ok, implemented. It definitely makes the design cleaner. Thanks again.
The delay was just because I had waited a while to see if any other
comments came up that would make me change my mind or turn the whole
design upside down.

Code:

https://github.com/dsimcha/TempAlloc/tree/master/std/allocators

Docs:
http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_allocator.html
http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_gc.html
http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_region.html

Post by Martin Nowak
Looks good.
Maybe nesting is a good name for the whole concept.
This would require further introductory explanation at the module header.
Possibly this can be partly merge with the explanation of stack pointer
bumping.
/*
* ...
* Multiple instances of RegionAllocator may use the same stack in which
case
* they are nested instances.
* When a nested RegionAllocator is destroyed, all memory allocated by it
* is returned to its stack.
* Memory may only be allocated by the most nested RegionAllocator.
*/
/*
* Creates a RegionAllocator using a thread local stack.
* If the thread local stack is already used by a RegionAllocator
* the returned RegionAllocator will be nested.
*/
newRegionAllocator();
/*
* Creates a RegionAllocator using a new stack.
* The stack will be freed when the returned RegionAllocator is destroyed.
*/
newRegionAllocator(size_t segmentSize, GCScan scan = GCScan.no);
struct RegionAllocator
{
/*
* Returns a new RegionAllocator using the same stack as this instance.
* When the nested allocator is destroyed all memory allocated by
* it will be freed. Memory allocated by this instance is unaffected.
* You may only allocate memory using the most nested instance.
*/
RegionAllocator nestedAllocator();
}

[Robert Jacques]

Post by dsimcha
Ok, implemented. It definitely makes the design cleaner. Thanks again.
The delay was just because I had waited a while to see if any other
comments came up that would make me change my mind or turn the whole
design upside down.
https://github.com/dsimcha/TempAlloc/tree/master/std/allocators
http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_allocator.html
http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_gc.html
http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_region.html

Here's a couple of thoughts on the allocator API design, given my experience with appender:

1) Regarding: void* allocate(size_t nBytes);
You should be able to allocate memory and specify the GC block attributes (scanning in particular). i.e. something like

auto ptr = alloc.allocate(128, Allocator.BlkAttr.SCAN); // See GC.BlkAttr and GC.qalloc

By correlation, void* free(void* ptr); also needs to take a BlkAttr. i.e. so that a region allocator could then remove scan from a memory block, etc.

void* allocate(size_t nBytes, Allocator.BlkAttr blkAttr = Allocator.BlkAttr.NO_SCAN);
void* free (void* ptr , Allocator.BlkAttr blkAttr = Allocator.BlkAttr.NO_SCAN);

2) Regarding: bool resize(void* ptr, size_t nBytes);
You should be able to specify both the desired and a minimum number of bytes for the resize operation. Also, in terms of nomenclature, I like 'extend' better as 'resize' implies a realloc in my mind. i.e.

alloc.resize(ptr, 128+4, 128+128); // See GC.extend

size_t resize(void* ptr, size_t minBytes, size_t nBytes);
//alternatively, have separate resize and extend routines.
bool resize(void* ptr, size_t nBytes);
size_t extend(void* p, size_t minBytes, size_t maxBytes);

3) Regarding: size_t allocSize(size_t nBytes);
This function only needs to be used if the allocator allows variable sized allocation blocks (like the GC). A static bool to flag this would be amiable to conditional compilation.

4) Regarding: size_t alignBytes(size_t nBytes);
The documentation of this needs to be improved. Specifically, there is no guarantee that the function will behave 'sanely'. i.e. does

alignBytes(N) <= alignBytes(M) && N <= M

hold true? And what's the value of alignBytes(0)?

[Jonathan M Davis]

Okay. The review period for the region allocator is over (actually, it was
over about 2 days ago, but I've been busy and forgot to post about it). So,
the question is: Is it ready for a vote, or does it need further revision and
review?

Looking over the thread, it's not at all clear to me that we're ready for a
vote - particularly since the most recent update was fairly recent and almost
no one has commented on the changes. Also, I believe that the most recent
revision is the first to include std.allocators.allocator, and it's
particularly critical that that be solid before moving forward with custom
allocators. So, I'm not at all convinced that this is ready for a vote, but I
don't know.

David, would you consider it to be ready for a vote?

- Jonathan M Davis

[dsimcha]

Post by Jonathan M Davis
Okay. The review period for the region allocator is over (actually, it was
over about 2 days ago, but I've been busy and forgot to post about it). So,
the question is: Is it ready for a vote, or does it need further revision and
review?
Looking over the thread, it's not at all clear to me that we're ready for a
vote - particularly since the most recent update was fairly recent and almost
no one has commented on the changes. Also, I believe that the most recent
revision is the first to include std.allocators.allocator, and it's
particularly critical that that be solid before moving forward with custom
allocators. So, I'm not at all convinced that this is ready for a vote, but I
don't know.
David, would you consider it to be ready for a vote?
- Jonathan M Davis

Hmm, I had noticed that the deadline had passed but didn't want to say
anything because I was hoping to get a few more reviews. Uhh, I guess
we should vote on it. Also note that I forgot to comment on this before
but resize() will be changed to:

size_t resize(void* ptr, size_t minBytes, size_t nBytes);

where minBytes is the minimum amount to declare success and nBytes is
the desired amount.

[Alix Pexton]

Post by Robert Jacques
size_t resize(void* ptr, size_t minBytes, size_t nBytes);
where minBytes is the minimum amount to declare success and nBytes is
the desired amount.

and the value returned is the new size, which will always be between
minBytes and nBytes?

A...

[dsimcha]

== Quote from Alix Pexton (alix.DOT.pexton at gmail.DOT.com)'s article

Post by Alix Pexton

Post by Robert Jacques
size_t resize(void* ptr, size_t minBytes, size_t nBytes);
where minBytes is the minimum amount to declare success and nBytes is
the desired amount.

and the value returned is the new size, which will always be between
minBytes and nBytes?
A...

...or zero on failure, similar to GC.extend.