3

I was accidentally surprised to found that inserting sorted keys into std::set is much much faster than inserting shuffled keys. This is somewhat counterintuitive since a red-black tree (I verified that std::set is implemented as a red-black tree on my system) as a self-balanced binary search tree, would need to do a lot of rebalancing opeartions to insert a sequence of sorted keys, thus inserting sorted keys should take more time than inserting shuffled keys.

But the fact is, inserting sorted keys can be up to 15 times faster than inserting shuffled keys! Here is my testing code and some results:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <set>
#include <vector>
using namespace std;

int64_t insertion_time(const vector<int> &keys) {    
        auto start = chrono::system_clock::now();
        set<int>(keys.begin(), keys.end());
        auto stop = chrono::system_clock::now();
        auto elapsed = chrono::duration_cast<chrono::milliseconds>(stop - start);
        return elapsed.count(); 
}

int main() {
    size_t test_size;
    cout << "test size: ";
    cin >> test_size;
    vector<int> keys(test_size);
    for (int i = 0; i < test_size; ++i) {
        keys[i] = i;
    }
    
    // whether shuffled case or sorted case took first was irrelevant and results were similar
    auto rng = std::default_random_engine {};
    shuffle(keys.begin(), keys.end(), rng);
    cout << "shuffled: " << insertion_time(keys) << endl;

    sort(keys.begin(), keys.end());
    cout << "sorted: " << insertion_time(keys) << endl;

    return 0;
}

// i7 8700, 32 GB RAM, WIN10 2004, g++ -O3 main.cpp
// An interesting observation is that the difference becomes larger as test_size being larger.
// Similar results showed up for my handwritten red-black tree and other
// machines( or other compilers, operating systems etc)

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 1000000
shuffled: 585
sorted: 96

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 3000000
shuffled: 2480
sorted: 296

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 5000000
shuffled: 4805
sorted: 484

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 10000000
shuffled: 11537
sorted: 977

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 30000000
shuffled: 46239
sorted: 3076

Anyone explains this please? I guess that this has something to do with cache locality since when inserting sorted keys, rebalancing typically involves those nodes that were most recently inserted. But above is just my guess and I know very little about cache locality.

Leon Cruz
  • 345
  • 3
  • 11

1 Answers1

5

If you look at https://en.cppreference.com/w/cpp/container/set/set

you can see:

Complexity
[..]
2) N log(N) where N = std::distance(first, last) in general, linear in N if the range is already sorted by value_comp().

We can use insert in loop with end() as hint which is amortized constant with correct hint.

Jarod42
  • 203,559
  • 14
  • 181
  • 302
  • But I still can't see why it is the case and what it has to do with `hint`. The ctor of `set` knows nothing about the sortedness of the keys. – Leon Cruz Feb 23 '21 at 11:38
  • 2
    If it is sorted, there is only one check to do find the position of the new element (is last position ok). When wrong, binary search (so `log(N)`) is done to find position. – Jarod42 Feb 23 '21 at 11:43
  • @LeonCruz checking if a sequence is sorted is very cheap (`O(N)`) compared to actually sorting (`O(N log(N)`) – 463035818_is_not_an_ai Feb 23 '21 at 11:54
  • @Jarod42 But the results were similar for my handwritten red-black tree, which always searches from the root when inserting keys. Also, I just found that unordered_set gives similar results, though the difference is smaller and the type int might play an important role in this case – Leon Cruz Feb 23 '21 at 12:08
  • @largest_prime_is_463035818 But what has it to do with checking sortedness? – Leon Cruz Feb 23 '21 at 12:09
  • @LeonCruz: My explanation is about complexity to find insertion point. I don't know if/how tree rebalancing is impacted by the position of insertion. – Jarod42 Feb 23 '21 at 12:25
  • @LeonCruz • instead of `set(keys.begin(), keys.end());` try adding the keys one-by-one in a for loop. I expect the set constructor to insert the middle element first, then the left partition middle, then the right partition middle, and so on, until the entire vector is inserted. And a pre-sorted vector won't require any rebalancing. – Eljay Feb 23 '21 at 12:29
  • @Eljay I have tried that, results were the same. Also my handwritten rbtree yielded similar results. My own rbtree ctor simpy adds keys from keys.begin() to keys.end() and always starts the seach from the root node. – Leon Cruz Feb 23 '21 at 12:45