Почему я получаю константу вместо логарифмической кривой для эталона времени вставки в C++ std::set на основе RB-дерева?

Question

Я сравнивал BST с Heap по адресу: Heap vs Binary Search Tree (BST), но когда я попытался сравнить оба и сравнить результаты, я не смог интерпретировать данные для BST.

Во-первых, я подтвердил, что стандартная библиотека использует красно-черное дерево: какова основная структура данных набора STL в C++?

Затем я провел этот тест.

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

Компилируем, запускаем и наносим на карту:

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

Результат:

Почему я не вижу хорошей логарифмической кривой, как в теоретической структуре данных, а скорее несколько постоянной линии с некоторыми выбросами?

Ubuntu 18.04, GCC 7.3, процессор Intel i7-7820HQ, оперативная память DDR4 2400 МГц, Lenovo Thinkpad P51.

Answer 1

Часы, вероятно, недостаточно точны, как упомянуто в комментариях, поэтому я попытался сгруппировать кучу вставок и рассчитать их время, чтобы улучшить отношение сигнал-шум, и это сработало, теперь я вижу логарифм:

#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;
}

Команда:

./main.out 100000000 10000

График: