Re: [boost] Re: 13. Re: Re 6. Re: Re: Query of Interest - vlarray (David White)

From: David White (dave_at_[hidden])
Date: 2002-04-20 01:50:21

Craig,

I think I can see what you're saying now. I am assuming that by
"psuedo-vlarray objects" you mean "objects that are stored in a
vlarray". I guess what you mean is that with this custom allocator, you
could do something like this:

{ //A
    vector<char,stack_allocator> myvector;
    vlarray<char,stack_allocator> myarray;
    ...code, during which time myvector might reallocate...
} //B

stack_allocator would not assume that everything happens in LIFO order,
however it would assume that anything allocated after A would be
deallocated before or at B.

I can see how this would be useful, and I would like to see how it
performs in practice. I have submitted a preliminary version of my (now
renamed to) var_length_array class template with associated allocators,
if you have the time/compulsion/etc etc it would be great if you could
write a modified version of my allocator that works in the way you
describe.

Also, note that var_length_array can store any type - POD types or
non-POD types. I think your point there was that types stored in a
var_length_array, that themselves allocate will simply allocate on the
heap. This is true, and I can see how your idea could be an advantage.

Cheers,

David.

On Sat, 2002-04-20 at 12:19, hicks wrote:
> David
> 
> >but if you want to do this, why not just use any small object allocator?
> >I would suggest that in this case the user should use a general purpose
> >small object allocator, and then only when they can guarantee LIFO
> >destruction order they could convert to use the LIFO allocator if they
> >think the performance gain warrants it.
> >
> 
> 
> I want to change my previously letter and answer you at the same time.
> You are right about a small object allocator for heap objects.
> The change: Forget I ever mentioned the word "h--p".
> I want to say this instead:
> For the sake of discussion, suppose we weaken the LIFO assumption
> so that psuedo-vlarray objects themselves can runtime alloc from the stack,
> i.e. psuedo-vlarray objects need not be POD (plain old data), and
> can use the same allocator from which they were allocated
> (this has a symmetric feeling to it).
> (Your small object allocator argument still holds, but wait...)
> Of course the lifetime of all memory used by these objects
> must cease with the destruction of the object.
> 
> I said "weaken" the LIFO assumption for the following reason.
> We cannot say it is no longer LIFO at all; instead it is now only LIFO
> between scopes.
> { scope A { scope B } scope A again }
> Scope A and scope B have a mutually LIFO relationship,
> but the objects within scope A might not be LIFO relative to each other.
> (Likewise for B)
> 
> We are able to state the following weak-LIFO guarantee:
> ** When a scope is exited, no trace it was ever there is left on the
> stack-allocator. **
> 
> Up side:
> 1. A stack allocator will not gradually fragment, like a heap can.
> 2. A stack allocator has guaranteed O(1) allocation time.
> 3. If N objects are allocated in a scope lifetime, deallocation
> of all N objects takes O(N) for the worst case, i.e. O(1) per object.
> A heap cannot guarantee that.
> [details: N-1 blocks are marked free, taking time O(1) for each one.
> Finally,
> the end block is deallocated and the stack unwound, taking time O(N).
> Total time is O(N)]
> 
> Down side:
> 4. Worst case for wasted space has no upper limit, since deallocated
> memory is not
> guaranteed to be reclaimed until scope exit.
> 
> In conclusion I would say that
> 
> A. stack-allocation with weak-LIFO could be useful
> in selected sections of code which were performance critical, but care
> must be
> taken because of 4.
> 
> B. Stack-allocation with strong-LIFO (all allocated data must be POD)
> could be useful in the same stiuations, but without the risk of misuse
> through runtime allocation. (* The risk of misuse through allocating
> non-scoped objects still exists)
> 
> C. In either case judicious scope delineation increases efficiency.
> 
> D. This is all about performance with no increase in functionality over
> what can be done with heaps,
> so if it isn't worry-free its not likely to be used. In that respect,
> Stack-allocation with strong-LIFO is preferable to Stack-allocation with
> weak-LIFO.
> 
> E. Implementation requires mainly (only?) a stack-based allocator with
> strong-LIFO checking.
> It wouldn't be much more difficult to write one with strong-LIFO
> checking as an option,
> which worked under weak-LIFO conditions as well.
> 
> Craig Hicks
> 
> 
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost