Re: [boost] Query of Interest - vlarray

From: David White (dave_at_[hidden])
Date: 2002-04-16 05:59:56

On Mon, 2002-04-15 at 23:27, Ian McCulloch wrote:
> On 15 Apr 2002, David White wrote:
> 
> > I was wondering if there would be any interest in a class template,
> > vlarray, which would have functionality similar to a stack-based array,
> > but which would have its size set at runtime. Essentially it would
> > provide functionality similar to the Variable Length Arrays (VLAs) now
> > offered in C. It would have a specialized allocation strategy written
> > for it, which would provide allocation/deallocation times much faster
> > than more general containers such as straight heap-based arrays or
> > vectors.
>  ...
> 
> I for one would definitely be interested in this, there are several times 
> I need a tempoary buffer in the inner loop of a high performance 
> (well, its _supposed_ to be high performance :-) numerical code, 
> currently this buffer has to be supplied by the caller, a fast stack-based 
> allocator would be a nice alternative, especially since it would eliminate 
> what is currently an assumed maximum size.

Well, just to clarify, the allocation would still be substantially
slower than allocating a C-style array. This is mainly because
allocating a C-style array is so fast (as in, typically a single
assembler instruction). Creation of a vlarray would involve calling the
vlarray's (possibly inlined) constructor, calling the allocation
function, which would have to allocate a new chunk if there is no space
left on the current chunk and do some arithmetic (for types with a size
other than 1, anyway) to make sure alignment is correct. This is still
alot faster than normal heap-based allocation might be, but nowhere in
the league of the speed of genuine stack allocation.

The places where I would suggest using vlarray are:

- where you are currently using a fixed size array, where your program
will fail in some way if the array is not large enough, and you are
willing to accept the speed degradation for program
correctness/flexibility.
- where you are currently using an STL sequence container - especially a
vector or string - as a local variable which has an initial size that is
set at runtime, but doesn't have its size change after this. Changing to
vlarray would provide more speed at the cost of reduced flexibility.

Essentially, for most sequential container requirements, I see two
extremes - a C-style array which is extremely inflexible (size set at
compile time, can't be resized), but very fast; and STL containers which
are very flexible, yet relatively slow. The idea of vlarray is to be
somewhere between these - when you want something a little less flexible
than a vector in exchange for a speed increase, or something a little
more flexible than an array in exchange for a speed decrease.

> 
> It is important that the container imposes as few restrictions as possible 
> on the underlying value_type, and especially, that a stack-based 
> container of builtins does not initialize the elements.  If this is 
> not possible/desirable, then it would be better to separate the allocation 
> into another class and layer the array on top.

Well, I think that it would be nice to also expose the allocator to
users. They'd just have to be careful about it since it would make some
assumptions about allocation/deallocation order in order to get its
speed increase.

However, I think that it is reasonable to elide initialization of
builtins. vlarray would probably have an initialization constructor as
well as a non-initializing constructor.

David.

> 
> Cheers,
> Ian McCulloch
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost