11

I was comparing BST to Heap at: Heap vs Binary Search Tree (BST) but when I tried to benchmark both and compare results, I could not interpret the data for BST.

First, I confirmed that the standard library does use a Red-black tree: What is the underlying data structure of a STL set in C++?

Then I ran this benchmark.

main.cpp

#include <chrono> #include <iostream> #include <random> #include <set> int main(int argc, char **argv) { size_t i, n; std::set<int> bst; std::random_device dev; unsigned int seed = dev(); std::mt19937 prng(seed); std::uniform_int_distribution<> dist; if (argc > 1) { n = std::stoi(argv[1]); } else { n = 1000000; } for (i = 0; i < n; ++i) { auto random_value = dist(prng); auto start = std::chrono::steady_clock::now(); bst.insert(random_value); auto end = std::chrono::steady_clock::now(); auto dt_bst = end - start; std::cout << random_value << " " << std::chrono::duration_cast<std::chrono::nanoseconds>(dt_bst).count() << std::endl; } }

plot.gnuplot:

#!/usr/bin/env gnuplot set terminal png size 1024, 1024 set output "bst_vs_heap.png" set title "BST insert time" set xlabel "size" set ylabel "nanoseconds" plot "main.dat" using 2 notitle

Compile, run and plot:

g++ -ggdb3 -O3 -std=c++17 -Wall -Wextra -pedantic-errors -o main.out main.cpp ./main.out 10000000 > main.dat ./plot.gnuplot

Outcome:

enter image description here

Why don't I see a nice logarithmic curve, as in the theoretical data structure, but rather a somewhat constant line with some outliers?

Ubuntu 18.04, GCC 7.3, Intel i7-7820HQ CPU, DDR4 2400 MHz RAM, Lenovo Thinkpad P51.

Improve this question
19
  • 3
    One million iterations will only get you to 19 layers deep into a balance binary search tree. Hardly worth sneezing about. Commented Aug 21, 2018 at 15:56
  • 1
    It looks to me like you're looking at the inserted value (std::cout << random_value), not the size of the set. But I'm not a gnuplot expert. Commented Aug 21, 2018 at 15:58
  • 2
    @CiroSantilli新疆改造中心六四事件法轮功 Ah, yes, "using 2". Of course. Commented Aug 21, 2018 at 16:03
  • 1
    @n.m. He has already done it in the answer he wrote. Commented Aug 21, 2018 at 16:46
  • 1
    Just wanna say, dude. Stellar presentation and example. Really well done. I hope this gets upticks o'festival in the years to come. Commented Aug 22, 2018 at 7:30

1 Answer 1

Reset to default
10

The clock is likely not accurate enough as mentioned in the comments, so I've tried to group a bunch of inserts together and time them to improve the signal to noise, and it worked, I can see a logarithm now:

#include <chrono> #include <iostream> #include <random> #include <set> int main(int argc, char **argv) { size_t i, j, n, granule; std::set<int> bst; std::random_device dev; unsigned int seed = dev(); std::mt19937 prng(seed); std::uniform_int_distribution<> dist; int *randoms; if (argc > 1) { n = std::stoi(argv[1]); } else { n = 1000000; } if (argc > 2) { granule = std::stoi(argv[2]); } else { granule = 10; } randoms = new int[granule]; for (i = 0; i < n / granule; ++i) { for (j = 0; j < granule; ++j) { randoms[j] = dist(prng); } auto start = std::chrono::high_resolution_clock::now(); for (j = 0; j < granule; ++j) { bst.insert(randoms[j]); } auto end = std::chrono::high_resolution_clock::now(); auto dt_bst = end - start; std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(dt_bst).count() << std::endl; } delete[] randoms; }

Command:

./main.out 100000000 10000

Graph:

enter image description here

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

This is more or less what is expected by theory. It can be smoothed out even further by collecting the timing in a vector, rather than directly sending it to std::cout. Then repeat the experiment N times, starting each time with the same random seed. Sum up all the results of each measurement point. In the process, consider throwing away the min/max points for each insertion (to minimize noise). At the end, print the values in the vector divided by N (or by N-2, if outliers are eliminated).
@MichaelVeksler why should the same seed be used?
@scry, so that it will measure exactly the same insertions into exactly the same bst multiple times. The idea is to get rid of noise that comes from other tasks, the operating system, and timer inaccuracies, for a given insertion in a given tree.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.