RE: [boost] Pool Iterators?

From: scleary_at_[hidden]
Date: 2002-11-15 15:50:02

> -----Original Message-----
> From: Geoff Leyland [mailto:geoff.leyland_at_[hidden]]
> 
> Hi Steve,
> 
> Thanks for the reply.

And sorry for the delay on this reply! :)

> On Lundi, novembre 11, 2002, at 06:00 , scleary_at_[hidden] wrote:
> 
> > One possibility is to write an object type that sits between your 
> > object and
> > the pool allocator, which adds a single pointer to your object.  
> > Something
> > similar to what a doubly-linked list container would do 
> when rebinding 
> > its
> > Allocator.  This gives you the ability to iterate over 
> them, and also 
> > allows
> > fast insertion and deletion.
> 
> This pretty much what I've got.  There's an object that talks 
> to a the 
> pool, and remembers everything that I've allocated in a 
> vector (actually 
> a holey_vector).
> This was really slow for deleting something, because 
> searching through a 
> list of 20000 pointers for the one you want is a waste of time.
> I solved that my sticking a back-pointer in the object 
> itself. This is a 
> sufficient solution, but I think it lacks elegance compared to a 
> possible pool_iterator, but, if you think it's the best idea, I'll go 
> that way.
> 
> One of the reasons I like the pool_iterator is that I store 
> the pointers 
> themselves in a vector with "holes".  This makes insertion 
> and deletion 
> in the vector very fast, and you can iterate through it very 
> quickly.  
> The free list is a map of free indexes, which means it's easy to work 
> out as you walk through the list which elements are free, and 
> also, that 
> any new allocations into free space are at the bottom of the 
> list, so, 
> with a bit of luck, you can cut the end off a shrinking list.
> I was pretty much of the opinion that this was just a cheap and nasty 
> substitute for a real pool allocator (it's what I was using before I 
> used pool), not in the least because when the vector resizes 
> the whole 
> thing moves.

I think I have been too lacking in sleep lately, and I cannot wrap my brain
around what you're describing.  But it seems to me that this requires
additional space overhead for a pool, so it's not something that I would
want to see in the generic pool<>.  However, if it's something you think
would be usable to others and can be built on top of the generic pool<>, I'd
be willing to accept an interface built on top of pool.

> There's stuff in the code and comments about an "ordered" 
> free list.  If 
> you can excuse my ignorance, does this mean that it's potentially 
> possible to walk through the pool's storage at the same time 
> as walking 
> through the ordered free list and find out fairly cheaply 
> which blocks 
> are free?

Yup.  A pool can be ordered or not, depending on how it is used.  If it is
ordered, then you can walk through the storage and free list at the same
time.  Take a look at release_memory() in pool.hpp, which does exactly that
-- it looks for allocated sections of storage that are completely free and
releases them back to the OS.

> > A similar approach, if you're willing to more seriously 
> change the code 
> > that
> > allocates/deallocates the objects, is to keep a 
> doubly-linked list of
> > pointers to the allocated objects.  But then reference the objects
> > indirectly through iterators of that list.  If you 
> reference them in 
> > this
> > way, then deletion should be fast.
> 
> That's not a bad idea.  The easiest would be to just stick 
> next and prev 
> pointers in the objects themselves.  But even so, if 
> pool_iterators were 
> possible in a generic way, everyone would benefit, and my code would 
> "just work".

I think a generic wrapper on top of the generic pool would be the best
approach.  That would enable those who do not need the iterative
functionality to not pay the price of it, but also supply that functionality
for those users who need it.

        -Steve