Re: [boost] [allocators] Article and library about allocatorimprovements

From: Lance.Diduck_at_[hidden]
Date: 2008-06-24 10:15:38

  Ion Gaztañaga wrote>
>In other words, Scoped Allocators and my proposal are completely complementary
To clarify "Scoped Allocators" is somewhat of a misnomer. It does not really address allocator implementation. To presume to speak for the authors (and I have had years collaboration with them when we worked together)the scoped allocator proposal intended two things:
1. The type of something does not change according to what "policy" is used to implement it - esp allocators. In particular, one should not be able to programatically determine differences between two types outside of public accessors, such that the operator== is equivalent to the logical conjunction of all public members (and accessors) equality compared. Furthermore, the equality test is the sole determiner of substitutability. (this was later "relaxed" to refer to only "salient" properties of a type). Also, any identical sequence of modifications applied to two "equal" instances should end up as "equal" (in other words, the serializable property)
2. The allocator in a container can be thought of modeling a storage class. So if I have a container that is a member of a struct, and that struct is instanced in storage class A (heap, stack, etc) then each member should also gets it memory from that same region. This is what the "scoped" part means. To obstensibly enhance performance (by increasing locality of reference perhaps) each object should be able to take it own allocator (arena, region, whatever), and pass that along to its members. So instead of "class specific" allocators we should have "object specific" allocators (hence the runtime polymorphism). (see Large Scale C++ chap 10 for a sketch of this)

 
In summary, the approach is a generalization of how C types interact with the UNIX process memory model in a sequential program. For instance, in C operator== for a struct is implemented as bitwise compare, and this has no dependence on which storage class is used to hold the "value." So one could argue (as the authors do) that policies that change the type (as in policies that are template parameters) are counterintuitive, and even bad design. Why? Because for otherwise "equivalent" things, operator== is inaccessible because the types do not allow it -- and policies do not change the "value" of a type, vis a vis what this type represent in the domain model (think OO programming). 

 
Indeed, for an allocator to be "scopeable" it cannot know anything about the type is allocates. Therefore, it has a particualry hard time taking advantage of any optimizations that are possible when you do know the type. For example, it would be nearly impossible to make a Burst Allocator scopable. And pretty hard to make a shared memory allocator scopeable. 

What did eventally make it to the WP was a design that allowed all kinds of options for how allocators were propogated via copy ctorsm, move ctors, and assignments.
Lance

-----Original Message-----
From: Ion Gaztañaga [mailto:igaztanaga_at_[hidden]] 
Sent: Monday, June 23, 2008 12:15 PM
To: boost_at_[hidden]
Subject: Re: [boost] [allocators] Article and library about allocatorimprovements

David Abrahams wrote:
> Ion Gaztañaga wrote:
> 
>> I plan to publish the article somewhere (supposing someone is crazy 
>> enough to publish it ;-) ) but first I wanted to share this with 
>> boosters to try to improve the article/library and know if developers 
>> are interested in allocator issues. Comments are welcome!
> 
> Hi Ion,
> 
> Are you aware of the "scoped allocator" support that has recently been 
> accepted into the WP?

Yes, thanks. I participated in some discussions with Pablo Halpern and John Lakos to make Scoped allocators with non-scoped ones (basically shared memory). Scoped allocators are basically mainly related to allocator propagation and polymorphic allocators (plus the machinery to implement this). My proposal has 3 different parts:

1) Realloc (expand in-place) and shrink to fit for std::vector. This means reusing the old buffer (and avoiding moving or copying data) if the allocator supports this.

2) Burst allocation: Some node containers (list, map...) just implement range insertion with a loop:

for(/*every input element*/){
    this->insert(pos, *inpit);
}

the idea here is to make a single to the allocator to allocate N nodes with a single call. The allocator can just allocate a single big chunk (thus, avoiding N lookups) and divide the big chunk in individually deallocatable nodes.

3) Adaptive pools:

Some allocators, (like Boost.Pool) use simple segregated storage to minimize node overhead. Sadly, they don't implicitly return memory to the general-purpose allocator because the operation is costly (Boost.Pool offers a purge() or release_memory() function to explicitly trim allocated nodes). Adaptive pools are similar to simple segregated storage allocators but they use alignment to automatically deallocate memory while maintaining zero per-node payload. These allocators don't need any allocator extension but they work extremely well with burst-allocation because we can simplify bookkeeping operations that have some impact when using single node allocation scheme.

In other words, Scoped Allocators and my proposal are completely complementary.

Regards,

Ion

Visit our website at http://www.ubs.com

This message contains confidential information and is intended only 
for the individual named.  If you are not the named addressee you 
should not disseminate, distribute or copy this e-mail.  Please 
notify the sender immediately by e-mail if you have received this 
e-mail by mistake and delete this e-mail from your system.
        
E-mails are not encrypted and cannot be guaranteed to be secure or 
error-free as information could be intercepted, corrupted, lost, 
destroyed, arrive late or incomplete, or contain viruses.  The sender 
therefore does not accept liability for any errors or omissions in the 
contents of this message which arise as a result of e-mail transmission.  
If verification is required please request a hard-copy version.  This 
message is provided for informational purposes and should not be 
construed as a solicitation or offer to buy or sell any securities 
or related financial instruments.