sslotin's blog

7x faster drop-in replacement for std::lower_bound
By sslotin, 5 years ago, In English

http://algorithmica.org/en/b-tree

Hi, it's me again. A couple of days ago I published a post about speeding up binary search by rearranging memory in a way that allows prefetching, which is basically a way of trading off memory bandwidth for latency.

As noted in the comments, it had a noisy neighbors issue when tested on online judges, as different solutions evaluating on the same machine could compete for the same memory bandwidth. The speedup was like 2x-3x (and very volatile) on Codeforces while on my laptop and my dedicated server it was 4-5x, depending on the array sizes.

And so I rewrited it using B-tree layout instead, and it worked, because it bluntly requires 4x less memory reads. It is still quite volatile on CF—compare this (6.6x) and this (5.1x)—but I've never seen it drop below 3x on adequate array sizing (yes, the title is a bit clickbaity; I think the average speedup is around 5x).

There are two implementations:

  1. One is straightforward and uses nothing fancy
  2. The other is compute-optimized with AVX2 instructions and is ~30% faster, but doesn't work with older hardware (notably ideone and Yandex.Contest servers)

For more details, check the article.

Also, it would be really cool if someone could figure out a way to make compiler produce an autovectorized version of the faster one, so that it could be more easily extendable. It's weird and annoying that the compiler can't produce these 3 lines of code.

  • Vote: I like it
  • +63
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Actually, it isn't full replacement of lower_bound, because, for finding index in this approach we need to store pair<int,int>, where index is second argument of pair.

In AVX2 approach we need to divide one block in vector [x0 x1 x2 x3 ... | i0 i1 i2 i3 ...], where first half is values, second half is indexes.

SSE4.2 can be used at the Yandex.Contest with 128-bit registers.

UPD. Maybe we can calculate index in original sorted array based on the position in Btree?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    I wrote a new version that is much faster and also doesn't require any additional work for finding indices (in fact, it is a few cycles faster if you only need the index).

    I've actually made several variants, all based on structures I'm going to call S-trees and S+ trees, which are modifications of B-trees and B+ trees. The fastest one achieves 12-15x speedup over std::lower_bound on small arrays (that fit in cache) and 7-8x speedup on large arrays (>1e6). I am working on a version for Windows / GCC so that it can run on CodeForces, but speedups are not that large yet (~10x / ~6x, because GCC sucks).

    This comment is sort of a teaser. I will publish an updated article sometime next week, after a few more minor optimizations I have in mind.

    → Reply