Benchmarks

About the Performance of the OOTL

The OOTL was not originally intended to be high-performance, however since the OOTL is less about portability and genericity it is able to provide significantly improved performance over some STL implementations under some conditions.

About the Benchmarks

These benchmarks were compiled using GCC 3.4.1 and STLPort 4.6.2 using full optimizations, and run on a Celeron 1.6 GHZ with 512 MB of Ram, running Windows XP SP2. Your mileage will vary.

ootl::stack versus std::vector and std::deque

The STL provide two implementations of an indexable stack: std::vector, and std::deque. The vector implementation is typically very slow at growth, while the deque implementation is very slow at indexing. The ootl::stack is relatively fast at both.

  benchmarking for size 4000000
  benchmarking : grow_vector(vec, fubar(), count / 10) = 547 msec
  benchmarking : grow_vector(deq, fubar(), count / 10) = 234 msec
  benchmarking : grow_stack(stk, fubar(), count / 10) = 203 msec
  benchmarking : vector_indexing(vec) = 202 msec
  benchmarking : vector_indexing(deq) = 2516 msec
  benchmarking : stack_indexing(stack) = 343 msec
  benchmarking : vector_iteration(vec) = 499 msec
  benchmarking : vector_iteration(deq) = 514 msec
  benchmarking : stack_iteration(stack) = 452 msec

The noteworthy features of these benchmarks are:

• The ootl::stack and std::vector grow at roughly the same rate and are faster than a vector by a factor of more than 2x
• The ootl::stack provides slower single element indexing than a vector (nearly 2x as long), but is nearly 8x faster than a deque
• The ootl::stack provides the fastest iteration. by a small margin.

Of these results, the discrepancy between iteration and indexing may be surprising at first. The reason is that the stack provides a for_each() member function for iterating over all elements. Like a linked-list, single item access is slow (worst case O(Log(N)), average case O(2), but access to each item one by one, is very fast.

ootl::map versus __gnu_cxx::hash_map and google::dense_hash_map

  benchmarking for 800000 elements
  string benchmarks for ootl string map
  benchmarking : grow_string_map(m, data, size) = 155 msec
  benchmarking : lookup_string_map(m, data, size) = 249 msec
  string benchmarks for google string map
  benchmarking : grow_string_map(m, data, size) = 329 msec
  benchmarking : lookup_string_map(m, data, size) = 155 msec
  string benchmarks for stl string map
  benchmarking : grow_string_map(m, data, size) = 656 msec
  benchmarking : lookup_string_map(m, data, size) = 249 msec

The google hash map implementation is better in all respects than the stlport hash map implementation. Comparing the google hash map and ootl hash map implementations reveal that the trade-off is a roughly balanced exchanged of speed of growth for speed of indexing at a ration of approx. 2 to 1.

Note: hash map performance is very sensitive to the collision factors generated by the hash function used. The STLPort for instance comes with an extremely naive default hashing algorithm which significantly degrades performance. I used Paul Hseih's hash algorithm for these benchmarks.

back to the OOTL documentation home page
back to the OOTL.org home page

http://www.ootl.org
last modified: November 13, 2005
Copyright Christopher Diggins, 2005
OOTL logo copyright 2005 Paige Lybbert.