STL Benchmark vs. ADT & DS C++ API

In order to reliably test API against STL and make everything transparent, another GIT project was created for that purpose alone. To install that project and run tests yourselves, go to its homepage and follow steps described there.

In benchmark results below, following methodology was used:

Despite different programming behind, memory usage is dictated by data structure and remains the same between STL and CDS, so the only thing that varies is speed.

Lists

Test case:

  1. checking duration of a million rows insertion on list's tail
  2. checking duration of iterating all list from head to tail
  3. checking duration of getting all list element values by offset from head to tail
  4. removing all list elements based on offset from tail to head (for dynamic arrays) and head to tail (for [doubly-]linked lists)

Benchmark results for long data type:

ImplementationInsertion (ms)Iteration (ms)Selection (ms)Deletion (ms)
ArrayList14312
std::vector13001
LinkedList22437
std::forward_list22036
DoublyLinkedList21438
std::list22126

Benchmark results for char* data type:

ImplementationInsertion (ms)Iteration (ms)Selection (ms)Deletion (ms)
ArrayList13311
std::vector13001
LinkedList21337
std::forward_list21936
DoublyLinkedList21438
std::list22036
Several notes:
1. tests for dynamic array implementations use reserved size of one million plus one. The reason is that each implementation has its own growth point (A grows at point V, while B grows at point Z>V: if we stop insertion between V and Z, A will appear slower because it has done one more reallocation)
2. std::list & std::forward_list do not support getting element by offset

Conclusion: STL wins by a 1-2ms margin, except on iterating Dynamic Array, where ArrayList has to encapsulate whereas std::vector can use pointer arithmetics and thus be faster by 3ms.

Maps

Test case:

  1. checking duration of a million rows insertion
  2. checking duration of iterating all map
  3. checking duration of getting all map entry values by key
  4. removing all map entries based on key

Benchmark results for long key & value types:

ImplementationInsertion (ms)Iteration (ms)Selection (ms)Deletion (ms)
TreeMap1841710389
std::map1931911792
HashMap1 2446917
std::unordered_map1 2552717

Benchmark results for char* key & value types:

ImplementationInsertion (ms)Iteration (ms)Selection (ms)Deletion (ms)
TreeMap19019129104
std::map19814125143
HashMap1 25592026
std::unordered_map1 2117192848
Several notes:
1. tests for hash table implementations use reserved size of one million plus one. The reason is that each implementation has its own growth point (A grows at point V, while B grows at point Z>V: if we stop insertion between V and Z, A will appear slower because it has done one more reallocation)
2. same hashing function per type was used for both std::unordered_map and HashMap to make results comparable. Default hash function for char* used by std::unordered_map is much slower.

Conclusion: API wins on all counts (5% advantage on TreeMap vs. std::map, 25%-100% advantage on HashMap vs. std::unordered_map).

Sets

Test case:

  1. checking duration of a million rows insertion
  2. checking duration of iterating all set
  3. removing all set entries based on value

Benchmark results for long data type:

ImplementationInsertion (ms)Iteration (ms)Deletion (ms)
TreeSet1781977
std::set1601678
HashSet1 228616
std::unordered_set1 237313

Benchmark results for char* data type:

ImplementationInsertion (ms)Iteration (ms)Deletion (ms)
TreeSet18514109
std::set18712139
HashSet1 234821
std::unordered_set1 245731
Several notes:
1. tests for hash table implementations use reserved size of one million plus one. The reason is that each implementation has its own growth point (A grows at point V, while B grows at point Z>V: if we stop insertion between V and Z, A will appear slower because it has done one more reallocation)
2. same hashing function per type was used for both std::unordered_set and HashSet to make results comparable. Default hash function for char* used by std::unordered_set is much slower.

Conclusion: on Red Black Tree implementations (TreeSet and std::set) results are a draw, wheres in Hash Table implementations (HashSet and std::unordered_set) API is a very strong winner (32% advantage on HashSet vs. std::unordered_set).

Conclusions

Test results demonstrate that by ergonomics and speed, API outperforms STL. Even in areas where it is in slight disadvantage, it brings forward an orderly structure that is easy and consistent to work with:


Share