• Jonathan M Davis (40/40) Sep 06 2011 Okay. Onto the next item in the review queue. I'm going to be the review...
• Vladimir Panteleev (9/10) Sep 06 2011 When the allocated region is not scanned by the GC (which is the default...
• Timon Gehr (3/10) Sep 06 2011 That is way too restrictive. Pointers do not always point to GC
• Vladimir Panteleev (10/23) Sep 06 2011 I'm not saying there shouldn't be a way to override it. Overriding this ...
• dsimcha (10/13) Sep 06 2011 The big red warning in the docs is do-able and probably a good idea.
• dsimcha (5/5) Sep 06 2011 BTW, forgot to mention it. This proposal also includes a gcallocator
• Alix Pexton (54/54) Sep 07 2011 1. The last part of the module description [lines 57-59 in the source]
• Alix Pexton (4/9) Sep 08 2011 Found it! 'twas just as I suspected, no idea how I missed it the first
• Michel Fortin (6/6) Sep 07 2011 Every time I read std.regionallocator, I read "regional locator" and I
• Andrei Alexandrescu (3/5) Sep 07 2011 Yes. That is part of my upcoming review. region_allocator please.
• dsimcha (2/7) Sep 07 2011 I was thinking std.allocators.region.
• Robert Clipsham (5/12) Sep 07 2011 +1
• Jacob Carlborg (4/11) Sep 07 2011 Same here.
• dsimcha (6/11) Sep 10 2011 I'm heavily anticipating your review, since I know your reviews tend to
• travert phare.normalesup.org (Christophe) (69/69) Sep 07 2011 I am not experienced in the d programming langage, so rather than
• dsimcha (37/99) Sep 07 2011 Thanks for taking the time to do this review. I appreciate the effort a...
• Timon Gehr (16/25) Sep 07 2011 'create' has been suggested and seems reasonable.
• dsimcha (8/35) Sep 07 2011 Hmm, I'll think about that. When it comes to the balance between making
• Timon Gehr (7/42) Sep 07 2011 The last allocated one is the array I append to in 80% or more of all
• Jonathan M Davis (3/19) Sep 07 2011 New breaks Phobos' naming conventions for functions. create does not.
• travert phare.normalesup.org (Christophe) (51/87) Sep 07 2011 Why catching other exceptions? This could apply to exceptions thrown by
• Timon Gehr (12/33) Sep 07 2011 Actually, I think the current semantics are a lot less confusing than
• travert phare.normalesup.org (Christophe) (48/89) Sep 07 2011 Well, then a simple copy of a RegionAllocator is also brand new, isn't
• Timon Gehr (28/115) Sep 07 2011 Basically, what you are trying to do is hiding the underlying reason for...
• travert phare.normalesup.org (Christophe) (49/68) Sep 07 2011 I prefer to see dangerously looking stuff in the code when one is
• dsimcha (4/11) Sep 08 2011 Again, the semantics of RegionAllocator and RegionAllocatorStack are
• Marco Leise (8/44) Sep 07 2011 alloc2 = alloc1.exclusiveCopy();
• Timon Gehr (9/59) Sep 07 2011 speaking name: RegionAllocator*Stack*
• Andrei Alexandrescu (44/55) Sep 10 2011 Unfortunately my review is incomplete because I don't see the allocator
• dsimcha (68/131) Sep 10 2011 I mostly took your proposal from a few months ago and doctored it
• dsimcha (4/10) Sep 10 2011 Ok, now I remember. It was so that if you give too many dimensions,
• Timon Gehr (11/22) Sep 10 2011 It is possible to determine the number of dimensions automatically
• dsimcha (5/30) Sep 10 2011 IIUC you misunderstood. I think Andrei was suggesting the following
• Timon Gehr (3/36) Sep 10 2011 I think he meant
• Timon Gehr (3/43) Sep 10 2011 sry:
• dsimcha (2/48) Sep 10 2011 No, that's roughly what I have now.
• Timon Gehr (2/54) Sep 10 2011 Oh k. Then I don't understand what his remark was about.
• Andrei Alexandrescu (3/49) Sep 10 2011 No, T would be the element type.
• Andrei Alexandrescu (4/36) Sep 10 2011 Instead:
• Andrei Alexandrescu (7/18) Sep 10 2011 If you just require
• dsimcha (7/28) Sep 10 2011 Yeah, but I prefer (admittedly subjective) the way I have. It's
• Timon Gehr (6/27) Sep 10 2011 The current interface allows to only initialize the first 1 to
• Timon Gehr (4/36) Sep 10 2011 Well, your proposal does too:
• Andrei Alexandrescu (30/87) Sep 10 2011 Yes.
• dsimcha (7/14) Sep 10 2011 Ok, well then I'll get busy creating a more formal description of the
• dsimcha (10/30) Sep 10 2011 Another issue is that templated methods (e.g. newArray) can't be virtual...

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

"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

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.

"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

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.

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.

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

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

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/

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

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

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

I was thinking std.allocators.region.

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

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

 I was thinking std.allocators.region.

+1

-- 
Robert
http://octarineparrot.com/

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

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

 I was thinking std.allocators.region.

Same here.

-- 
/Jacob Carlborg

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.

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

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.

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.

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

 'create' has been suggested and seems reasonable.
 (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.

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

 'create' has been suggested and seems reasonable.
 (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?

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

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

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.

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.

Well, then a simple copy of a RegionAllocator is also brand new, isn't 
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

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.

 Well, then a simple copy of a RegionAllocator is also brand new, isn't
 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.

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.

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

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

Ok, that's a point.

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

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

"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?

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.

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

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

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

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

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.

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

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

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.

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.

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

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

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

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.

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

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.

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

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?

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.