Re: [boost] Stack-based vector container

Subject: Re: [boost] Stack-based vector container
From: Christopher Jefferson (chris_at_[hidden])
Date: 2011-01-23 19:09:01

On 23 Jan 2011, at 23:59, Emil Dotchevski wrote:

> On Sun, Jan 23, 2011 at 1:01 PM, Thorsten Ottosen <nesotto_at_[hidden]> wrote:
>> As for the conjectured extra indirection, then I'm not sure it can become
>> any major performance problem, nor do I see how one can avoid it when we
>> need to go for the heap in certain cases.
> 
> Clearly the extra indirection is the only potential problem, otherwise
> a stack-based vector implementation could probably be replaced by a
> stack-based std::vector allocator.
> 
> However, the cost of the extra indirection is platform-dependent and
> difficult to measure in the abstract. In my experience, most cases
> when someone has complained about inefficiencies in std::vector boil
> down to incorrect use:
> 
> - not using reserve();
> - calling push_back()/insert() in a loop (which is inefficient even
> with reserve);
> - iterating by redundantly calling end() each time;
> - using operator[] for sequential access to the elements.

I find most modern compilers do not have issues with calling end() repeatedly, or push_back(). Also it is unclear if operator[] or iterators are more efficient.

The biggest issue I have with using vector is short-lived vectors, where the time is dominated by calls to new/delete inside the allocator. Of course I could start caching vectors everywhere, but then that introduces threading and singleton issues, which I would prefer to avoid. This is the ideal place for stack-based vectors, where allocating and freeing the vector is (almost) free.

Chris