40x Faster Binary Search

https://www.p99conf.io/session/40x-faster-binary-search/

by teleforce • 3 months ago

35 14 3 months ago

p99conf.io

rurban2• 3 months ago

Of course cache misses dominate over search or eytzinger.

Algorithmic courses are only for theoretical stone age computers.

mathisfun1235• 3 months ago

You're wrong but for the right reasons: all of academic software pedagogy is about "abstractions" because academics do not work for a living (they teach). That's why whenever I hear anyone use the word abstraction I bucket them under roughly the same category (people who write software that does not matter). Think about it: if you can afford to not care about cache misses or latencies or memory hierarchies or any of the other physical details which are extremely specific (the opposite of abstract) then you are writing code that has no constraints. no scale, no externalities.

rurban2• 3 months ago

Fine and dandy, but 40x faster trumps all algorithmic theories. You need to teach and implement cache-oblivious algos.

malnourish• 3 months ago

You use abstractions every day. Interfaces are abstractions. Perhaps you are simply being flippant, or rather abstract with your words.

coldtea3• 3 months ago

Almost everything you use came from academics and research labs.

coldtea3• 3 months ago

You'd be surprised.

sn9• 3 months ago

https://accidentallyquadratic.tumblr.com/

rerdavies• 3 months ago

Even my stone age Algorithmics course (50 years ago) covered cache-friendly algorithms. And one would hope that contemporary algorithmics courses at least touch on SIMD optimizations.

And one would hope that professional software engineers who are writing actual production code are doing more than relying on what was covered in their undergraduate algorithmics course. As a professional, I, personally, think that you have a duty to keep your education up to date by keeping up with academic advances (or at least being savvy enough to go to the literature when dealing like problems like this one). This particular academic paper provides a highly specific implementation of a specific algorithm. But it also provides about five techniques that I'm going to add to my profession arsenal of code-optimization techniques.

I do understand that general criticism that academic researchers do often seem to have curious underdeveloped coding skills. But that's not a criticism one can lay against the this particular academic (member of a research group at ETH Zurich, in case you missed that). He's providing code that concretely provides dramatic optimizations for AVX512 specifically, on a machine architecture that has 512-bit cache lines; but that doesn't detract from the generality of the techniques he's putting forward.

And probably worth mentioning that this is not an isolated instance. There are a number of papers I have used to write production code that provide similar levels of concrete detail for machine architectures that are no longer concretely relevant. A paper that documents a clever SIMD optimization for some IBM mainframe or another (not actually sure which) that provides performance improvements for DFTs that turned out to be usable on ARM NEON comes to mind.

These sorts of skills are what makes the difference between excellent software developers and merely mediocre ones over the arc of a career where one often has to go beyond merely what one was taught as an undergraduate.

tnelsond4• 3 months ago

Rambus goes VROOM Vroom.

Would all of this still be applicable for string comparisons? Would I have to hash my strings first?

40x Faster Binary Search

Related Stories