Date: Mon, 24 Mar 2025 09:31:26 +0000
On Mon, 24 Mar 2025, 09:15 Robin Savonen Söderholm via Std-Proposals, <
std-proposals_at_[hidden]> wrote:
> 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?
>
We do, just not in the standard.
https://www.delorie.com/djgpp/doc/libc/libc_621.html
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fpowi
Implementations should probably just optimise pow to powi when possible.
std-proposals_at_[hidden]> wrote:
> 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?
>
We do, just not in the standard.
https://www.delorie.com/djgpp/doc/libc/libc_621.html
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fpowi
Implementations should probably just optimise pow to powi when possible.
Received on 2025-03-24 09:31:43