<bit>: Is the __isa_available check for lzcnt worth the cost?
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 11.1k
- Forks
- 1.7k
- Avg merge
- 4d 15h
- Merged PRs (30d)
- 22
Description
std::bit_ceil emits quite a bit of assembly on x64. This seems to occur mostly due the branch in _Checked_x86_x64_countl_zero and to a lesser extent due to the branch in bit_ceil itself.
I've written a variant which produces a more compact result: https://godbolt.org/z/q4EEz83aW
(It also removes the extra branch on ARM64 by using conditional assignments.)
I've checked the PR that introduced the code (https://github.com/microsoft/STL/pull/795) and it appears as if the cost of this if condition wasn't discussed. The if condition generally makes sense though: bsr is costly on AMD CPUs (up to Zen3, 4 cycles/op latency), whereas lzcnt is very fast on any architecture (<= 1 cycle).
But it takes up 3 slots in the CPU's branch target buffer (contemporary hardware has ~4096 slots, newly added branches incur an extra 5-20 cycle latency), generates larger binaries after inlining and unfortunately the added instructions seem to add about ~5 cycles of latency themselves, offsetting the cost of bsr.
This makes me wonder: Should we drop the __isa_available check?
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in stl/inc/bit at _Checked_x86_x64_countl_zero and bit_ceil, then review the implementation history in PR 795. Compare the generated assembly and reported latency with the linked Godbolt variant across the relevant x64 and ARM64 paths; done means a justified decision on whether the __isa_available check should remain or change.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 28/100