Optimize `checked_ilog` and `pow` when `base` is a power of two #147250

Kmeakin · 2025-10-02T00:33:17Z

Optimize checked_ilog and pow when the base is a power of two

rustbot · 2025-10-02T00:33:22Z

rustbot has assigned @scottmcm.
They will have a look at your PR within the next two weeks and either review your PR or reassign to another reviewer.

Use r? to explicitly pick a reviewer

workingjubilee · 2025-10-02T02:09:34Z

does this affect the codegen in practical circumstances? I would expect even a fairly weak optimizer to perform this optimization, making us hand-coding it irrelevant and potentially even harmful because we introduce more conditional logic to chew through.

Kmeakin · 2025-10-02T02:21:24Z

does this affect the codegen in practical circumstances?

It replaces a loop by some bit manipulations. Whether anyone actually calls either function with a compile-time known, power of 2 base is another question. But it can't hurt, since it is guarded by is_statically_known.

I would expect even a fairly weak optimizer to perform this optimization, making us hand-coding it irrelevant

No, in either function, LLVM is not able to see that the loop is performing a log/pow and apply the identities: https://godbolt.org/z/6vMsxc9Kh

and potentially even harmful because we introduce more conditional logic to chew through.

They're guarded by is_statically_known so will be ignored if the base is not known at compile-time

workingjubilee · 2025-10-02T02:40:04Z

No, in either function, LLVM is not able to see that the loop is performing a log/pow and apply the identities: https://godbolt.org/z/6vMsxc9Kh

...then I'm kinda surprised! Nice catch.

library/core/src/num/uint_macros.rs

scottmcm · 2025-10-02T06:01:57Z

does this affect the codegen in practical circumstances?

Would be good to have codegen tests to demonstrate what this is doing -- especially since that way there's a way for people to try removing the special cases later if they think that LLVM no longer needs them.

library/core/src/num/uint_macros.rs

workingjubilee · 2025-10-05T18:10:15Z

thanks for the codegen tests!

Kmeakin · 2025-10-05T21:25:43Z

@rustbot ready

Kmeakin · 2025-10-10T22:51:45Z

@scottmcm ping?

scottmcm · 2025-10-14T02:41:27Z

tests/codegen-llvm/ilog_known_base.rs

+#[no_mangle]
+pub fn checked_ilog16(val: u32) -> Option<u32> {
+    // CHECK: %[[ICMP:.+]] = icmp ne i32 %val, 0
+    // CHECK: %[[CTZ:.+]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 %val, i1 true)


This isn't really this PR's problem, but consider filing an LLVM bug (assuming it's also true in trunk) that this range is wider than necessary -- we're passing true for is_zero_poison https://llvm.org/docs/LangRef.html#llvm-ctlz-intrinsic so the range here should be range(i32 0, 32).

The range attribute is too large, but it seems LLVM is still able to propagate the knowledge:

https://godbolt.org/z/dzxfGnhMf

scottmcm

The code here is looking good, but can you make sure there's normal runtime behaviour tests for it too? Notably, after the base conversation (that's fixed in the code) it made me think that that's not currently covered by any tests, so we should have something -- maybe just add to the # Examples that it returns None for base zero or one? (They seem like perfectly reasonable and helpful examples, in addition to giving coverage for this stuff.)

And maybe add some should_panic tests to ensure that the overflow checking is still correct for pow when overflow checks are enabled?

View changes since this review

Kmeakin · 2025-11-10T00:41:50Z

@scottmcm ping?

library/core/src/num/uint_macros.rs

scottmcm

I still have concerns about the correctness of this; see above.

View changes since this review

rustbot · 2025-11-19T19:56:56Z

Reminder, once the PR becomes ready for a review, use @rustbot ready.

if base == 2 ** k, then log(base, n) == log(2, n) / k

rustbot · 2025-11-26T22:48:39Z

This PR was rebased onto a different main commit. Here's a range-diff highlighting what actually changed.

Rebasing is a normal part of keeping PRs up to date, so no action is needed—this note is just to help reviewers.

Increase test coverage to check all interesting edge cases and all variants.

`strict_pow` can be implemented in terms of `checked_pow`, `wrapping_pow` can be implemented in terms of `overflowing_pow`, and `pow` can be implemented in terms of `strict_pow` or `wrapping_pow`.

Copy the optimization that unrolls the loop from `pow` to `checked_pow` and `overflowing_pow`.

if base == 2 ** k, then (2 ** k) ** n == 2 ** (k * n) == 1 << (k * n)

Kmeakin · 2025-11-27T17:02:53Z

@rustbot ready

quaternic · 2025-12-05T21:53:19Z

library/core/src/num/uint_macros.rs

+            if intrinsics::is_val_statically_known(exp) {
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        (acc, tmp_overflow) = acc.overflowing_mul(base);
+                        overflow |= tmp_overflow;
+                    }
+                    exp /= 2;
+                    (base, tmp_overflow) = base.overflowing_mul(base);
+                    overflow |= tmp_overflow;
+                }
+
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
+                (acc, tmp_overflow) = acc.overflowing_mul(base);
+                overflow |= tmp_overflow;
+                return (acc, overflow);
+            }


