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

[Koishi-Satori]

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.