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

From: hicks (hicks_at_[hidden])
Date: 2002-04-19 21:19:08

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