So, here's an idea: If either input is statically known, checking for overflow could be folded into a single range check on the other input. Doing so would allow all of the variants to delegate to wrapping_pow.

Quick test that this would help:
https://rust.godbolt.org/z/oEWWGx4f9

Hmm. That should be easy enough when base is known: overflow = exp > $T::MAX.ilog(base). If the exp is known, that would be harder: overflow = base > $T::MAX.nth_root(exp), but we don't have a way of calculating the nth root of an integer

For any exp >= T::BITS, the condition is just base > 1, which means that a pre-computed array of length T::BITS would be sufficient. Computing them at compile time should be reasonable, but it could be too much additional complexity to this PR.

You could maybe factor out a helper like

const fn statically_cheap_overflow_condition(base, exp) -> Option<bool> { if intrinsics::is_val_statically_known(base) { Some(exp > u64::MAX.ilog(base)) } else { None } }

The known exp case would be easy to add later.

Callsites can then do

if let Some(overflow) = statically_cheap_overflow_condition(base, exp) { // delegate to wrapping_pow where necessary, as overflow is already known } else { // the usual runtime thing }

Although, I suppose it's really the known exponent cases that would benefit the most by removing the need for having the LLVM-unrollable blocks duplicated for each variant.

In case it's of use, here's the code I tested with: https://godbolt.org/z/5svnKM7hM
(Includes computing the roots for unsigned types. Signed would have some additional complications)

I think the PR is getting complicated enough already. Let's get this merged first, then we can further optimise in a follow up

I think the PR is getting complicated enough already. Let's get this merged first, then we can further optimise in a follow up PR

rustbot assigned scottmcm Oct 2, 2025

rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. T-libs Relevant to the library team, which will review and decide on the PR/issue. labels Oct 2, 2025

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch from 8f19ce6 to e5ca8cd Compare October 2, 2025 01:31

This comment has been minimized.

Sign in to view

Kmeakin changed the title ~~Optimize checked_ilog when base is a power of two~~ Optimize checked_ilog and pow when base is a power of two Oct 2, 2025

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch 2 times, most recently from 2faa397 to abb7f32 Compare October 2, 2025 02:38

scottmcm reviewed Oct 2, 2025

View reviewed changes

library/core/src/num/uint_macros.rs Outdated Show resolved Hide resolved

scottmcm reviewed Oct 2, 2025

View reviewed changes

library/core/src/num/uint_macros.rs Outdated Show resolved Hide resolved

scottmcm added S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. and removed S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. labels Oct 2, 2025

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch from abb7f32 to 9ab0f63 Compare October 2, 2025 23:13

nikic reviewed Oct 3, 2025

View reviewed changes

library/core/src/num/uint_macros.rs Outdated Show resolved Hide resolved

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch from 9ab0f63 to 1d0ac82 Compare October 3, 2025 21:16

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch from 1d0ac82 to c84b99e Compare October 5, 2025 18:29

rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. and removed S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. labels Oct 5, 2025

scottmcm reviewed Oct 14, 2025

View reviewed changes

scottmcm requested changes Oct 14, 2025

View reviewed changes

rustbot added S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. and removed S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. labels Oct 14, 2025

scottmcm reviewed Nov 19, 2025

View reviewed changes

library/core/src/num/uint_macros.rs Outdated Show resolved Hide resolved

scottmcm requested changes Nov 19, 2025

View reviewed changes

rustbot added S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. and removed S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. labels Nov 19, 2025

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch from 53449c9 to a3a4b22 Compare November 22, 2025 01:30

This comment has been minimized.

Sign in to view

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch 2 times, most recently from be3ec71 to 5251791 Compare November 22, 2025 03:22

This comment has been minimized.

Sign in to view

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch 2 times, most recently from e8a603e to c2f36c5 Compare November 23, 2025 17:31

This comment has been minimized.

Sign in to view

optimize: checked_ilog when base is a power of two

9726f4d

if base == 2 ** k, then log(base, n) == log(2, n) / k

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch from c2f36c5 to 2f902f7 Compare November 26, 2025 22:48

This comment has been minimized.

Sign in to view

Kmeakin added 3 commits November 27, 2025 00:23

refactor: Increase test coverage for pow

2395dba

Increase test coverage to check all interesting edge cases and all variants.

refactor: Deduplicate pow implementations

fc24178

`strict_pow` can be implemented in terms of `checked_pow`, `wrapping_pow` can be implemented in terms of `overflowing_pow`, and `pow` can be implemented in terms of `strict_pow` or `wrapping_pow`.

optimize: pow if exp is statically known

9988dcd

Copy the optimization that unrolls the loop from `pow` to `checked_pow` and `overflowing_pow`.

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch from 2f902f7 to 659e612 Compare November 27, 2025 01:22

optimize: pow when base is a power of two

b1b3348

if base == 2 ** k, then (2 ** k) ** n == 2 ** (k * n) == 1 << (k * n)

Kmeakin force-pushed the km/optimize-ilog-base-power-of-two branch from 659e612 to b1b3348 Compare November 27, 2025 16:02

rustbot added S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. and removed S-waiting-on-author Status: This is awaiting some action (such as code changes or more information) from the author. labels Nov 27, 2025

quaternic reviewed Dec 5, 2025

View reviewed changes

Kmeakin requested a review from scottmcm January 11, 2026 00:11

Uh oh!

Optimize checked_ilog and pow when base is a power of two #147250

Are you sure you want to change the base?

Optimize checked_ilog and pow when base is a power of two #147250

Conversation

Kmeakin commented Oct 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

rustbot commented Oct 2, 2025

Uh oh!

This comment has been minimized.

workingjubilee commented Oct 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Kmeakin commented Oct 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

workingjubilee commented Oct 2, 2025

Uh oh!

Uh oh!

Uh oh!

scottmcm commented Oct 2, 2025

Uh oh!

Uh oh!

workingjubilee commented Oct 5, 2025

Uh oh!

Kmeakin commented Oct 5, 2025

Uh oh!

Kmeakin commented Oct 10, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

scottmcm left a comment • edited by rustbot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Kmeakin commented Nov 10, 2025

Uh oh!

Uh oh!

scottmcm left a comment • edited by rustbot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rustbot commented Nov 19, 2025

Uh oh!

This comment has been minimized.

This comment has been minimized.

This comment has been minimized.

This comment has been minimized.

rustbot commented Nov 26, 2025

Uh oh!

This comment has been minimized.

Kmeakin commented Nov 27, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

Optimize `checked_ilog` and `pow` when `base` is a power of two #147250

Optimize `checked_ilog` and `pow` when `base` is a power of two #147250

Kmeakin commented Oct 2, 2025 •

edited

Loading

workingjubilee commented Oct 2, 2025 •

edited

Loading

Kmeakin commented Oct 2, 2025 •

edited

Loading

scottmcm left a comment •

edited by rustbot

Loading

scottmcm left a comment •

edited by rustbot

Loading