www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Vote on region allocator

reply Jonathan M Davis <jmdavisProg gmx.com> writes:
Okay, David Simcha wrote some modules intended to form the basis for custom 
allocators in D, and that code has been reviewed in the "Formal Review of 
region allacator begins" thread. The review period has passed, and it's time 
to vote on whether we want to include it in Phobos as-is or not.

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

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

A yes vote means that we will be creating a new std.allocators module in 
Phobos and adding dsimcha's allocater, gc, and region modules to it (which 
provide the general custom allocator stuff, a custom allocator using the GC, 
and a custom allocator using a segmented stack respectively).

A no vote means that we will not be including them at this time, and they will 
need to go through further revision and review if they are ever to be 
included.

Please refrain from discussions in this thread. This thread is intended for 
voting only. Anyone can vote.

The voting will last for approximately one week and will end on Saturday, 
October 1st at midnight in UTC (2011-10-01T00:00:00Z).

- Jonathan M Davis
Sep 23 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
BTW, since the latest revision didn't get much review, I recommend we allow
"conditional yes" votes.  If you find some small issue that you think really
needs
fixing, I think it's perfectly reasonable to say something like "yes, but please
fix X.".

== Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article
 Okay, David Simcha wrote some modules intended to form the basis for custom
 allocators in D, and that code has been reviewed in the "Formal Review of
 region allacator begins" thread. The review period has passed, and it's time
 to vote on whether we want to include it in Phobos as-is or not.
 Code:
 https://github.com/dsimcha/TempAlloc/tree/master/std/allocators
 Docs:
 http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_allocator.html
 http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_gc.html
 http://cis.jhu.edu/~dsimcha/d/phobos/std_allocators_region.html
 A yes vote means that we will be creating a new std.allocators module in
 Phobos and adding dsimcha's allocater, gc, and region modules to it (which
 provide the general custom allocator stuff, a custom allocator using the GC,
 and a custom allocator using a segmented stack respectively).
 A no vote means that we will not be including them at this time, and they will
 need to go through further revision and review if they are ever to be
 included.
 Please refrain from discussions in this thread. This thread is intended for
 voting only. Anyone can vote.
 The voting will last for approximately one week and will end on Saturday,
 October 1st at midnight in UTC (2011-10-01T00:00:00Z).
 - Jonathan M Davis

Sep 23 2011
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, September 23, 2011 14:13 dsimcha wrote:
 BTW, since the latest revision didn't get much review, I recommend we allow
 "conditional yes" votes. If you find some small issue that you think
 really needs fixing, I think it's perfectly reasonable to say something
 like "yes, but please fix X.".

I'm fine with that, but major changes will likely require that the code actually be reviewed again, and we don't want major discussions in this thread, since this is the voting thread. - Jonathan M Davis
Sep 23 2011
prev sibling next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
I already added a comment on github (sorrowly allows comments only on  
diffs).
Bugs should be fixed whenever they are know and should only be a concern  
for
voting if there is a gross number of them, i.e. it's code and for sure it  
contains bugs.

martin

On Fri, 23 Sep 2011 23:36:09 +0200, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Friday, September 23, 2011 14:13 dsimcha wrote:
 BTW, since the latest revision didn't get much review, I recommend we  
 allow
 "conditional yes" votes. If you find some small issue that you think
 really needs fixing, I think it's perfectly reasonable to say something
 like "yes, but please fix X.".

I'm fine with that, but major changes will likely require that the code actually be reviewed again, and we don't want major discussions in this thread, since this is the voting thread. - Jonathan M Davis

Sep 23 2011
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, September 23, 2011 16:02 Martin Nowak wrote:
 I already added a comment on github (sorrowly allows comments only on
 diffs).
 Bugs should be fixed whenever they are know and should only be a concern
 for
 voting if there is a gross number of them, i.e. it's code and for sure it
 contains bugs.

The real concern is API issues. Bugs in the code can be fixed, and unless they are serious issues with the implementation that make it so that it shouldn't go into Phobos, then they're not really the issue. But if the API isn't solid, it's a _much_ bigger deal to change it. The implementation is definitely part of what has been (and should be) reviewed, but the API is the most important part. - Jonathan M Davis
Sep 23 2011
parent deadalnix <deadalnix gmail.com> writes:
Le 24/09/2011 01:14, Jonathan M Davis a écrit :
 On Friday, September 23, 2011 16:02 Martin Nowak wrote:
 I already added a comment on github (sorrowly allows comments only on
 diffs).
 Bugs should be fixed whenever they are know and should only be a concern
 for
 voting if there is a gross number of them, i.e. it's code and for sure it
 contains bugs.

