`<__msvc_int128.hpp>`: The multiply operation function has performance issue
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 11.2k
- Forks
- 1.7k
- Avg merge
- 4d 15h
- Merged PRs (30d)
- 22
Description
Summary
std::_Signed128::operator* in <__msvc_int128.hpp> perform sign-normalizes before multiplying, but it is unnecessary and will cause performance issue.
Detail
The current implementation sign-normalizes both operands before multiplying, and on MSVC x64 /O2 the whole operator* function compiles to roughly 40+ instructions.
I've tried to implement a version without sign handling, the new version has same behavior and will not break any ABI. The new version without sign-normalizing is more faster than current version in <__msvc_int128.hpp>.
Here shows the differ: https://godbolt.org/z/Y4x8Pq7Ka, the version without sign handling only contains 7 mov + 1 mul + 2 imul and 2 add instructions, which are more faster.
The new version:
_NODISCARD friend constexpr _Signed128 operator*(_Signed128 _Left, _Signed128 _Right) noexcept {
// The low 128 bits of a two's-complement product equal the unsigned product, so the sign normalization in the old
// implementation was unnecessary.
_Signed128 _Result;
_Result._Word[0] = _UMul128(_Left._Word[0], _Right._Word[0], _Result._Word[1]);
_Result._Word[1] += _Left._Word[1] * _Right._Word[0];
_Result._Word[1] += _Left._Word[0] * _Right._Word[1];
return _Result;
}
Measurements
Benchmark on MSVC x64, Release, walking a 1,000,000-pair vector of random operands:
- std::_Signed128 (current): 14.5 ns per multiply
- new 128-bit multiply: 2.37 ns per multiply
The new 128-bit multiply is implemented as eirin::ext::int128 in my Eirin Math Library, which has the same behavior as the version without sign handling mentioned before. And I believe this could be a strong evidence that the new version is faster than the old one.
Notes
- Same semantics, no ABI change; the multiplication core is identical to _Base128::_Multiply.
- I can attach the benchmark (including a faithful replica of the old implementation) if useful.
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 <__msvc_int128.hpp> at std::_Signed128::operator* and compare its current sign normalization with _Base128::_Multiply. Check the proposed unsigned-product behavior for signed operands, then inspect MSVC x64 optimized output and benchmark results. Done means preserving semantics and ABI while confirming the multiply is measurably faster.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- tooling
- Issue type
- Bug
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 78/100