RB Tree insertion order sensitivity

Question

Given an interval of integers I, an RB Tree R which has n unique elements from I and a sequence S of n unique elements from I whose values are not in R, would the performance of inserting S into R vary based on whether S is sorted or in random order? How would the answer vary based on the relative size of |I| and n?

Given that the elements of S are not in R it is not clear how to analyze the invariants that insertion needs to maintain and the rebalancing operations that need to happen. Ruby benchmarks I've run where |I| is 100 times larger than n suggest that sorted insertion performs 10+% faster.

How much of a difference are you expecting since both the average and the worst case performance of RBTs is `log(n)` on insertion? — Alexey Frunze, Apr 07 '13 at 02:52
The constant factor in big-O notation can vary substantially and then there is how the hardware, i.e., the branch predictor is affected, by a particular stream of data going through an algorithm. It is one of the reasons why processing a sorted array, for example, can be many times faster than processing an unsorted array in an algorithm that seemingly is unaffected by the order of input data. See http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array I do not have an expectation but I'm curious and hence this question. — Sim, Apr 07 '13 at 03:24
@AlexeyFrunze after tweaking with my benchmarks to eliminate factors such as GC variability, I'm now seeing 10+% performance increase for the sorted data. — Sim, Apr 07 '13 at 04:15

score 2 · Accepted Answer · answered Apr 07 '13 at 04:21

The performance is going to vary.

Sample test in C++ (I know that g++'s map is based on red-black trees and used it):

#include <iostream>
#include <map>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 50000;
const int REPS = 100;
int ints[N];

int main()
{
  time_t t;
  srand(time(0));

  // fill ints[] with ints from 0 to N-1
  for (int i = 0; i < N; i++)
    ints[i] = i;

  // randomly shuffle ints[]
  for (int i = 0; i < N; i++)
  {
    int j = ((unsigned)rand() * rand()) % N;
    int t = ints[i];
    ints[i] = ints[j];
    ints[j] = t;
  }

  cout << "Inserting " << 2 * N << " sorted keys, repeating " << REPS << " times..." << endl;
  time(&t); cout << ctime(&t) << endl;
  for (int n = 0; n < REPS; n++)
  {
    map<int,int> m;
    for (int i = 0; i < N; i++)
      m[i] = i;
    for (int i = 0; i < N; i++)
      m[N + i] = i;
  }
  time(&t); cout << ctime(&t) << endl;

  cout << "Inserting " << N << " sorted keys and then " << N << " unsorted keys, repeating " << REPS << " times..." << endl;
  time(&t); cout << ctime(&t) << endl;
  for (int n = 0; n < REPS; n++)
  {
    map<int,int> m;
    for (int i = 0; i < N; i++)
      m[i] = i;
    for (int i = 0; i < N; i++)
      m[N + ints[i]] = i;
  }
  time(&t); cout << ctime(&t) << endl;

  return 0;
}

Output (liveworkspace):

Inserting 100000 sorted keys, repeating 100 times...
Sun Apr 7 04:14:03 2013

Sun Apr 7 04:14:05 2013

Inserting 50000 sorted keys and then 50000 unsorted keys, repeating 100 times...
Sun Apr 7 04:14:05 2013

Sun Apr 7 04:14:10 2013

As you can see, the performance is noticeably different: 2 seconds for sorted insertion vs 5 seconds for unsorted insertion.

I trust a C++ benchmark more than a Ruby one because there are fewer things going on behind the scenes. — Sim, Apr 07 '13 at 18:00

score 0 · Answer 2 · answered Apr 07 '13 at 03:01

0

Of course the performance varies; if you insert 2, then 1, then 3 into an empty red-black tree, you never perform a rotation; if you insert 1, then 2, then 3, you must perform a rotation.

If you just want to build a red-black tree in the quickest possible way, sort the list, split it around the middle element, build red-black trees from both halves, and make the middle element the parent of the two halves. You do no rotations or other shenanigans here.

Like Alexey Frunze said, it can't vary by more than a small constant factor.

answered Apr 07 '13 at 03:01

tmyklebu

13,915
3
28
57

The question is not about whether any two given sequences of insertions could have variable performance. The answer to that is obviously yes. It is also not about how to build an RB tree. The question is about a random insertion sequence into an existing RB Tree with uniqueness restrictions. – Sim Apr 07 '13 at 03:29
@Sim: Yeah. My intent was to give a concrete example where the performance of a sorted sequence of insertions is bad while one-third of all random sequences is pretty good. – tmyklebu Apr 07 '13 at 03:50

RB Tree insertion order sensitivity

2 Answers2