From 586952f4cefd809b7becd16c6d1e751ea923adfd Mon Sep 17 00:00:00 2001 From: Jorg Brown Date: Mon, 4 Nov 2019 19:00:23 -0800 Subject: [PATCH] Optimize std::midpoint for integers Same idea as the current algorithm, that is, add (half of the difference between a and b) to a. But we use a different technique for computing the difference: we compute b - a into a pair of integers that are named "sign_bit" and "diff". We have to use a pair because subtracting two 32-bit integers produces a 33-bit result. Computing half of that is a simple matter of shifting diff right by 1, and adding sign_bit shifted left by 31. llvm knows how to do that with one instruction: shld. The only tricky part is that if the difference is odd and negative, then shifting it by one isn't the same as dividing it by two - shifting a negative one produces a negative one, for example. So there's one more adjustment: if the sign bit and the low bit of diff are one, we add one. For a demonstration of the codegen difference, see https://godbolt.org/z/7ar3K9 , which also has a built-in test. Differential Revision: https://reviews.llvm.org/D69459 --- libcxx/include/numeric | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) diff --git a/libcxx/include/numeric b/libcxx/include/numeric index 854bbfa..11a5641 100644 --- a/libcxx/include/numeric +++ b/libcxx/include/numeric @@ -532,17 +532,14 @@ midpoint(_Tp __a, _Tp __b) noexcept _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK { using _Up = std::make_unsigned_t<_Tp>; + constexpr _Up __bitshift = std::numeric_limits<_Up>::digits - 1; - int __sign = 1; - _Up __m = __a; - _Up __M = __b; - if (__a > __b) - { - __sign = -1; - __m = __b; - __M = __a; - } - return __a + __sign * _Tp(_Up(__M-__m) >> 1); + _Up __diff = _Up(__b) - _Up(__a); + _Up __sign_bit = __b < __a; + + _Up __half_diff = (__diff / 2) + (__sign_bit << __bitshift) + (__sign_bit & __diff); + + return __a + __half_diff; } -- 2.7.4