The real concern is API issues. Bugs in the code can be fixed, and unless they are serious issues with the implementation that make it so that it shouldn't go into Phobos, then they're not really the issue. But if the API isn't solid, it's a _much_ bigger deal to change it. The implementation is definitely part of what has been (and should be) reviewed, but the API is the most important part. - Jonathan M Davis

The API has some incoherencies, in naming convention for exemple. freeIsChecked for exemple, sounds incoherent to me with isAutomatic and isScoped. In addition, fixing bug is nice, but including something in the standards lib with known bugs is quite scary. Just immaging the poor beginner in D wondering why his code isn't working as expected - note that it happend to me when I begun D and had a bogus compiler, I almost gave up the laguage on that event. Inclusion in the standard lib should be made with no known bug IMO.
Sep 25 2011
prev sibling next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis <jmdavisProg gmx.com>
wrote:

No. I cannot build an efficient and safe appender on this API.
Sep 23 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet. The allocate() fix with block attributes, however, is not because: 1. You can just call addRegion/removeRegion yourself after allocating, so it just adds bloat. 2. A major purpose of RegionAllocator and probably several other allocators is to avoid the GC lock. I don't want anything that could lock to be implicit unless the only alternative is failure.
Sep 23 2011
next sibling parent dsimcha <dsimcha yahoo.com> writes:
On 9/23/2011 11:51 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 23:30:34 -0400, dsimcha <dsimcha yahoo.com> wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet. The allocate() fix with block attributes, however, is not because: 1. You can just call addRegion/removeRegion yourself after allocating, so it just adds bloat. 2. A major purpose of RegionAllocator and probably several other allocators is to avoid the GC lock. I don't want anything that could lock to be implicit unless the only alternative is failure.

A) If the allocator is the GC, then I've just taken the GC lock twice. B) If the allocator is stack like, then I might not necessarily need to use addRegion, at least for some internal structures. C) If region allocator, for example, maintained a second, GC-region segmented stack, then I can have GC tracing without taking the GC lock. In terms of attributes, you might generalize this to: NO_SCAN // I had no pointers REGION_SCAN // I have pointers internal to the region GC_SCAN // I have pointers to general memory D) There's performance gains in knowing that REGION_SCAN is equivalent to NO_SCAN or GC_SCAN

You make an interesting point. One concern, though, is e.g. RegionAllocator, where scan vs. no scan has to be set on creation. I don't want to force this to be specified again on allocation, and then have to throw an exception or something if it doesn't match.
Sep 23 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/23/11 22:30 CDT, dsimcha wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet.

Then we might be hasty to vote this in. Ideally Phobos should be integrating tried and true APIs. I wish we voted allocator in once it's used throughout std.container to great effect. Andrei
Sep 23 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/24/11 1:19 CDT, Jonathan M Davis wrote:
 On Saturday, September 24, 2011 01:10:44 Andrei Alexandrescu wrote:
 On 9/23/11 22:30 CDT, dsimcha wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com>  wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet.

Then we might be hasty to vote this in. Ideally Phobos should be integrating tried and true APIs. I wish we voted allocator in once it's used throughout std.container to great effect.

So, do you think that we should cease the vote then?

At the risk of annoying David and others, allow me to vote against inclusion of the current proposal. There are three main reasons: 1. The proposal has been changed mid-review. 2. There are hints of further changes post-review. 3. Only the scoped allocator has been used, but not the others. These threes are basis enough for a negative vote. That being said, this is excellent progress towards solving a very difficult problem. Below are some more thoughts about steps that could be taken to improve the design and its implementation. Fundamentally we want to make sure we cover the following allocators: 1. Classic malloc/realloc/free, unsafe 2. Scoped allocators of various flavors (simple/expanding/etc.) 3. Full-fledged garbage collectors, conservative and not 4. Stacked combinations (e.g. freelist over region over malloc etc.) (5. It would be awesome if we could somehow catch allocators that use reference counting, or at least not prevent their definition. I'm just mentioning this because it's been buzzing in my mind forever, but any design I can think of is fraught with issues.) Of these, the garbage-collected allocators need type information about the data, so we can only assume that any allocator needs it. There is some design in that direction, but it lacks the dynamic component. Generally the relationship between the structural/static interface and the dynamic interface is tenuous (when should one use one vs. the other? how does one pass type information about an allocation through the dynamic interface?) Currently the low-level interface traffics in void* (not even void[] or ubyte[] which may be better) and does not offer any way to e.g. set the type of a chunk after it's been allocated. This makes e.g. a precise garbage collector difficult to integrate (and impossible with the dynamic interface). I think the interface should offer a bool freeAll() that frees all memory allocated by the given allocator. That would only work with scoped allocators and would return false for the others. Speaking of which, there's no property that says "free() is inoperant", which is the case for certain region-based allocators. Finally, it would be great if some validation was available. There's no use of the dynamic interface with e.g. containers, which would have readily revealed e.g. the fact that a container can't pass type information to the allocator through the dynamic interface. We should also have some more examples of stacked allocators, e.g. that use free lists on top of regions etc. The current static design seems to be almost adequate. The way I see this all working is that allocators define the static interface for maximum performance and are stackable in infinite ways. Once the user decides on a stacking configuration, they simply wrap the entire stack in the dynamic interface and use that with e.g. a container. Thanks, Andrei
Sep 24 2011
parent dsimcha <dsimcha yahoo.com> writes:
On 9/24/2011 3:08 AM, Andrei Alexandrescu wrote:
 On 9/24/11 1:19 CDT, Jonathan M Davis wrote:
 On Saturday, September 24, 2011 01:10:44 Andrei Alexandrescu wrote:
 On 9/23/11 22:30 CDT, dsimcha wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet.

Then we might be hasty to vote this in. Ideally Phobos should be integrating tried and true APIs. I wish we voted allocator in once it's used throughout std.container to great effect.

So, do you think that we should cease the vote then?

At the risk of annoying David and others, allow me to vote against inclusion of the current proposal. There are three main reasons: 1. The proposal has been changed mid-review.

It was changed mid-review in response to some legitimate criticism. I thought this is the way the review process is supposed to work.
 2. There are hints of further changes post-review.

Agreed.
 3. Only the scoped allocator has been used, but not the others.

Agreed, though to play Devil's Advocate this does create a chicken-and-egg problem. If these allocators are buried somewhere in my Github page, probably noone except me and my GSoC mentees are going to use them.
 These threes are basis enough for a negative vote. That being said, this
 is excellent progress towards solving a very difficult problem.

 Below are some more thoughts about steps that could be taken to improve
 the design and its implementation.

 Fundamentally we want to make sure we cover the following allocators:

Agreed, eventually. I just thought that this proposal would be enough to get the ball rolling and that this stuff would all be added later.
 Of these, the garbage-collected allocators need type information about
 the data, so we can only assume that any allocator needs it. There is
 some design in that direction, but it lacks the dynamic component.
 Generally the relationship between the structural/static interface and
 the dynamic interface is tenuous (when should one use one vs. the other?
 how does one pass type information about an allocation through the
 dynamic interface?)

Yeah, the dynamic interface was something proposed and added mid-review. This was really my first shot at it. You're right, it had not been reviewed or used at all.
 Currently the low-level interface traffics in void* (not even void[] or
 ubyte[] which may be better) and does not offer any way to e.g. set the
 type of a chunk after it's been allocated. This makes e.g. a precise
 garbage collector difficult to integrate (and impossible with the
 dynamic interface).

I stuck with void* because that's what core.memory uses.
 I think the interface should offer a bool freeAll() that frees all
 memory allocated by the given allocator. That would only work with
 scoped allocators and would return false for the others. Speaking of
 which, there's no property that says "free() is inoperant", which is the
 case for certain region-based allocators.

Good ideas.
 Finally, it would be great if some validation was available. There's no
 use of the dynamic interface with e.g. containers, which would have
 readily revealed e.g. the fact that a container can't pass type
 information to the allocator through the dynamic interface.

I guess using RTTI would be the solution here?
 We should also have some more examples of stacked allocators, e.g. that
 use free lists on top of regions etc. The current static design seems to
 be almost adequate. The way I see this all working is that allocators
 define the static interface for maximum performance and are stackable in
 infinite ways. Once the user decides on a stacking configuration, they
 simply wrap the entire stack in the dynamic interface and use that with
 e.g. a container.

I disagree slightly. Again, getting these in Phobos eventually is a worthy goal, but I'd rather just get the ball rolling first. I don't have time to write all these anytime soon, I haven't heard anyone else volunteer, and I think a single proposal with all of these would be overwhelming.
Sep 24 2011
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/24/2011 2:10 AM, Andrei Alexandrescu wrote:
 On 9/23/11 22:30 CDT, dsimcha wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet.

Then we might be hasty to vote this in. Ideally Phobos should be integrating tried and true APIs. I wish we voted allocator in once it's used throughout std.container to great effect. Andrei

I see your point, but at the same time this does create a chicken-and-egg problem. The use case that inspired me to work on allocators is much simpler: Allocating simple temporary objects in performance-critical functions. I don't have any plans to do containers and I don't know of anyone else who does in the short term. Is there a way to avoid waiting indefinitely to get allocators into Phobos?
Sep 24 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/24/11 9:33 AM, dsimcha wrote:
 On 9/24/2011 2:10 AM, Andrei Alexandrescu wrote:
 On 9/23/11 22:30 CDT, dsimcha wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet.

Then we might be hasty to vote this in. Ideally Phobos should be integrating tried and true APIs. I wish we voted allocator in once it's used throughout std.container to great effect. Andrei

I see your point, but at the same time this does create a chicken-and-egg problem. The use case that inspired me to work on allocators is much simpler: Allocating simple temporary objects in performance-critical functions. I don't have any plans to do containers and I don't know of anyone else who does in the short term. Is there a way to avoid waiting indefinitely to get allocators into Phobos?

I plan to work on containers, and part of the work is to integrate allocators. There are two basic paths from here. One is to make the allocator a template parameter a la STL. The other is to define a dynamic allocator interface and use it. Making the allocator a part of the container type would go the STL way, and STL allocators are essentially a failed experiment. I'm only partially clear on why it has failed, but it does seem that part of the reason was making the allocator a template parameter. Defining and using an allocator interface would have a small speed impact (i.e. allocation would entail an indirect call) but I think that would be acceptable. Andrei
Sep 24 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/24/2011 7:55 PM, Andrei Alexandrescu wrote:
 Defining and using an allocator interface would have a small speed
 impact (i.e. allocation would entail an indirect call) but I think that
 would be acceptable.

Agreed. My much bigger concern w.r.t. dynamic interfaces is their inflexibility, i.e. that they can't be used effectively with template metaprogramming.
Sep 24 2011
next sibling parent "dame" <damesureurnotme yousuck.gov> writes:
dsimcha wrote:
 On 9/24/2011 7:55 PM, Andrei Alexandrescu wrote:
 Defining and using an allocator interface would have a small speed
 impact (i.e. allocation would entail an indirect call) but I think
 that would be acceptable.

Agreed.

Suck his dick, bitch.
Sep 24 2011
prev sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 25/09/11 1:20 AM, dsimcha wrote:
 On 9/24/2011 7:55 PM, Andrei Alexandrescu wrote:
 Defining and using an allocator interface would have a small speed
 impact (i.e. allocation would entail an indirect call) but I think that
 would be acceptable.

Agreed. My much bigger concern w.r.t. dynamic interfaces is their inflexibility, i.e. that they can't be used effectively with template metaprogramming.

In what way would you want to meta-program with allocators?
Sep 25 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/25/2011 4:40 PM, Peter Alexander wrote:
 On 25/09/11 1:20 AM, dsimcha wrote:
 On 9/24/2011 7:55 PM, Andrei Alexandrescu wrote:
 Defining and using an allocator interface would have a small speed
 impact (i.e. allocation would entail an indirect call) but I think that
 would be acceptable.

Agreed. My much bigger concern w.r.t. dynamic interfaces is their inflexibility, i.e. that they can't be used effectively with template metaprogramming.

In what way would you want to meta-program with allocators?

Allocating arrays, etc.
Sep 25 2011
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 25/09/11 10:57 PM, dsimcha wrote:
 On 9/25/2011 4:40 PM, Peter Alexander wrote:
 On 25/09/11 1:20 AM, dsimcha wrote:
 On 9/24/2011 7:55 PM, Andrei Alexandrescu wrote:
 Defining and using an allocator interface would have a small speed
 impact (i.e. allocation would entail an indirect call) but I think that
 would be acceptable.

Agreed. My much bigger concern w.r.t. dynamic interfaces is their inflexibility, i.e. that they can't be used effectively with template metaprogramming.

In what way would you want to meta-program with allocators?

Allocating arrays, etc.

I'm not following. Can you give an example of something that wouldn't work if we had dynamic interfaces instead of templated ones?
Sep 25 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 9/25/2011 6:24 PM, Peter Alexander wrote:
 On 25/09/11 10:57 PM, dsimcha wrote:
 On 9/25/2011 4:40 PM, Peter Alexander wrote:
 On 25/09/11 1:20 AM, dsimcha wrote:
 On 9/24/2011 7:55 PM, Andrei Alexandrescu wrote:
 Defining and using an allocator interface would have a small speed
 impact (i.e. allocation would entail an indirect call) but I think
 that
 would be acceptable.

Agreed. My much bigger concern w.r.t. dynamic interfaces is their inflexibility, i.e. that they can't be used effectively with template metaprogramming.

In what way would you want to meta-program with allocators?

Allocating arrays, etc.

I'm not following. Can you give an example of something that wouldn't work if we had dynamic interfaces instead of templated ones?

T newArray(T, I...)(I sizes); // Usage: auto foo = newArray!(uint[])(5); This would be marginally do-able but very ugly if RTTI were used.
Sep 25 2011
next sibling parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"dsimcha" <dsimcha yahoo.com> wrote in message 
news:j5otvn$2qg1$1 digitalmars.com...
 T newArray(T, I...)(I sizes);

 // Usage:
 auto foo = newArray!(uint[])(5);

 This would be marginally do-able but very ugly if RTTI were used.

You can do this with a final templated interface method and forward to the ugly rtti method. Well, you will be able to when https://github.com/D-Programming-Language/dmd/pull/131 gets merged.
Sep 25 2011
prev sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 26/09/11 5:10 AM, dsimcha wrote:
 On 9/25/2011 6:24 PM, Peter Alexander wrote:
 On 25/09/11 10:57 PM, dsimcha wrote:
 On 9/25/2011 4:40 PM, Peter Alexander wrote:
 On 25/09/11 1:20 AM, dsimcha wrote:
 On 9/24/2011 7:55 PM, Andrei Alexandrescu wrote:
 Defining and using an allocator interface would have a small speed
 impact (i.e. allocation would entail an indirect call) but I think
 that
 would be acceptable.

Agreed. My much bigger concern w.r.t. dynamic interfaces is their inflexibility, i.e. that they can't be used effectively with template metaprogramming.

In what way would you want to meta-program with allocators?

Allocating arrays, etc.

I'm not following. Can you give an example of something that wouldn't work if we had dynamic interfaces instead of templated ones?

T newArray(T, I...)(I sizes); // Usage: auto foo = newArray!(uint[])(5); This would be marginally do-able but very ugly if RTTI were used.

Ok, now I'm really lost. Where do allocators come into that?
Sep 26 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Peter Alexander (peter.alexander.au gmail.com)'s article
 T newArray(T, I...)(I sizes);

 // Usage:
 auto foo = newArray!(uint[])(5);

 This would be marginally do-able but very ugly if RTTI were used.


I'm sorry. To clarify: SomeAllocator alloc; auto foo = alloc.newArray!(uint[])(5); The only way to do this with dynamic allocators would be a final templated function wrapping a function that takes RTTI. This would be marginally do-able but very ugly.
Sep 26 2011
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 26/09/11 7:46 PM, dsimcha wrote:
 == Quote from Peter Alexander (peter.alexander.au gmail.com)'s article
 T newArray(T, I...)(I sizes);

 // Usage:
 auto foo = newArray!(uint[])(5);

 This would be marginally do-able but very ugly if RTTI were used.


I'm sorry. To clarify: SomeAllocator alloc; auto foo = alloc.newArray!(uint[])(5); The only way to do this with dynamic allocators would be a final templated function wrapping a function that takes RTTI. This would be marginally do-able but very ugly.

Why on Earth would an allocator have a newArray method? Allocators allocate bytes, they don't construct objects. newArray should take an allocator: // Template version T newArray(A, T, I...)(A allocator, I...); // Dynamic version T newArray(T, I...)(IAllocator allocator, I...); newArray then requests: allocator.allocate( /+ bytes +/, /+ align (optional) +/ ); And constructs the array in those bytes.
Sep 26 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Peter Alexander (peter.alexander.au gmail.com)'s article
 On 26/09/11 7:46 PM, dsimcha wrote:
 == Quote from Peter Alexander (peter.alexander.au gmail.com)'s article
 T newArray(T, I...)(I sizes);

 // Usage:
 auto foo = newArray!(uint[])(5);

 This would be marginally do-able but very ugly if RTTI were used.


I'm sorry. To clarify: SomeAllocator alloc; auto foo = alloc.newArray!(uint[])(5); The only way to do this with dynamic allocators would be a final templated function wrapping a function that takes RTTI. This would be marginally do-able but very ugly.

