←back to thread

Beautiful branchless binary search

(probablydance.com)
386 points ingve | 2 comments | 28 Apr 23 05:46 UTC | HN request time: 0.612s | source
Show context
SleepyMyroslav ◴[28 Apr 23 07:34 UTC] No.35738552[source]▶
If being branchless is important property of the algorithm then it is better to enforce it. Or at least test for it. If his GCC version will get an update and it will stop producing assembly that he wants no-one will ever know.

Which brings us back to regular discussion: C ( and C++ ) does not match hardware anymore. There is no real control over important properties of generated code. Programmers need tools to control what they write. Plug and pray compilation is not a solid engineering approach.

replies(6): >>35738629 #>>35738633 #>>35738677 #>>35738943 #>>35741009 #>>35745436 #
pjmlp ◴[28 Apr 23 07:47 UTC] No.35738633[source]▶
The myth that they match has been busted since at very least Pentium came to be.

A good read of Michael Abrash books explains that quite well, as does playing around Intel's VTune.

replies(2): >>35738709 #>>35738794 #
touisteur ◴[28 Apr 23 08:00 UTC] No.35738709[source]▶
For those looking for it https://www.jagregory.com/abrash-black-book

If some/most of the actual tricks are not up to date (ahem) the whole book is filled with techniques, stories, concepts... It's more than ever a Zen of optimization opus.

Can someone on HN close to him tell Michael Abrash, should he write again, whatever he wants, even gardening or vulkanstuff wrangling, he has guaranteed readers.

replies(1): >>35739282 #
1. liendolucas ◴[28 Apr 23 09:44 UTC] No.35739282[source]▶
Slightly off-topic... There's was a post in HN about how to set up a nice retro DOS development environment in linux. Despite searching for it I can't find it... If a gentle soul remembers it, much appreciated. I think a good DOS environment is a must in order to follow the book.
replies(1): >>35753660 #
2. touisteur ◴[29 Apr 23 15:12 UTC] No.35753660[source]▶
Yes a DOS environment is necessary if you want to follow through code examples, and tackle some of the optimization challenges (but mostly only try to beat the book if you have an actual 8086/286/386/486/Pentium I processor - or a cycle-precise emulator).

I read the whole book(s) thrice cover to cover without touching a computer (these were the days) in my teens and it was easy to follow, and full of nuggets for a young aspiring programmer. I had third-hand 8086, 386 and pentium 75 boxes at the time, but didn't open Turbo C before I'd finished the book, and it was to try and implement a bsp tree, then a whole 3d stereo (anaglyphs) software renderer (inspired by the book).