Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Beautiful branchless binary search

probablydance.com

Post reply on HN
Print view View original

101–110 of 198 posts

Re: Beautiful branchless binary search

#101

Post by dist1ll »

SleepyMyroslav wrote: post #42

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 contr…

> 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.

Not sure how one relates to the other. Do you want more fine-grained control over emitted assembly? Or do you want a general-purpose CPU that exposes microarchitecture details (i.e. "matching hardware")?

Only the former can be solved by tooling.

Re: Beautiful branchless binary search

#102

Post by tomsmeding »

josephg wrote: post #100
eska wrote: post #86

Earlier quoted context omitted.

The compiler will outright remove bounds checks that are implied by previous bounds checks. It is a common low level optimization to add a wide boundary check in the beginning to avoid successive smaller bounds checks.

True. But if binary size is anything to go by, an awful lot of bounds checks still end up in the code.

Doesn't a rust binary also include a whole lot of standard library? C compilers assume that libc is available, a rust compiler is hardly going to assume that rust's libstd is installed on a random user's machine.

Re: Beautiful branchless binary search

#103

Post by zulu-inuoe »

pizza234 wrote: post #27

Some information on the CMOV can be found on the Intel Optimization Reference Manual ( https://cdrdv2-public.intel.com/671488/248966-046A-software-... ). Torvalds was famously critical of it ( https://yarchive.net/comp/linux/cmov.html); part of the criticism is now moot though, due to low latencies on modern processors (it seems 1 cycle or less, although the instruction consumes internal flags). His idea seems to be…

404 on that Torvalds link

Re: Beautiful branchless binary search

#104

Post by chaboud »

“Those spikes for std::lower_bound are on powers of two, where it is somehow much slower. I looked into it a little bit but can’t come up with an easy explanation. The Clang version has the same spikes even though it compiles to very different assembly.”

I saw this and immediately went “oh, those look like Intel hardware”.

Intel uses 12-bit memory port quick addressing in their hardware, resulting in an issue known as “4K Aliasing”. When addresses are the same modulo 4K, it causes a collision that has to be mitigated by completing the associated prior memory operation to free up the use of the address in the load/store port system, effectively serializing operations and making performance very dependent on the data stride.

I first bumped up against this when running vertical passes of image processing algorithms that got very slow at certain image sizes, a problem that could be avoided by using an oversized buffer and correspondingly oversized per-line “pitch” to diagonally offset aliased addresses (at a small cost to inter-line cache line overlap).

Re: Beautiful branchless binary search

#105

Post by pizza234 »

zulu-inuoe wrote: post #103
pizza234 wrote: post #27

Some information on the CMOV can be found on the Intel Optimization Reference Manual ( https://cdrdv2-public.intel.com/671488/248966-046A-software-... ). Torvalds was famously critical of it ( https://yarchive.net/comp/linux/cmov.html); part of the criticism is now moot though, due to low latencies on modern processors (it seems 1 cycle or less, although the instruction consumes internal flags). His idea seems to be…

404 on that Torvalds link

The HN renderer is rendering the closing round bracket and semicolon as part of the HTML link, which is unfortunate for this case, but good to know :)

Re: Beautiful branchless binary search

#106

Post by waynecochran »

dist1ll wrote: post #101
SleepyMyroslav wrote: post #42

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 contr…

> 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. Not sure how one relates to the other. Do you want more fine-grained control over emitted assembly? Or do you want a general-purpose CPU that e…

C++ could add a an explicit conditional move I suppose. `x` and `y` types would have to be restrictive:

      x = std::cmove(y,flag);
The compiler would be slightly mrve compelled to use a hardware conditional move than in the following case:

      if (flag) x = y;
The other option is to do something more like CUDA / SIMD kernels do ... every line gets executed but each each instruction inside the "false branch" becomes a no-op. Of course this requires hardware support.

Re: Beautiful branchless binary search

#107

Post by usefulcat »

> In fact in Clang branchless_lower_bound is slower than std::lower_bound

That's strange, I've profiled it and I find that branchless_lower_bound is still faster than std::lower_bound using clang14, just not as fast as with gcc12 (on Intel Broadwell). I'm using gcc's libstdc++ in both cases, maybe he was using libc++ with clang?

Edit:

Replacing the contents of the for loop with the following improves performance for clang but reduces performance for gcc:

    const size_t increment[] = { 0, step };
    begin += increment[compare(begin[step], value)];

Re: Beautiful branchless binary search

#108

Post by vidarh »

martincmartin wrote: post #89
WithinReason wrote: post #61

Earlier quoted context omitted.

So binary search should actually not be binary but... octary?

Yes, these are the same issues faced by databases on spinning rust disks. The solution was to figure out how many keys fit in a disk block / cache line, let's call it k, then have a k-ary tree instead of a binary tree. This is called a B-tree. https://en.wikipedia.org/wiki/B-tree With caching on modern CPUs, as opposed to databases on disks, there are multiple levels of caching and you may not know the size of the ca…

But note that, as per their benchmark against B-tree's, in memory the cost of the memory fetch is sufficiently small that the cost of the comparisons might wipe out the savings.

When retrieving from disk you have far more cycles to work with before less disk-read sized blocks can get close to competitive.

Re: Beautiful branchless binary search

#109

Post by msla »

zulu-inuoe wrote: post #103
pizza234 wrote: post #27

Some information on the CMOV can be found on the Intel Optimization Reference Manual ( https://cdrdv2-public.intel.com/671488/248966-046A-software-... ). Torvalds was famously critical of it ( https://yarchive.net/comp/linux/cmov.html); part of the criticism is now moot though, due to low latencies on modern processors (it seems 1 cycle or less, although the instruction consumes internal flags). His idea seems to be…

404 on that Torvalds link

https://yarchive.net/comp/linux/cmov.html

Re: Beautiful branchless binary search

#110

Post by msla »

pizza234 wrote: post #27

Some information on the CMOV can be found on the Intel Optimization Reference Manual ( https://cdrdv2-public.intel.com/671488/248966-046A-software-... ). Torvalds was famously critical of it ( https://yarchive.net/comp/linux/cmov.html); part of the criticism is now moot though, due to low latencies on modern processors (it seems 1 cycle or less, although the instruction consumes internal flags). His idea seems to be…

https://yarchive.net/comp/linux/cmov.html
Post reply on HN