Date: Mon, 24 Mar 2025 10:08:19 +0100
Hi!
Unsure if this should be a proposal here or if it is more of a
implementation detail, but from what I can read upon cppreference it seems
to be correct to float it here.
Background/Motivation:
I have seen and experienced time when you want to do something like
<double> ^ <some int larger than 2 but less than say 100>. And in general
there are two different approaches here: use `std::pow(...)` or roll your
own manual integer-pow function. The thing is that std::pow(...) can be
slower than just doing a naive loop with multiplications for small
integers, but the roll will quickly become slower as you approach higher
exponents (I think my desktop showed signs of serious degradation at
between 32 and 64 values in exponents).
I propose a slightly different integer-exponent pow that has a O(log2(n))
complexity (in contrast to the naive loop that as O(n), where 'n' here is
the exponent). Some quick benchmarks showed that this implementation seemed
to be as fast as the naive solution at low exponents and did not seem to
get worse than std::pow for large N. An implementation can be found here:
dooc-template-library/lib/math/inc/dtl/lpow.hpp at main ·
doocman/dooc-template-library · GitHub
<https://github.com/doocman/dooc-template-library/blob/main/lib/math/inc/dtl/lpow.hpp>
, the benchmarks was here:
dooc-template-library/lib/math/benchmarks/lpow.bb.cpp at main ·
doocman/dooc-template-library · GitHub
<https://github.com/doocman/dooc-template-library/blob/main/lib/math/benchmarks/lpow.bb.cpp>
and a godbolt link: https://godbolt.org/z/Khz9K385P
In addition to speed, the new power-function has the advantage of being
usable with any type that supports multiplication (and division in the
negative exponent case).
Note: I am sure there are certain corner-cases still left with the
reference implementation, but I still think that it can be useful to better
merge readability with performance. And there could be further
optimisations to do to improve the speed further (looking into how branches
are made in the assembly, vectorising operations (can probably only be made
on certain types)).
Proposal 1:
The first version of the proposal is to add an alternative to std::pow that
could be named like `std::lpow` or `std::powi` with the signature:
```c++
constexpr auto lpow(/*multiplicable*/ auto b, std::integral auto e)
requires(!std::is_signed_v<decltype(e)> || /*divisable<decltype(b)>) ->
decltype(b) {...}
```
. Then linters in user-code can identify places where an integer (or at
least integer literal/compile time integer) is used in a std::pow and
suggest using the new function.
Proposal 2:
The second version would be to simply overload the existing `std::pow` with
the aforementioned signature and let the compiler automatically use the
appropriate overload. I don't have this as the first version because there
could be cornercases in behavious that I am missing, causing this to become
a breaking change. For example, the return-type of std::pow(float,
std::int_least64_t) seems to return double on both GCC and MSVC while
current reference returns a float.
Proposal 3:
An alternative solution could be to incorporate both versions but with a
change: the std::pow should have it's returntype unchanged from todays
implementation.
Ending
Now I can't help but ending with a question: this 'power strategy' feels
like it should not be a too novel approach, so is there a reason why we
don't already have something like this?
Unsure if this should be a proposal here or if it is more of a
implementation detail, but from what I can read upon cppreference it seems
to be correct to float it here.
Background/Motivation:
I have seen and experienced time when you want to do something like
<double> ^ <some int larger than 2 but less than say 100>. And in general
there are two different approaches here: use `std::pow(...)` or roll your
own manual integer-pow function. The thing is that std::pow(...) can be
slower than just doing a naive loop with multiplications for small
integers, but the roll will quickly become slower as you approach higher
exponents (I think my desktop showed signs of serious degradation at
between 32 and 64 values in exponents).
I propose a slightly different integer-exponent pow that has a O(log2(n))
complexity (in contrast to the naive loop that as O(n), where 'n' here is
the exponent). Some quick benchmarks showed that this implementation seemed
to be as fast as the naive solution at low exponents and did not seem to
get worse than std::pow for large N. An implementation can be found here:
dooc-template-library/lib/math/inc/dtl/lpow.hpp at main ·
doocman/dooc-template-library · GitHub
<https://github.com/doocman/dooc-template-library/blob/main/lib/math/inc/dtl/lpow.hpp>
, the benchmarks was here:
dooc-template-library/lib/math/benchmarks/lpow.bb.cpp at main ·
doocman/dooc-template-library · GitHub
<https://github.com/doocman/dooc-template-library/blob/main/lib/math/benchmarks/lpow.bb.cpp>
and a godbolt link: https://godbolt.org/z/Khz9K385P
In addition to speed, the new power-function has the advantage of being
usable with any type that supports multiplication (and division in the
negative exponent case).
Note: I am sure there are certain corner-cases still left with the
reference implementation, but I still think that it can be useful to better
merge readability with performance. And there could be further
optimisations to do to improve the speed further (looking into how branches
are made in the assembly, vectorising operations (can probably only be made
on certain types)).
Proposal 1:
The first version of the proposal is to add an alternative to std::pow that
could be named like `std::lpow` or `std::powi` with the signature:
```c++
constexpr auto lpow(/*multiplicable*/ auto b, std::integral auto e)
requires(!std::is_signed_v<decltype(e)> || /*divisable<decltype(b)>) ->
decltype(b) {...}
```
. Then linters in user-code can identify places where an integer (or at
least integer literal/compile time integer) is used in a std::pow and
suggest using the new function.
Proposal 2:
The second version would be to simply overload the existing `std::pow` with
the aforementioned signature and let the compiler automatically use the
appropriate overload. I don't have this as the first version because there
could be cornercases in behavious that I am missing, causing this to become
a breaking change. For example, the return-type of std::pow(float,
std::int_least64_t) seems to return double on both GCC and MSVC while
current reference returns a float.
Proposal 3:
An alternative solution could be to incorporate both versions but with a
change: the std::pow should have it's returntype unchanged from todays
implementation.
Ending
Now I can't help but ending with a question: this 'power strategy' feels
like it should not be a too novel approach, so is there a reason why we
don't already have something like this?
Received on 2025-03-24 09:15:14