www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Formal Review of region allocator begins

reply Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Sep 06 2011
next sibling parent reply "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Tue, 06 Sep 2011 22:53:31 +0300, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 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. -- Best regards, Vladimir mailto:vladimir thecybershadow.net
Sep 06 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/06/2011 10:34 PM, Vladimir Panteleev wrote:
 On Tue, 06 Sep 2011 22:53:31 +0300, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 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.
Sep 06 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 9/6/2011 5:11 PM, Vladimir Panteleev wrote:
 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.
Sep 06 2011
prev sibling next sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Tue, 06 Sep 2011 23:52:20 +0300, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 09/06/2011 10:34 PM, Vladimir Panteleev wrote:
 On Tue, 06 Sep 2011 22:53:31 +0300, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 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 :) -- Best regards, Vladimir mailto:vladimir thecybershadow.net
Sep 06 2011
prev sibling next sibling parent dsimcha <dsimcha yahoo.com> writes:
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.
Sep 06 2011
prev sibling next sibling parent reply Alix Pexton <alix.DOT.pexton gmail.DOT.com> writes:
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...
Sep 07 2011
parent Alix Pexton <alix.DOT.pexton gmail.DOT.com> writes:
On 07/09/2011 14:05, Alix Pexton wrote:

 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...
Sep 08 2011
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
Every time I read std.regionallocator, I read "regional locator" and I 
find it hillarious. :-)

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Sep 07 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/7/11 8:45 AM, Michel Fortin wrote:
 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
Sep 07 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 On 9/7/11 8:45 AM, Michel Fortin wrote:
 Every time I read std.regionallocator, I read "regional locator" and I
 find it hillarious. :-)

Andrei

I was thinking std.allocators.region.
Sep 07 2011
next sibling parent Robert Clipsham <robert octarineparrot.com> writes:
On 07/09/2011 15:10, dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 On 9/7/11 8:45 AM, Michel Fortin wrote:
 Every time I read std.regionallocator, I read "regional locator" and I
 find it hillarious. :-)

Andrei

I was thinking std.allocators.region.

+1 -- Robert http://octarineparrot.com/
Sep 07 2011
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2011-09-07 16:10, dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 On 9/7/11 8:45 AM, Michel Fortin wrote:
 Every time I read std.regionallocator, I read "regional locator" and I
 find it hillarious. :-)

Andrei

I was thinking std.allocators.region.

Same here. -- /Jacob Carlborg
Sep 07 2011
prev sibling parent dsimcha <dsimcha yahoo.com> writes:
On 9/7/2011 9:51 AM, Andrei Alexandrescu wrote:
 On 9/7/11 8:45 AM, Michel Fortin wrote:
 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.
Sep 10 2011
prev sibling next sibling parent reply travert phare.normalesup.org (Christophe) writes:
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.


-- 
Christophe Travert
Sep 07 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
Thanks for taking the time to do this review.  I appreciate the effort and the
constructive criticism.

== Quote from Christophe (travert phare.normalesup.org)'s article
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.

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.
 - 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.
 - 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.
 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.
 Important point:
 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.
 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.
Sep 07 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/07/2011 09:48 PM, dsimcha wrote:
 Thanks for taking the time to do this review.  I appreciate the effort and the
 constructive criticism.

 == Quote from Christophe (travert phare.normalesup.org)'s article
 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.
Sep 07 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Timon Gehr (timon.gehr gmx.ch)'s article
 On 09/07/2011 09:48 PM, dsimcha wrote:
 Thanks for taking the time to do this review.  I appreciate the effort and the
 constructive criticism.

 == Quote from Christophe (travert phare.normalesup.org)'s article
 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.]

(personally I would prefer 'New' though.)

Sounds good.
 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.

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.
 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.
Sep 07 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/07/2011 10:37 PM, dsimcha wrote:
 == Quote from Timon Gehr (timon.gehr gmx.ch)'s article
 On 09/07/2011 09:48 PM, dsimcha wrote:
 Thanks for taking the time to do this review.  I appreciate the effort and the
 constructive criticism.

 == Quote from Christophe (travert phare.normalesup.org)'s article
 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.]

(personally I would prefer 'New' though.)

Sounds good.
 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.

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?
 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?
Sep 07 2011
prev sibling parent reply travert phare.normalesup.org (Christophe) writes:
 Right.

OK, I'm glad I got the way RegionAllcator works right. dsimcha , dans le message (digitalmars.D:144124), a écrit :
 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.
 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.
 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.

;)
 - 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.
 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.
 Important point:
 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.

;)
 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. -- Christophe
Sep 07 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/07/2011 11:43 PM, Christophe wrote:
 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.

It is a brand new allocator which operates on an existing 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.

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.
Sep 07 2011
next sibling parent reply travert phare.normalesup.org (Christophe) writes:
Timon Gehr , dans le message (digitalmars.D:144133), a écrit :
 On 09/07/2011 11:43 PM, Christophe wrote:
 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.

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

it ? As is a copy of a File, etc.
 - 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.

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.
 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. -- Christophe
Sep 07 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/08/2011 01:09 AM, Christophe wrote:
 Timon Gehr , dans le message (digitalmars.D:144133), a écrit :
 On 09/07/2011 11:43 PM, Christophe wrote:
 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.

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

it ? As is a copy of a File, etc.
 - 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.

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.
 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.
 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.
 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.

 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.
 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.
Sep 07 2011
parent reply travert phare.normalesup.org (Christophe) writes:
Timon Gehr , dans le message (digitalmars.D:144140), a écrit :
 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.

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)".
 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.
 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.
 Creating a new RegionAlloc is not free. I don't want overhead for stuff 
 I don't need.

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.
 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().
Sep 07 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 9/8/2011 2:56 AM, Christophe wrote:
 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.
Sep 08 2011
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/08/2011 01:43 AM, Marco Leise wrote:
 Am 08.09.2011, 00:05 Uhr, schrieb Timon Gehr <timon.gehr gmx.ch>:

 On 09/07/2011 11:43 PM, Christophe wrote:
 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.

It is a brand new allocator which operates on an existing 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.

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.

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(); ;)
 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.
Sep 07 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, September 07, 2011 22:30:29 Timon Gehr wrote:
 On 09/07/2011 09:48 PM, dsimcha wrote:
 Thanks for taking the time to do this review.  I appreciate the effort
 and the constructive criticism.
 
 == Quote from Christophe (travert phare.normalesup.org)'s article
 
 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
Sep 07 2011
prev sibling next sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
Am 08.09.2011, 00:05 Uhr, schrieb Timon Gehr <timon.gehr gmx.ch>:

 On 09/07/2011 11:43 PM, Christophe wrote:
 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.

It is a brand new allocator which operates on an existing 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.

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.

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?
Sep 07 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/6/11 2:53 PM, Jonathan M Davis wrote:
 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

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
Sep 10 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/10/2011 5:07 PM, Andrei Alexandrescu wrote:
 On 9/6/11 2:53 PM, Jonathan M Davis wrote:
 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

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.
 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.
 * 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?
 * Use "bumped up" and "bumped down" or something instead of
 "incremented" and "decremented", which imply 1 as the unit.

Good point.
 * 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?
 * Synopsis should go before the textual intro.

Ok.
 * 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.
 * 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.
 * 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.
 * 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?
 * I think "scanThreadLocalStack" should be "threadLocalStackIsScannable"
 so as people don't confuse it with an action.

Sounds good.
 * 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.
 * 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.
 * 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.
 * I think alignBytes should be a compile-time computable property, and
 that the documentation should mention that.

Good point.
 * 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.
 Andrei

Sep 10 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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
Sep 10 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/11/2011 01:23 AM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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); }
Sep 10 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/10/2011 7:38 PM, Timon Gehr wrote:
 On 09/11/2011 01:23 AM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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

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.
Sep 10 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/11/2011 01:41 AM, dsimcha wrote:
 On 9/10/2011 7:38 PM, Timon Gehr wrote:
 On 09/11/2011 01:23 AM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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

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.

I think he meant auto new Array(T,A...)(A dims) if(NumDim!T==A.length);
Sep 10 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/11/2011 01:47 AM, Timon Gehr wrote:
 On 09/11/2011 01:41 AM, dsimcha wrote:
 On 9/10/2011 7:38 PM, Timon Gehr wrote:
 On 09/11/2011 01:23 AM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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

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.

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);
Sep 10 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/10/2011 7:48 PM, Timon Gehr wrote:
 On 09/11/2011 01:47 AM, Timon Gehr wrote:
 On 09/11/2011 01:41 AM, dsimcha wrote:
 On 9/10/2011 7:38 PM, Timon Gehr wrote:
 On 09/11/2011 01:23 AM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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

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.

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

No, that's roughly what I have now.
Sep 10 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/11/2011 01:51 AM, dsimcha wrote:
 On 9/10/2011 7:48 PM, Timon Gehr wrote:
 On 09/11/2011 01:47 AM, Timon Gehr wrote:
 On 09/11/2011 01:41 AM, dsimcha wrote:
 On 9/10/2011 7:38 PM, Timon Gehr wrote:
 On 09/11/2011 01:23 AM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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

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.

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

No, that's roughly what I have now.

Oh k. Then I don't understand what his remark was about.
Sep 10 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/10/11 6:48 PM, Timon Gehr wrote:
 On 09/11/2011 01:47 AM, Timon Gehr wrote:
 On 09/11/2011 01:41 AM, dsimcha wrote:
 On 9/10/2011 7:38 PM, Timon Gehr wrote:
 On 09/11/2011 01:23 AM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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

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.

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

No, T would be the element type. Andrei
Sep 10 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/10/11 6:41 PM, dsimcha wrote:
 On 9/10/2011 7:38 PM, Timon Gehr wrote:
 On 09/11/2011 01:23 AM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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

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

Instead: auto newArray(T, Args...)(Args dims) if (suitable_constraint); Andrei
Sep 10 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/10/11 6:23 PM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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
Sep 10 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
On 9/10/2011 8:03 PM, Andrei Alexandrescu wrote:
 On 9/10/11 6:23 PM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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.
Sep 10 2011
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 09/11/2011 02:03 AM, Andrei Alexandrescu wrote:
 On 9/10/11 6:23 PM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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);
Sep 10 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 09/11/2011 02:09 AM, Timon Gehr wrote:
 On 09/11/2011 02:03 AM, Andrei Alexandrescu wrote:
 On 9/10/11 6:23 PM, dsimcha wrote:
 On 9/10/2011 5:37 PM, dsimcha wrote:
 * 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

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

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.
Sep 10 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/10/11 4:37 PM, dsimcha wrote:
 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.
 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.
 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.
 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.
 * 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.
 * 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 ...)
 * 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.
 * 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)
 * 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
Sep 10 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
On 9/10/2011 8:26 PM, Andrei Alexandrescu wrote:
 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.
 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?
Sep 10 2011
prev sibling parent dsimcha <dsimcha yahoo.com> writes:
On 9/10/2011 8:26 PM, Andrei Alexandrescu wrote:
 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.
 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.

 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.
Sep 10 2011