microsoft / microsoft/STL

`<__msvc_int128.hpp>`: The multiply operation function has performance issue

Open Beginner friendly
#6,405 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

performance
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.