Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

<numeric>: Make gcd() faster with constexpr bitscan intrinsics #298

Closed
StephanTLavavej opened this issue Nov 15, 2019 · 0 comments · Fixed by #665
Closed

<numeric>: Make gcd() faster with constexpr bitscan intrinsics #298

StephanTLavavej opened this issue Nov 15, 2019 · 0 comments · Fixed by #665
Labels
fixed Something works now, yay! performance Must go faster

Comments

@StephanTLavavej
Copy link
Member

Our gcd() implementation contains the following workaround:

STL/stl/inc/numeric

Lines 847 to 860 in 58bb49d

template <class _Unsigned>
constexpr unsigned long _Stl_bitscan_forward(_Unsigned _Mask) noexcept {
// find the index of the least significant set bit (_BitScanForward isn't constexpr... yet :))
static_assert(is_unsigned_v<_Unsigned>, "Bitscan only works on bits");
unsigned long _Count = 0;
if (_Mask != 0) {
while ((_Mask & 1U) == 0) {
_Mask >>= 1;
++_Count;
}
}
return _Count;
}

For #25 (WG21-P0553 <bit> Rotating And Counting Functions), we're getting compiler support for constexpr bitscans (with different intrinsic names). We should use this in gcd().

Note that because <bit> is a C++20 header, we can't include it from <numeric>, nor can we use its non-_Ugly functions to implement C++17 features like gcd(). However, we can use the compiler intrinsics directly, or define _Ugly wrappers for them in centralized headers.

Also tracked by Microsoft-internal VSO-597250.

@StephanTLavavej StephanTLavavej added enhancement Something can be improved performance Must go faster labels Nov 15, 2019
@StephanTLavavej StephanTLavavej removed the enhancement Something can be improved label Feb 6, 2020
@StephanTLavavej StephanTLavavej added the fixed Something works now, yay! label Apr 12, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
fixed Something works now, yay! performance Must go faster
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant