The Artima Developer Community
Sponsored Link

Weblogs Forum
Indexable Stacks and Programming with Contracts

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 0 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Indexable Stacks and Programming with Contracts (View in Weblogs)
Posted: Nov 18, 2005 3:14 PM
Reply to this message Reply
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.

Topic: A Faster Growable Array ( Indexable Stack ) for C++ Previous Topic   Next Topic Topic: Problems with using stored procedures


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us