3 ms·
For the given assembly from the blog post loop: lea (%rdx,%rax,4),%rcx cmp (%rcx),%esi cmovg %rcx,%rdx shr %rax jne
by 2102922286 3y ago
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_trace.html 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.
- jeffreygoesto 3y agoHow do you get such am image please?
- 2102922286 3y agohttps://uops.info/uiCA.html https://uops.info/uiCA.html it's really cool!!
- kevingadd 3y agoWow, 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.