Summary
The growable array I posted about two days ago has evolved into a full-featured stack template class with more features, more tests, better performance and contract verification.

---

Advertisement

The performance of the OOTL stack class has improved significantly with the use of std::allocator, and the addition of contract verification. The latest version is at OOTL.org.

Here are some benchmark results for containers of 12.8 million elements:

benchmarking : grow_vector(vec, count) = 1015 msec
benchmarking : grow_vector(deq, count) = 734 msec
benchmarking : grow_stack(stk, count) = 577 msec
benchmarking : grow_vector(vec, "hello", count / 40) = 1420 msec
benchmarking : grow_vector(deq, "hello", count / 40) = 1047 msec
benchmarking : grow_stack(stk, "hello", count / 40) = 953 msec
benchmarking : grow_vector(vec, fubar(), count / 10) = 1875 msec
benchmarking : grow_vector(deq, fubar(), count / 10) = 717 msec
benchmarking : grow_stack(stk, fubar(), count / 10) = 578 msec
benchmarking : vector_indexing(vec) = 593 msec
benchmarking : vector_indexing(fixed_deq) = 6749 msec
benchmarking : vector_indexing(grown_deq) = 6733 msec
benchmarking : stack_indexing(fixed_stack) = 890 msec
benchmarking : stack_indexing(grown_stack) = 1171 msec
benchmarking : vector_iteration(vec) = 1358 msec
benchmarking : vector_iteration(fixed_deq) = 1546 msec
benchmarking : vector_iteration(grown_deq) = 1546 msec
benchmarking : stack_iteration(fixed_stack) = 1219 msec
benchmarking : stack_iteration(grown_stack) = 1297 msec 

To summarize the results, vectors are slow at individual element growth using the push_back() member function, sometimes more than 3x than the stack. The variation depends on how expensive copy operations are. An extremely expensive copy operation will cause the vector to suffer greatly. The other thing I want you to notice is that deques are very very bad at indexing, 6x as slow as the stack! The difference between fixed_stack and grown_stack is due to the fact that if initialized with a specific size the data structure allocates a single large initial buffer, rather than needing to create a long doubling list.

As I mentioned previously the data structure used, is a "reverse doubling list" (does anyone know if this exist under a prior name?) which is a linked list of arrays each one twice the size as the next. Lookups take an average constant time in this data structure, with a worst case of O(Log N).

The recent versions uses the latest techniques I've developed for programming with contracts, which are more effective previous incarnations. Here is what the contract verification class looks like:

template
<
  typename Implementation,
  typename Inherited
>
struct stack_contract : Inherited
{
  // public typedef
  typedef Inherited inh;
  typedef Implementation impl;
  typedef typename inh::value_type value_type;

  // constructors
  stack_contract() : inh() { }
  stack_contract(impl& x) : inh(x) { }
  stack_contract(int nsize, value_type x = value_type()) : inh(nsize, x) { }

  // public functions
  void pop() {
    int old = inh::count();
    assert(!inh::is_empty());
    inh::pop();
    assert(count() == old - 1);
  }
  void push(const value_type& x) {
    int old = inh::count();
    inh::push(x);
    assert(inh::count() == old + 1);
  }
  value_type& top() {
    assert(!inh::is_empty());
    value_type& ret = inh::top();
    value_type& tmp = inh::operator[](inh::count() - 1);
    assert(&ret == &tmp);
    return ret;
  }
  int count() {
    int ret = inh::count();
    assert(ret >= 0);
    assert(ret > 0 ? !inh::is_empty() : inh::is_empty());
    return ret;
  }
  bool is_empty() {
    bool ret = inh::is_empty();
    assert(ret ? inh::count() == 0 : inh::count() > 0);
    return ret;
  }
  value_type& operator[](int n) {
    assert(n >= 0);
    assert(n < inh::count());
    return inh::operator[](n);
  }
};

The contract is applied to the stack implementation as follows:

#ifndef _NDEBUG
  template
  <
    typename T,
    typename Implementation = indexable_stack_impl<T>,
    typename Contract = stack_contract<Implementation, Implementation>,
    typename Extension = stack_extension<Implementation, Contract>
  >
  struct stack : Extension
  {
    typedef Implementation impl;
    typedef Extension inh;
    stack() : inh() { }
    stack(impl& x) : inh(impl& x) { }
    stack(int nsize, const T& x = T()) : inh(nsize, x) { }
  };
#else
  template
  <
    typename T,
    typename Implementation = indexable_stack_impl<T>,
    typename Extension = stack_extension<Implementation, Implementation>
  >
  struct stack : Extension
  {
    typedef Implementation impl;
    typedef Extension inh;
    stack() : inh() { }
    stack(impl& x) : inh(x) { }
    stack(int nsize, const T& x = T()) : inh(nsize, x) { }
  };
#endif

The reason it is so great to have the contract separated like this is for two main reasons:

1. the contract is separated into a logical and cohesive unit which is easier to read and understand, and can serve as a standalone description of the implementation class.
2. the logic of the implementation remains unaffected by the verification of preconditions and postconditions

To understand the significance of number 2 consider the pop() function. Traditional programming techniques would have preconditions and postconditions checked directly within the function implementation. For instance, the pop() function would have to be written as:

  void pop() {
    int old = inh::count();
    assert(!inh::is_empty());
    ...
    assert(count() == old - 1);
  }

But the problem with this approach is that during release builds there remains a superflous variable declaration and a superflous call to count(). In this trivial example the compiler might be able to optimize the calls away, but in other less trivial cases it won't be able to do so. By separating the entire contract verification into a separate class, all of the logic is applied (or not) depending on the _NDEBUG macro.

I hope some of this code I am developing is useful, the download is public domain, so you can use it to your heart's content. If you need help with it, let me know.

Talk Back!

Have an opinion? Be the first to post a comment about this weblog entry.

RSS Feed

If you'd like to be notified whenever Christopher Diggins adds a new entry to his weblog, subscribe to his RSS feed.

Digg | del.icio.us | Reddit

About the Blogger

Christopher Diggins is a software developer and freelance writer. Christopher loves programming, but is eternally frustrated by the shortcomings of modern programming languages. As would any reasonable person in his shoes, he decided to quit his day job to write his own ( www.heron-language.com ). Christopher is the co-author of the C++ Cookbook from O'Reilly. Christopher can be reached through his home page at www.cdiggins.com.