Allocators allocate bytes, they don't construct objects. newArray should take an allocator: // Template version T newArray(A, T, I...)(A allocator, I...); // Dynamic version T newArray(T, I...)(IAllocator allocator, I...); newArray then requests: allocator.allocate( /+ bytes +/, /+ align (optional) +/ ); And constructs the array in those bytes.

This was previously discussed in the review. The problem is that the allocator may have a use for the type information, e.g. setting GC flags, etc.
Sep 26 2011
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 26/09/11 8:25 PM, dsimcha wrote:
 == Quote from Peter Alexander (peter.alexander.au gmail.com)'s article
 On 26/09/11 7:46 PM, dsimcha wrote:
 == Quote from Peter Alexander (peter.alexander.au gmail.com)'s article
 T newArray(T, I...)(I sizes);

 // Usage:
 auto foo = newArray!(uint[])(5);

 This would be marginally do-able but very ugly if RTTI were used.


I'm sorry. To clarify: SomeAllocator alloc; auto foo = alloc.newArray!(uint[])(5); The only way to do this with dynamic allocators would be a final templated function wrapping a function that takes RTTI. This would be marginally do-able but very ugly.

Allocators allocate bytes, they don't construct objects. newArray should take an allocator: // Template version T newArray(A, T, I...)(A allocator, I...); // Dynamic version T newArray(T, I...)(IAllocator allocator, I...); newArray then requests: allocator.allocate( /+ bytes +/, /+ align (optional) +/ ); And constructs the array in those bytes.

This was previously discussed in the review. The problem is that the allocator may have a use for the type information, e.g. setting GC flags, etc.

In that case it should just pass that information to the allocator as well. The interface should be minimal and only request the information that it needs, no more.
Sep 27 2011
prev sibling next sibling parent "dame" <damesureurnotme yousuck.gov> writes:
Andrei Alexandrescu wrote:

 I plan to work on containers,

"I plan".. "I plan to work on".... You're not a very good planner though, huh. Or do indulge and show me that you are (rhetorical). Forget what I said. What do you wish? Distinctly different (note the emphasis), ... (I forgot the thought while writing the parenthetical thought). A plan, is a plan, is a plan, is a plan. Might I interest anyone in my own personal "plan"? Well you know I'm going to tell you anyway, so just change the channel if you hate me. Is "plan" a word? (I need a drink, brb). Ok, I'm back. I think I know your plan. I am drinking heavily these days because you plan eclipsed my plan. I, of course, am ready to... "Even .... ha! how to frame that one! "Even I" can't.... "Even" I can't... WTF, you are programmers. WTF, aren't you? "There are two basic paths from here." "There is a fork in the road". Over used by Johnny Carson for decades. ("bless him", I was about to type "bless his soul")
  One is to make the allocator

I don't think you are sure about that. Did One do that? Or are you just here?
  a
 template parameter

Or do just hope to fullfill some kind of "template parameter"?
  a la STL.

It's Ok, it's all the same "god".
 The other is to define

You sound really "definitive".
 a dynamic

Buzz word.
 allocator interface and use it.

Make me. I don't dare you.
 Making the allocator a part of the container type would go the STL
 way,

Didn't evangelists like that go out in the 50's?
  and STL allocators are essentially a failed experiment.

But your snake oil is best.
 I'm only

I assure you that.
 partially clear on why it has failed,

As if anyone actually gives a shit what you are spouting about?
 but it does seem

To you, or those you try to hypnotize? Hmm?
  that part of
 the reason was making the allocator a template parameter.

There is no evidence of your ability to reason.
 Defining

You wish you could define anything.
 and using an allocator interface would have a small speed
 impact (i.e. allocation would entail an indirect call) but I think
 that would be acceptable.

Who cares what you think?
Sep 24 2011
prev sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 25/09/11 12:55 AM, Andrei Alexandrescu wrote:
 On 9/24/11 9:33 AM, dsimcha wrote:
 On 9/24/2011 2:10 AM, Andrei Alexandrescu wrote:
 On 9/23/11 22:30 CDT, dsimcha wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet.

Then we might be hasty to vote this in. Ideally Phobos should be integrating tried and true APIs. I wish we voted allocator in once it's used throughout std.container to great effect. Andrei

