Beautiful branchless binary search

Re:Beautiful branchless binary search by 2102922286 on Friday April 28, 2023 @02:48AM (#35738262)

For the given assembly from the blog post

    loop:
        lea (%rdx,%rax,4),%rcx
        cmp (%rcx),%esi
        cmovg %rcx,%rdx
        shr %rax
        jne loop

Here's a simulated CPU trace on Intel skylake: https://uica.uops.info/tmp/2de9d862d05d482ebed576d7e3923b93_...

Note that this tracer makes the assumption that all memory loads are in cache (otherwise the memory lookup will dominate). So bear that in mind for this code, especially since memory reads will likely dominate the cost of a binary search.

Regardless, it appears that the cost of conditional move is not the source of bottleneck.

[ Parent | on HN ]

Re:Beautiful branchless binary search by jeffreygoesto on Friday April 28, 2023 @02:54AM (#35738304)

How do you get such am image please?

[ Parent | on HN ]

Re:Beautiful branchless binary search by 2102922286 on Friday April 28, 2023 @03:03AM (#35738352)

https://uops.info/uiCA.html it's really cool!!

[ Parent | on HN ]

Re:Beautiful branchless binary search by kevingadd on Friday April 28, 2023 @03:03AM (#35738355)

Wow, the dispatch queue is so deep! The trace makes a lot of sense, thanks for sharing it. I must have been unclear if it sounded like I was saying cmov was a bottleneck - my argument is just that it's not going to be especially faster than a branch in the general case.

Great point that memory reads are going to dominate a binary search - at that point the CPU will be spending a lot more time waiting for memory than it is spending executing your branches or cmovs.

[ Parent | on HN ]