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

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

"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

"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

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

"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

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.

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

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.

"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

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.

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

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

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

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

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.

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

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?

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

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.

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

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?

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.

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?

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.

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

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?

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.

 Ok, now I'm really lost. Where do allocators come into that?

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.

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.

 Ok, now I'm really lost. Where do allocators come into that?

 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.

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.

 Ok, now I'm really lost. Where do allocators come into that?

 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.

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.

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.

 Ok, now I'm really lost. Where do allocators come into that?

 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.

 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.

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

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 =

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.

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

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.

Jakob Ovrum <jakobovrum+ng gmail.com> writes:

No, this needs more time for review of the current iteration.

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.

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.

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.