sslotin's blog

By sslotin, 2 months 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
  • +28
  • Vote: I do not like it