Click here to Skip to main content
15,860,972 members
Articles / Programming Languages / C++

Fast Indexable Stacks

Rate me:
Please Sign up or sign in to vote.
4.95/5 (16 votes)
19 Nov 2005Public Domain3 min read 60.6K   296   27   17
I provide an implementation of fast-growing indexable stacks which outperforms std::vector and std::deque

Introduction

The ootl::stack is a template class similar to std::vector which provides extremely fast element growth: O(1) complexity in both the average and worst cases, rather than the O(N) complexity of std::vector in the worst case. The ootl::stack template also provides fast indexing, outperforming std::deque by as much as 6x or more.

The Reverse Doubling ArrayList

The ootl::stack template is based on a data structure called the "reverse doubling array list" (which as far as I know is original, but if anyone knows otherwise, please let me know. The reverse doubling array list is a linked list of arrays, each one twice the size of the next. When the array of the first node (or last node depending on how you want to envision it) is filled to capacity, a new node is created with twice the capacity as the previous one. Since the original data isn't moved, only 2N memory is used at any given time, no deallocation occurs, and there is no need for the N destruction and copy-construction operations.

Quite clearly, this data structure supports efficient growth, since there are no copies, and less wasted space. However, what is somewhat counterintuitive is that this data structure provides, on an average, random element access with constant complexity. The key to achieving indexing with O(1) complexity is the list must be traversed from the biggest node to the smallest.

Analyzing the Complexity of Indexing

The reverse doubling array list has half of its elements in the first node, 1/4 of its elements in the second node, 1/8 in the third node, and so on until some lower bound is reached. On an average, you will find a node you want after two elements, and in the worst case, you'll find it in O(Log N) time complexity. Here's why: ignoring lookup operations, the mean number of nodes you need to visit to access an element using an index lookup is expressed by the following equation:

(1/2)n + (2/4)n + (3/8)n + ... + (i/2^i)n / n

The factors of n in the quotient are the infinite series 1/2 + 2/4 + 3/8 + 4/16 + ... + (i/2^i). This series converges at the value of two. In order to understand why this is so, consider that it is equivalent to the following infinite sum of infinite sums:

(1/2 + 1/4 + 1/8 + ...) + (1/4 + 1/8 + 1/16 + ...) +
                            (1/8 + 1/16 + 1/32 + ...) + ...

These infinite series are very well-known and easily recognizable to be equal to:

1 + 1/2 + 1/4 + ...

Benchmarks

I've run a few informal tests to compare the performance of the described stack class with the std::vector and std::vector implementations which come with the STLPort 4.6.2 implementation of the C++ standard library. The following results were achieved under Windows XP Service Pack 2, running on an Intel Celeron 1.80 GHZ machine with 512 MB of RAM, using the MinGW GCC 3.4 compiler with full optimizations:

C++
// appending 12.8 million integers
std::vector = 1015 msec
std::deque = 734 msec
ootl::stack = 577 msec

// indexing speeds of 12.8 million integers
std::vector = 593 msec
std::deque = 6733 msec
ootl::stack = 1171 msec

These are fairly representative excerpts from the full benchmarking suite.

The Interface

The ootl::stack template itself (which is listed later) is quite complex so first here is its simplified interface:

C++
template<typename
class stack
{
public:
    // public
    typedef T value_type;
    typedef stack self;
    
    // 'structors
    stack();
    stack(self& x);
    stack(int nsize, const T& x = T());
    ~stack();
    
    // model the OOTL Indexable concept
    T& operator[](int n);
    int count();
    
    // model the OOTL Stackable concept
    void push(const T& x = T());
    void pop();
    bool is_empty();
    T& top();
    
    // model the OOTL Iterable concept
    tempate<Procedure>
    void for_each(Procedure& p);
};

The Implementation

Here's the big ol' implementation:

C++
// Public Domain by Christopher Diggins 
// http://www.ootl.org 

#ifndef OOTL_STACK_HPP
#define OOTL_STACK_HPP

#include <cstdlib>

#include <cassert>

#include <memory>

#include <algorithm>

#include <iostream>

namespace ootl {

    template<
      typename T, 
      int Factor_N = 2, 
      int Initial_N = 8, 
      typename Alloc = std::allocator<T> 
    >
    struct indexable_stack_impl
    {
    public:
      typedef T value_type;
      typedef indexable_stack_impl self;  
    private:
      // local buffer type
      struct buffer {
        buffer(int n, int i = 0, buffer* x = NULL) : 
          size(n), index(i), prev(x), begin(a.allocate(n)), end(begin + n)
        { }
        ~buffer() { 
          a.deallocate(begin, size); 
        }
        template<typename Procedure>
        void for_each(Procedure& proc, T* end) {
          if (prev != NULL) {
            prev->for_each(proc, prev->end);
          }
          T* p = begin;
          while (p != end) {
            proc(*p++);
          }
        }
        int index; 
        int size;
        T* begin;
        Alloc a; 
        T* end;
        buffer* prev;
      };  
    private:
      // begin fields 
      buffer* buff;
      T* last;
      int cnt;
      int cap;
      int init;
    public:
      indexable_stack_impl() { 
        initialize(Initial_N);
      }
      indexable_stack_impl(self& x) { 
        initialize(x.capacity());
        x.for_each(stacker(*this));
      }
      indexable_stack_impl(int nsize, const T& x = T()) { 
        if (nsize >= Initial_N) {
          initialize(nsize);
        }
        else {
          initialize(Initial_N);      
        }    
        last = buff->begin + nsize;
        while (cnt < nsize) {
          buff->a.construct(buff->begin + cnt++, x);
        }
        assert(last == buff->begin + cnt);
      }
      ~indexable_stack_impl() { 
        while (cnt > 0) {      
          pop();
        }
        assert(buff != NULL);
        delete buff; 
      } 
      // implementation of OOTL Indexable
      T& operator[](int n) {
        if (n >= buff->index) { 
          return buff->begin[n - buff->index]; 
        }
        buffer* curr = buff->prev;
      loop:
        if (n >= curr->index) { 
          return curr->begin[n - curr->index]; 
        }
        curr = curr->prev;
        goto loop;
      }
      int count() const {
        return cnt;
      }
      // implementation of OOTL Stack concept
      void push(const T& x = T()) {
        assert(last >= buff->begin);
        assert(last <= buff->end);
        if (last == buff->end) {
          add_buffer();
        }
        buff->a.construct(last++, x);
        ++cnt;
      }
      void pop() {        
        assert(last >= buff->begin);
        assert(last <= buff->end);
        if (last == buff->begin) {
          remove_buffer();
        }
        assert(buff != NULL);
        buff->a.destroy(--last);          
        --cnt;
      }
      bool is_empty() {
        return count() == 0;
      }
      T& top() {
        return *(top_pointer());
      }
      // implementation of OOTL Iterable concept 
      template<typename Procedure>
      void for_each(Procedure& proc) {
        buff->for_each(proc, last);
      }  
    private:
      void initialize(int ncap) {
        assert(ncap >= Initial_N);
        buff = new buffer(ncap); 
        cnt = 0;
        cap = ncap;
        last = buff->begin;
      }
      T* top_pointer() {
        assert(!is_empty());
        assert(last >= buff->begin);
        assert(last <= buff->end);
        if (last == buff->begin) {
          return buff->prev->end - 1; 
        }
        else {
          return last - 1;
        }    
      }
      void add_buffer() {
        buff = new buffer(buff->size * Factor_N, cap, buff);
        cap += buff->size;
        last = buff->begin;
        assert(count() < capacity());
      }    
      void remove_buffer() {
        buffer* tmp = buff;
        cap -= buff->size;
        buff = buff->prev;
        tmp->prev = NULL; 
        last = buff->end;
        delete(tmp);
      }    
      int capacity() const {
        return cap;     
      }
    };
    
    ///////////////////////////////////////////////////////////////
    // A stack_extension contains additional functions which 
    // can be easily derived from a stack
    
    template
    <
      typename Implementation,
      typename Inherited 
    >
    struct stack_extension : Inherited
    {
      // public typedef
      typedef Inherited inh;
      typedef Implementation impl;
      typedef typename inh::value_type value_type;
      
      // constructors
      stack_extension() : inh() { }
      stack_extension(impl& x) : inh(x) { }
      stack_extension(int nsize, const value_type& x = value_type()) : 
                                                       inh(nsize, x) { }
    
      // implementation of OOTL Growable concept
      void grow(int n = 1, const value_type& x = value_type()) {      
        while (n > 0) inh::push(x);
      } 
      // implementation of OOTL Shrinkable concept
      void shrink(int n = 1) {      
        while (n--) inh::pop();
      }  
      // implementation of OOTL Resizable concept  
      void resize(int n, const value_type& x = value_type()) {      
        while (n > inh::count()) inh::push(x);
        while (n < inh::count()) inh::pop();
      }    
      // implementation of OOTL Sortable concept
      bool lt(int i, int j) {
        return inh::operator[](i) < inh::operator[](j);
      }
      void swap(int i, int j) {
        std::swap(inh::operator[](i), inh::operator[](j));
      }
      // utility functions
      void clear() {
        while (!inh::is_empty()) {
          inh::pop();
        }
      }
      void dup() {
        inh::push(inh::top());
      }
      void reverse() {
        int max = inh::count() - 1;
        int n = inh::count() / 2;
        for (int i=0; i < n; ++i) {
          inh::swap(i, max - i);
        }
      }
    };
    
    ///////////////////////////////////////////////
    // The contract checks the preconditions and 
    // postconditions of the functions 
    
    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 final version of the stack
    
    #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
}
#endif

Final Words

Unfortunately, the code will not work as-is for versions of Visual C++ earlier than 7.1. You'll have to do some trimming to make it work. The code is public domain, so feel free to do what you want with it. I'd always be appreciative though of a quick note on the forum, just to let me know what kind of application this code finds a home in, it'll make me happy to know. If you want to release a more portable version, I'm sure other readers will appreciate it greatly!

License

This article, along with any associated source code and files, is licensed under A Public Domain dedication


Written By
Software Developer Ara 3D
Canada Canada
I am the designer of the Plato programming language and I teach computer science at Bishop's University. I can be reached via email at cdiggins@gmail.com

Comments and Discussions

 
QuestionHow to limit stack size? Pin
filippov.anton28-Jun-06 0:45
filippov.anton28-Jun-06 0:45 
GeneralBug (of sorts) Pin
Stewart Tootill23-Nov-05 5:50
Stewart Tootill23-Nov-05 5:50 
GeneralRe: Bug (of sorts) Pin
Christopher Diggins23-Nov-05 7:01
professionalChristopher Diggins23-Nov-05 7:01 
GeneralPreallocation, virtual memory is your friend! Pin
PedroMC23-Nov-05 0:32
PedroMC23-Nov-05 0:32 
GeneralNot understand Pin
jesusdesantos22-Nov-05 12:56
jesusdesantos22-Nov-05 12:56 
GeneralRe: Not understand Pin
Christopher Diggins23-Nov-05 4:57
professionalChristopher Diggins23-Nov-05 4:57 
QuestionFaster indexing and is Destruct/CopyConstruct really necessary? Pin
Hofver22-Nov-05 0:16
Hofver22-Nov-05 0:16 
AnswerRe: Faster indexing and is Destruct/CopyConstruct really necessary? Pin
Christopher Diggins22-Nov-05 4:06
professionalChristopher Diggins22-Nov-05 4:06 
GeneralRe: Faster indexing and is Destruct/CopyConstruct really necessary? Pin
Hofver23-Nov-05 3:17
Hofver23-Nov-05 3:17 
GeneralRe: Faster indexing and is Destruct/CopyConstruct really necessary? Pin
Christopher Diggins23-Nov-05 4:54
professionalChristopher Diggins23-Nov-05 4:54 
QuestionWhat about iterators? Pin
WREY21-Nov-05 3:16
WREY21-Nov-05 3:16 
AnswerRe: What about iterators? Pin
Christopher Diggins21-Nov-05 3:20
professionalChristopher Diggins21-Nov-05 3:20 
GeneralRe: interesting, but not enough Pin
Christopher Diggins21-Nov-05 3:34
professionalChristopher Diggins21-Nov-05 3:34 
Vasian Cepa wrote:
First, once the number of elements in this structure gets large the memory manager should check for bigger and bigger continuous memory blocks to satisfy the request. The size of the block grows up exponentially. The memory manager may, thus, fail to allocate the memory; even thought fragmented memory blocks could be free to fulfil the request.


To be fair you should mention that the std::vector requires all N elements are continuous where the ootl::stack requires at most N/2 elements are continuous in memory.

Vasian Cepa wrote:
Second, it is unfair to compare your code for performance against the std::vector or other generic STL classes, without offering the same generic functionality. ... Your solution does not have this or other generic optimizations, and hence it is somehow faster.


You are correct those generic optimizations are not available in this implementation, and I would welcome a contribution which does have them, though that is not "why" it is faster, as you conclude.

The ootl::stack is faster because it uses less memory during reallocations (2N instead of 3N), it doesn't deallocate as it grows, and doesn't have to call the destructor and copy-constructor for all N elements each time it grows.


Christopher Diggins
GeneralRe: interesting, but not enough Pin
Craig Muller21-Nov-05 9:11
Craig Muller21-Nov-05 9:11 
GeneralRe: interesting, but not enough Pin
Christopher Diggins21-Nov-05 14:32
professionalChristopher Diggins21-Nov-05 14:32 
GeneralRe: interesting, but not enough Pin
_kb_23-Nov-05 23:16
_kb_23-Nov-05 23:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.