40x Faster Binary Search(p99conf.io)
p99conf.io
40x Faster Binary Search
https://www.p99conf.io/session/40x-faster-binary-search/
15 comments
Of course cache misses dominate over search or eytzinger.
Algorithmic courses are only for theoretical stone age computers.
Algorithmic courses are only for theoretical stone age computers.
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.
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.
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.
Almost everything you use came from academics and research labs.
lol you joking? point to a single piece of software on your computer that is maintained by academics/researchers ("came from" means absolutely nothing - this isn't a discussion about royalties or credit).
Weasely moving the goalposts. If we were stuck with mere "maintaining", you'd still be using the most primitive CPU and OS. Besides, once something is invented and shaped and studied, even a monkey can maintain it.
The point is the things that you get to use, and tech industry gets to maintain, come from research in the academic fields, in corporate R&D research labs from people with PhDs and everything (from Xerox's to Googles and Anthropics), and of course from direct parterships with universities as well.
Not as in "they created that in 1976", as in: the past, the current, and the next things you'll use, will come from that too. This includes anything from Algol, Lisp and OO and TeX to Monads, and Futures, and Prototype inheritance, and NNs and LLMs.
The point is the things that you get to use, and tech industry gets to maintain, come from research in the academic fields, in corporate R&D research labs from people with PhDs and everything (from Xerox's to Googles and Anthropics), and of course from direct parterships with universities as well.
Not as in "they created that in 1976", as in: the past, the current, and the next things you'll use, will come from that too. This includes anything from Algol, Lisp and OO and TeX to Monads, and Futures, and Prototype inheritance, and NNs and LLMs.
my guy this is the most bog standard defense of academia that exists - that they are the original progenitors of everything. it's not even true (industry pioneers plenty of things, especially in tech/swe) but even if it were, it would still be banal because by the same logic i might as well be worshipping prokaryotes instead of academics.
> in corporate R&D research labs from people with PhDs
lol tell me you've never been in a research group without telling me. hate to break it to you, as someone with a PhD and as someone who spent some time in an industry research group at the beginning of their career, almost nothing comes out of these groups in tech (the stuff that does see the light of day is the exception that proves the rule).
> in corporate R&D research labs from people with PhDs
lol tell me you've never been in a research group without telling me. hate to break it to you, as someone with a PhD and as someone who spent some time in an industry research group at the beginning of their career, almost nothing comes out of these groups in tech (the stuff that does see the light of day is the exception that proves the rule).
You use abstractions every day. Interfaces are abstractions. Perhaps you are simply being flippant, or rather abstract with your words.
i have no idea what that has to do with anything - i use a toilet every day as well.
Fine and dandy, but 40x faster trumps all algorithmic theories. You need to teach and implement cache-oblivious algos.
I think you misunderstood me - I agree with you. I'm pointing out that academics are incapable of that.
[deleted]
Would all of this still be applicable for string comparisons? Would I have to hash my strings first?