Re: [boost] [GSOC] Regarding the project Boost.DeVector

Subject: Re: [boost] [GSOC] Regarding the project Boost.DeVector
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2009-03-28 14:13:57

Satyam Shekhar skrev:
> Hi Thorsten,
> I have been working on my proposal for the last few days and am almost
> done. Some of the questions which came to my mind:
> 
> a. Why would deque need a reserve function?
> Vector needs it because growing a vector is costly due to relocations,
> and a reserve can reduce those relocations. A deque which is
> *generally* (from the reading I did and the opinions on this list)
> implemented as a list of blocks (whose addresses are stored in an
> array) will not need the relocations because the blocks are all
> scattered in memory. The only case where relocations would be required
> is when the array storing the addresses grows and needs to be
> relocated. Will this be frequent? Is this the case we are targeting
> when we want to add the reserve function?
> 
> b. Why isn't the reserve function already there in a deque?
> Assuming there is a valid case for this function, adding it shouldn't
> be too difficult. Allocate a block(s) and add the address to the
> top-level array.

Well, I can't say why exactly std::deque is like it is. But I guess it 
has something to do with shrinking the container automatically
when elements are erased (std::vector never does this).

Now, I think it will be possible to implement reserve such that
it allocates one big chunk with the new segments pointing into this
chunk by adding a flag saying if the segment can be deallocated.

> c. Why would be want to specify the size of the chunks?
> Again, as in a., relocation does not take place in a deque except the
> top-level array, and changing the chunk size will not change the
> frequency of relocations in that. Also, with blocks of unequal sizes,
> providing constant time random access will be difficult.

The chunk size needs to be the same. So if the chunk size is changed
after elements is added to the container, it would need to reallocate to 
new segments (sort of like rehash()).

But, initially, it would be very handy to set the segment size such that 
it matches your particular application, and such that allocation 
performance is
portable accross compilers. With std::deque you just don't know.

> Regarding the project proposal, I wished to know whether to put it on
> the mailing list first, or submit it through the gsoc app.

I guess you should do both.

-Thorten