Results
The data set is 1,000,000 integers using g++ version 8.1 and optimization level -O2.The computer used for the testing is nina:
Here are the details about nina.Operating System Linux Mint 17 Qiana 3.13.0-24-generic x86_64 Model Shuttle Inc. DS81D Model ID Motherboard Shuttle Inc. FS81 Processor Intel(R) Core(TM) i7-4790S CPU @ 3.20GHz 1 Processor, 4 Cores, 8 Threads Processor ID GenuineIntel Family 6 Model 60 Stepping 3 L1 Instruction Cache 32.0 KB x 4 L1 Data Cache 32.0 KB x 4 L2 Cache 256 KB x 4 L3 Cache 8.00 MB Memory 15.6 GB BIOS American Megatrends Inc. 3.08
System topology:
Table of results (with compiler optimization level -O2)
Data structure insert*
(random)delete*
(random)insert
(sorted)delete
(sorted)insert
(sorted rev.)delete
(sorted rev.)find*
(random)AVL tree 0.689 0.842 0.186 0.197 0.185 0.196 0.345 Red-black tree 0.653 0.601 0.223 0.110 0.228 0.109 0.328 Skiplist 0.790 0.768 0.138 0.066 0.111 0.111 0.054 BList1 1.837 2.461 6.297 (no opt)2
0.691 (w/opt)30.175 0.475 3.371 2.402 Hash table (OA)4 0.213 0.655 (PACK)5
0.187 (MARK)60.222 Hash table (chaining)7 0.360 0.345 0.346
* These columns are the most relevant because they represent the average/typical case.
1The BList was tested with 2,048 items per node.
2No special optimizations were made and the normal search code was used to find the position.
3Before walking the list looking for the insertion point, a check was made to see if the value being inserted was larger than the largest element in the list. This meant no searching was required and it could simply be inserted at the end.
4The confguration: load factor is 0.667, hash function is Super Fast, and the collision resolution policy is linear probing.
5When an item is deleted, the remaining items in the cluster are reinserted into the table.
6When an item is deleted, the slot is simply marked as DELETED.
7The confguration: load factor is 5, hash function is Super Fast.
It's important to realize that the times are only for the operations listed. Constructors and destructors were not part of the timings, nor was the creation of the sample data. Here's an example of code that is being timed:
Timing code:// All constructors are called and test data was created ... StartTimer(); for (int i = 0; i < size; i++) tree.insert(ia[i]); StopTimer(); // All destructors are called and test data was destroyed ...
#include <chrono> std::chrono::time_point<std::chrono::system_clock> Start; std::chrono::time_point<std::chrono::system_clock> Stop; void StartTimer() { Start = std::chrono::system_clock::now(); } void StopTimer() { Stop = std::chrono::system_clock::now(); } void PrintElapsedTime() { std::chrono::duration<double> elapsed = Stop - Start; std::cout << "Elapsed time: " << std::setprecision(3) << std::fixed << elapsed.count() << std::endl; }
Things that could affect the performance:
The table above shows that compiler optimization can sometimes have a significant affect on performance.
Data structure insert
(random)delete
(random)insert
(sorted)delete
(sorted)insert
(sorted rev.)delete
(sorted rev.)find
(random)AVL tree 1.420 2.015 0.917 1.002 0.902 0.994 0.712 Red-black tree 0.750 0.832 0.354 0.207 0.347 0.197 0.717 Skiplist 1.104 1.177 0.319 0.183 0.245 0.282 0.135 BList (2048) 4.335 3.299 9.377 (no opt)
3.398 (w/opt)1.172 2.914 3.490 2.452 Hash table (OA) 0.269 2.914 (PACK)
1.014 (MARK)0.251 Hash table (chaining) 0.391 0.392 0.367
All of the sizes assume 4-byte integers and 8-byte pointers.
A BST/AVL tree node (size is 32):
A Red-black tree node (size is 32):template <typename T> struct BinTreeNode { BinTreeNode *left; // Left child BinTreeNode *right; // Right child int balance_factor; // For efficient balancing unsigned count; // Nodes in this subtree (for efficient indexing) T data; // The data };
template <typename T> struct RBNode { RBNode *left; // Left child RBNode *right; // Right child RBNode *parent; // Parent node ptr RBCOLOR color; // Color (red or black) T data; // The data };
Skiplist | Statistics |
---|---|
A Skiplist node (size varies from (24 to 140):
template <typename T> struct SLNode { unsigned level; // This node's level SLNode *prev; // Previous node SLNode* next[MAX_SKIP_LEVELS]; // Forward pointers T data; // The data }; |
Number of items: 1000000 Statistics for 1000000 nodes with interval 2: Actual Ideal Level 0 nodes: 509596 500000 Level 1 nodes: 249837 250000 Level 2 nodes: 122918 125000 Level 3 nodes: 59911 62500 Level 4 nodes: 29604 31250 Level 5 nodes: 14175 15625 Level 6 nodes: 7124 7812.5 Level 7 nodes: 3475 3906.25 Level 8 nodes: 1767 1953.12 Level 9 nodes: 807 976.562 Level 10 nodes: 388 488.281 Level 11 nodes: 184 244.141 Level 12 nodes: 99 122.07 Level 13 nodes: 49 61.0352 Level 14 nodes: 31 30.5176 Level 15 nodes: 16 15.2588 Level 16 nodes: 7 7.62939 Level 17 nodes: 8 3.8147 Level 18 nodes: 1 1.90735 Level 19 nodes: 2 0.953674 Level 20 nodes: 1 0.476837 Total nodes: 1000000 Total pointers: 1961892 pointers/nodes: 1.9619 |
BList | Statistics |
---|---|
A BList node (size varies from 24 with no limit):
template <typename T, int Size = 1> struct BNode { BNode *next; // Next pointer BNode *prev; // Previous pointer int count; // Count of items in the node T values[Size]; // Array of items in the node }; |
Number of items: 1000000 Asize: 2048 Items: 1000000 Nodes: 689 Average items per node: 1451.38 Node utilization: 70.9% (with 2048 integers per node: sizeof(BNode) is 8212 bytes) |
Open-address hash table | Statistics |
---|---|
An open-addressed hash table slot (size varies, with MAX_KEYLEN=12, size is 24):
template <typename T> struct OAHTSlot { // The 3 possible states the slot can be in enum OAHTSlot_State {OCCUPIED, UNOCCUPIED, DELETED}; char Key[MAX_KEYLEN]; // Key is a NUL-terminated string OAHTSlot_State State; // The state of the slot int probes; // For testing/debuggin T Data; // Client data }; |
Number of items: 1000000 Creating table: Primary hash function: SF Hash Secondary hash function: None (Linear probing) Max load factor: 0.667 Growth factor: 2 Deletion policy: PACK Initial table size: 1500007 Inserting 1000000 items... Number of probes: 6573876 Average probes: 6.57388 Number of expansions: 0 Items: 1000000, TableSize: 1500007 Load factor: 0.667 |
Closed-address hash table | Statistics |
---|---|
A closed-addressed (chaining) hash table node (size varies, with MAX_KEYLEN=12, size is 24):
template <typename T> struct ChHTNode { char Key[MAX_KEYLEN]; // Key is a string ChHTNode *Next; // The next node T Data; // Client data }; // Each list has a head pointer (size is 16) struct ChHTHeadNode { ChHTNode *Nodes; // All nodes for this bucket int Count; // For testing/debugging }; |
Number of items: 1000000 Creating table: Hash function: SF Hash Initial size: 200000 Max load factor: 5 Growth factor: 2 Inserting 1000000 items... Number of probes: 5011635 Average probes: 5.01164 Number of expansions: 0 Items: 1000000, TableSize: 200003 Load factor: 5 |