Re: [boost] Stack-based vector container

Subject: Re: [boost] Stack-based vector container
From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2011-01-23 16:01:34

Den 22-01-2011 15:18, Domagoj Saric skrev:
>
> "Thorsten Ottosen" <nesotto_at_[hidden]> wrote in message
> news:4D331E6A.2030907_at_cs.aau.dk...
>> Den 16-01-2011 16:13, Domagoj Saric skrev:
>>> Could you possibly add a policy that would 'produce' a strictly static
>>> buffer, i.e. that does not use/expand into the heap (to avoid the
>>> overhead described in the response to David Bergman)...
>>
>> Maybe. I guess it takes some measurement to see if it is actually needed.
>
> Why should we need to measure?
> - It is a priori known that overhead exists: containing and maintaining
> two extra pointers/size_ts, extra indirection for buffer access through
> a pointer on the stack (as opposed to 'direct' access to a buffer on the
> stack), 'possible' EH...
> - The primary, if not the sole purpose of this library is performance...
> ....so ignoring performance issues known in advance would be self/goal
> contradicting and a case of premature pessimization (as pretty much most
> of, so frequently encountered, 'invocations' of the 'root of all evil'
> rule are)...
>
> And measure what and how exactly?

assembler or runtime.

> - A low level tool like this can be used in a wide range of
> ways...somewhere the difference will matter little, somewhere it will
> matter a lot...A 'good' library/tool ideally does not 'cut corners'
> based on assumptions that something 'will be good enough for everyone'
> (if it does not need to)...

mostly agree.

>
>> For one, the container will allow you to do
>>
>> boost:.auto_buffer<T,N> buffer( n, boost::dont_initialize );
>>
>> to make it avoid initialization.
>
> Nice. It would be useful if it could do something similar for non-POD
> types, i.e. it would take a functor in the constructor which it would
> then 'walk' through the N entries and let it in-place construct them (to
> avoid the usual default construction then assignment procedure)...

well, you can just do that post-construction wise. No need for another 
constructor.

>
>> Futhermore, you may use
>>
>> buffer.unchecked_push_back( x );
>>
>> to avoid code that checks for a full buffer and subsequent expansion.
>
> AFAICT there is no ('unchecked') resize equivalent...

unitialised_resize() ?

> Speaking of which, there seem to be two approaches/syntaxes for using
> the unchecked/uninitialized versions (of code/functionality), with
> policies/tags and unchecked_*/uninitialized_* versions of
> functions...Perhaps it would be a 'happier' solution to go with only one
> option (policies/tags) or to replace both with a proxy 'unchecked'
> class...So that when you want 'unchecked' access you call the proxy
> getter and in effect get different semantics through an identical
> interface...This would also 'play better' with Boost.Range and
> <algorithms>...

How? Range algorithms use iterators and not much else.

boost::push_back( cont, range )

does not call cont.push_back(), and is the preferred way compared
to using copy().

>> If that is not good enough, then why not just use boost::array<T,N>?
>> (that is, if you really never will need the heap for any n)
>
> boost::array is not resizable...
> The gap between std::array and std::vector is larger then it may
> seem...and it might be worthwhile to use this opportunity to fill it
> completely...Besides a resizable stack-only/fixed-max-size buffer and a
> stack-to-heap expandable buffer (auto buffer) there is also a need for a
> fixed sized (non-resizable) buffer whose size is dynamically determined
> which also comes in two flavours, a stack-only portable alloca wrapper

alloca() does not seem to apply here: think about where you would put 
the call.

> and a heap version...both can be modeled with a const iterator_range
> (the only essential difference being that the heap version has a
> non-trivial destructor that calls delete[]...)...

As I said, I'm not sure we need all these variants. For example, if
the buffer does not need to be expanded, then it is likely the compiler
can determine that the capacity_ member is not used.

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.

-Thorsten