I see your point, but at the same time this does create a chicken-and-egg problem. The use case that inspired me to work on allocators is much simpler: Allocating simple temporary objects in performance-critical functions. I don't have any plans to do containers and I don't know of anyone else who does in the short term. Is there a way to avoid waiting indefinitely to get allocators into Phobos?

I plan to work on containers, and part of the work is to integrate allocators. There are two basic paths from here. One is to make the allocator a template parameter a la STL. The other is to define a dynamic allocator interface and use it. Making the allocator a part of the container type would go the STL way, and STL allocators are essentially a failed experiment. I'm only partially clear on why it has failed, but it does seem that part of the reason was making the allocator a template parameter. Defining and using an allocator interface would have a small speed impact (i.e. allocation would entail an indirect call) but I think that would be acceptable. Andrei

I would like to say something here as someone that uses allocators in C++ every single day at my day job: STL allocators are useless and no one uses them in the way they were intended. Everyone I know defines a runtime polymorphic allocator that is used by all containers and then derives from that to implement different allocators. The problems with STL allocators are listed here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html#std_allocator It's a document by a large game developer, but none of the allocator complaints are specific to game development. Many of the same concerns are raised here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1850.pdf Also note that even though we obviously care a lot about performance, we're fine with the cost of the virtual call on allocation. If you care about performance then you shouldn't be allocating often in the first place. We'd care a lot more about the code bloat caused by instantiating different templates for each different allocator we use. In short, I believe that templating containers on their allocator would be a very poor decision. It was tried in STL and it failed miserably. Let's learn from its mistake.
Sep 25 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 23 Sep 2011 23:30:34 -0400, dsimcha <dsimcha yahoo.com> wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet. The allocate() fix with block attributes, however, is not because: 1. You can just call addRegion/removeRegion yourself after allocating, so it just adds bloat. 2. A major purpose of RegionAllocator and probably several other allocators is to avoid the GC lock. I don't want anything that could lock to be implicit unless the only alternative is failure.

A) If the allocator is the GC, then I've just taken the GC lock twice. B) If the allocator is stack like, then I might not necessarily need to use addRegion, at least for some internal structures. C) If region allocator, for example, maintained a second, GC-region segmented stack, then I can have GC tracing without taking the GC lock. In terms of attributes, you might generalize this to: NO_SCAN // I had no pointers REGION_SCAN // I have pointers internal to the region GC_SCAN // I have pointers to general memory D) There's performance gains in knowing that REGION_SCAN is equivalent to NO_SCAN or GC_SCAN
Sep 23 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sat, 24 Sep 2011 00:09:41 -0400, dsimcha <dsimcha yahoo.com> wrote:

 On 9/23/2011 11:51 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 23:30:34 -0400, dsimcha <dsimcha yahoo.com> wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:

 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet. The allocate() fix with block attributes, however, is not because: 1. You can just call addRegion/removeRegion yourself after allocating, so it just adds bloat. 2. A major purpose of RegionAllocator and probably several other allocators is to avoid the GC lock. I don't want anything that could lock to be implicit unless the only alternative is failure.

A) If the allocator is the GC, then I've just taken the GC lock twice. B) If the allocator is stack like, then I might not necessarily need to use addRegion, at least for some internal structures. C) If region allocator, for example, maintained a second, GC-region segmented stack, then I can have GC tracing without taking the GC lock. In terms of attributes, you might generalize this to: NO_SCAN // I had no pointers REGION_SCAN // I have pointers internal to the region GC_SCAN // I have pointers to general memory D) There's performance gains in knowing that REGION_SCAN is equivalent to NO_SCAN or GC_SCAN

You make an interesting point. One concern, though, is e.g. RegionAllocator, where scan vs. no scan has to be set on creation. I don't want to force this to be specified again on allocation, and then have to throw an exception or something if it doesn't match.

Well, that was why I suggested that the allocator type be passed into free/resize as well. So all you have to do if a RegionAllocator is NO_SCAN, is to add/remove a GC region, on allocate(nBytes, GC_SCAN)/resize(...,GC_SCAN)/free(...,GC_SCAN). I think it's safe to say that calling allocate(nBytes,NO_SCAN) and a GC_SCAN region allocator, can be considered a no-op. Also, you could add a DEFAULT_SCAN to the attributes.
Sep 23 2011
prev sibling next sibling parent Jakob Ovrum <jakobovrum+ng gmail.com> writes:
No, this needs more time for review of the current iteration.
Sep 23 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, September 24, 2011 01:10:44 Andrei Alexandrescu wrote:
 On 9/23/11 22:30 CDT, dsimcha wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:
 
 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet.

Then we might be hasty to vote this in. Ideally Phobos should be integrating tried and true APIs. I wish we voted allocator in once it's used throughout std.container to great effect.

So, do you think that we should cease the vote then? Personally, I'm not convinced that it's ready given the review thread, but I haven't looked at the API or code in great detail yet either. If we really don't think that this is ready for being voted on, then we shouldn't vote on it. It's better to put it off and let it bake a bit more than vote in a partially baked API. - Jonathan M Davis
Sep 23 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, September 24, 2011 11:06:59 dsimcha wrote:
 On 9/24/2011 3:08 AM, Andrei Alexandrescu wrote:
 On 9/24/11 1:19 CDT, Jonathan M Davis wrote:
 On Saturday, September 24, 2011 01:10:44 Andrei Alexandrescu wrote:
 On 9/23/11 22:30 CDT, dsimcha wrote:
 On 9/23/2011 11:25 PM, Robert Jacques wrote:
 On Fri, 23 Sep 2011 15:53:46 -0400, Jonathan M Davis
 <jmdavisProg gmx.com> wrote:
 
 No. I cannot build an efficient and safe appender on this API.

The resize() fix you requested is going to get implemented. I just haven't actually added it yet.

Then we might be hasty to vote this in. Ideally Phobos should be integrating tried and true APIs. I wish we voted allocator in once it's used throughout std.container to great effect.

So, do you think that we should cease the vote then?

At the risk of annoying David and others, allow me to vote against inclusion of the current proposal. There are three main reasons: 1. The proposal has been changed mid-review.

It was changed mid-review in response to some legitimate criticism. I thought this is the way the review process is supposed to work.

It is. std.datetime changed quite a bit over the course of its review process. However, there were major changes not long before the end of the review process, and they have not been thoroughly reviewed. Minor changes near the end are one thing, but in this case, a whole new module was created. Changes can and will occur through the review process, but those changes need to be reviewed as well. - Jonathan M Davis
Sep 24 2011
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
On Sep 24, 2011, at 4:55 PM, Andrei Alexandrescu wrote:
=20
 Making the allocator a part of the container type would go the STL =

partially clear on why it has failed, but it does seem that part of the = reason was making the allocator a template parameter. I think the STL allocators were perhaps a bit overly ambitious, and the = resulting complexity ended up in the wrong areas. For example, because = the allocator defines all types related to the allocated data--pointers = to the data, etc--it seems entirely feasible to make an allocator = fronting some utterly bizarre dynamic storage method, like a database. = The thing is that no one actually ended up caring about this, while at = the same time the complexity of the allocator design made it difficult = and confusing to use. Which I believe is why we don't see many STL-like = containers in the wild. All this is pure conjecture of course, but = having implemented unordered_map/set from C++0x I can say with = confidence that the allocator requirements were the most complicated = part of the process. If anyone is interested, I can provide the code.=
Sep 25 2011
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
No.  If this were just a scoped allocator, that would be fine, but a =
general purpose allocator interface needs more discussion.=
Sep 25 2011
prev sibling next sibling parent Jesse Phillips <jessekphillips+d gmail.com> writes:
No.

Purely because there is a need to continue the review process as evident 
by the discussions.

I have no criticism of my own.
Sep 27 2011
prev sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 23/09/11 8:53 PM, Jonathan M Davis wrote:
 Okay, David Simcha wrote some modules intended to form the basis for custom
 allocators in D, and that code has been reviewed in the "Formal Review of
 region allacator begins" thread. The review period has passed, and it's time
 to vote on whether we want to include it in Phobos as-is or not.

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

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

 A yes vote means that we will be creating a new std.allocators module in
 Phobos and adding dsimcha's allocater, gc, and region modules to it (which
 provide the general custom allocator stuff, a custom allocator using the GC,
 and a custom allocator using a segmented stack respectively).

 A no vote means that we will not be including them at this time, and they will
 need to go through further revision and review if they are ever to be
 included.

 Please refrain from discussions in this thread. This thread is intended for
 voting only. Anyone can vote.

 The voting will last for approximately one week and will end on Saturday,
 October 1st at midnight in UTC (2011-10-01T00:00:00Z).

 - Jonathan M Davis

No.
Sep 28 2011
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 28/09/11 9:19 AM, Peter Alexander wrote:
 No.

This would be a conditional yes if the template functions were removed from the allocator interface. IMO allocators should never construct objects; they should only allocate memory.
Sep 28 2011