VLA Redux

After discovering C99’s Variable Length Array feature, I was discouraged by the apparent lack of a C++ equivalent. To review, a VLA has a dynamic size at creation time, but is otherwise fixed. This allows it to use stack memory for blazingly fast allocation and deallocation. The fully-dynamic, growable, heap-allocated std::vector is heavyweight by comparison.

In an ideal world, C++ would have a VLA template class which would confer all the benefits of C99’s VLA, plus additional type safety and (for the love of god) a .size() accessor.

In wrestling with this, I stumbled on to the idea of putting alloca() into a forceinline function. Depending on your mood, this is either a clever trick or a fragile hack.

Let me enumerate the problems here:

  1. The alloca() function is not standard.
  2. Neither is forceinline.
  3. If the compiler cannot forceinline your alloca function, it’s a bug.
  4. Compilers can never guarantee inlining of arbitrary functions (recursion, etc).

That being said, here’s a nascent implementation which seems to work on gcc and VC++:


#include <new>
#include <stdlib.h>

#if defined( __GNUC__ )
   #define FORCEINLINE inline __attribute__ ((always_inline))
   #define ALLOCA alloca
#elif defined( _MSC_VER )
   #define FORCEINLINE __forceinline
   #define ALLOCA _alloca
#endif

template< typename T >
class dynamic_array
{
   private:
   T* elems_;
   std::size_t size_;

   public:
   FORCEINLINE explicit dynamic_array(std::size_t size) :
      size_(size),
      elems_(static_cast<T*>(ALLOCA(sizeof(T)*size)))
   {}
   T& operator[](std::size_t x) { return elems_[x]; }
   std::size_t size() const { return size_; }
};

Now we can say things like:


template< typename A >
void fib(A array)
{
   array[0] = 0;
   array[1] = 1;
   for( unsigned i=2; i<array.size(); ++i )
     array[i] = array[i-1] + array[i-2];
}

void both(size_t size)
{
   dynamic_array<int> d(size);  // cheap
   std::vector<int> v(size);
   fib(d);
   fib(v);
}

If we had a caller_alloca() or the ability to write if( inline ), we might even be able to do this safely.

Kevin and I talked about this idea at length and, being the uber-coder that he is, he whipped up a full-fledged version here. Check it out.

Advertisements


%d bloggers like this: