Benchmarks of different segment tree implementations

Revision en2, by pavelthebest, 2022-06-30 23:40:01

Sometimes I wonder, what implementation of a segment tree to use. Usually, I handwave that some will suit, and that works in most of the cases.

But today I decided to back up the choice with some data and I ran benchmarks against 4 implementations:

  • Simple recursive divide-and-conquer implementation
    Code
  • Optimized recursive divide-and-conquer, which does not descend into apriori useless branches
    Code
  • Non-recursive implementation (credits: https://codeforces.com/blog/entry/18051)
    Code
  • Fenwick Tree
    Code

All implementations are able to:

  • get(l, r): get sum on a segment (half-interval) $$$[l; r)$$$
  • update(i, x): add $$$x$$$ to the element by index $$$i$$$

Here are the results:

Note: I decided not to apply any addition-specific optimizations so that with minor modifications the data structures could be used for any supported operations.

I generated queries the following way:

  • Update: generate random index (rnd() % size) and number
  • Query: at first, generate random length (rnd() % size + 1), then generate a left border for that length

Benchmarking source code. Note that ideally you should disable frequency scaling and close any applications that might disrupt the benchmark (basically, the more you close — the better).

Plot-generating Python script

My benchmarking data in case you want to do some more plotting/comparing.

I compiled the benchmark with #pragma GCC optimize("O3") on GNU GCC 11.3.0, and ran it with the CPU fixed on 2.4 GHz without the desktop environment open.

This is probably my first useful contribution so any suggestions/improvements are welcome.

Tags benchmark, segment tree, implementations, whatever

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English pavelthebest 2022-07-01 18:47:14 227 Benchmark data updated: benchmark process was pinned on a single CPU core
ru4 Russian pavelthebest 2022-07-01 18:41:47 205 Результаты обновлены: бенчмарк был запущен с процессом "прибитым" к одному ядру процессора
en3 English pavelthebest 2022-07-01 00:42:53 7 Tiny change: '>\n<li>\n`update(i, x)`: a' -> '>\n<li>\n`add(i, x)`: a'
ru3 Russian pavelthebest 2022-07-01 00:42:11 7 Мелкая правка: '>\n<li>\n`update(i, x)`: п' -> '>\n<li>\n`add(i, x)`: п'
ru2 Russian pavelthebest 2022-06-30 23:40:36 4 (опубликовано)
en2 English pavelthebest 2022-06-30 23:40:01 8 (published)
ru1 Russian pavelthebest 2022-06-30 23:39:25 7722 Первая редакция перевода на Русский (сохранено в черновиках)
en1 English pavelthebest 2022-06-30 23:27:37 7598 Initial revision (saved to drafts)