Skip to content

Commit 981835d

Browse files
borsbors
committed
Auto merge of #115913 - FedericoStra:checked_ilog, r=the8472
checked_ilog: improve performance Addresses #115874. (This PR replicates the original #115875, which I accidentally closed by deleting my forked repository...)
2 parents fb89862 + 3de51c9 commit 981835d

File tree

3 files changed

+89
-27
lines changed

3 files changed

+89
-27
lines changed

‎library/core/benches/num/int_log/mod.rs

+73-6
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
use rand::Rng;
22
use test::{black_box, Bencher};
33

4-
macro_rules! int_log_bench {
4+
macro_rules! int_log10_bench {
55
($t:ty, $predictable:ident, $random:ident, $random_small:ident) => {
66
#[bench]
77
fn $predictable(bench: &mut Bencher) {
@@ -51,8 +51,75 @@ macro_rules! int_log_bench {
5151
};
5252
}
5353

54-
int_log_bench! {u8, u8_log10_predictable, u8_log10_random, u8_log10_random_small}
55-
int_log_bench! {u16, u16_log10_predictable, u16_log10_random, u16_log10_random_small}
56-
int_log_bench! {u32, u32_log10_predictable, u32_log10_random, u32_log10_random_small}
57-
int_log_bench! {u64, u64_log10_predictable, u64_log10_random, u64_log10_random_small}
58-
int_log_bench! {u128, u128_log10_predictable, u128_log10_random, u128_log10_random_small}
54+
int_log10_bench! {u8, u8_log10_predictable, u8_log10_random, u8_log10_random_small}
55+
int_log10_bench! {u16, u16_log10_predictable, u16_log10_random, u16_log10_random_small}
56+
int_log10_bench! {u32, u32_log10_predictable, u32_log10_random, u32_log10_random_small}
57+
int_log10_bench! {u64, u64_log10_predictable, u64_log10_random, u64_log10_random_small}
58+
int_log10_bench! {u128, u128_log10_predictable, u128_log10_random, u128_log10_random_small}
59+
60+
macro_rules! int_log_bench {
61+
($t:ty, $random:ident, $random_small:ident, $geometric:ident) => {
62+
#[bench]
63+
fn $random(bench: &mut Bencher) {
64+
let mut rng = crate::bench_rng();
65+
/* Exponentially distributed random numbers from the whole range of the type. */
66+
let numbers: Vec<$t> = (0..256)
67+
.map(|_| {
68+
let x = rng.gen::<$t>() >> rng.gen_range(0..<$t>::BITS);
69+
if x >= 2 { x } else { 2 }
70+
})
71+
.collect();
72+
bench.iter(|| {
73+
for &b in &numbers {
74+
for &x in &numbers {
75+
black_box(black_box(x).ilog(b));
76+
}
77+
}
78+
});
79+
}
80+
81+
#[bench]
82+
fn $random_small(bench: &mut Bencher) {
83+
let mut rng = crate::bench_rng();
84+
/* Exponentially distributed random numbers from the range 0..256. */
85+
let numbers: Vec<$t> = (0..256)
86+
.map(|_| {
87+
let x = (rng.gen::<u8>() >> rng.gen_range(0..u8::BITS)) as $t;
88+
if x >= 2 { x } else { 2 }
89+
})
90+
.collect();
91+
bench.iter(|| {
92+
for &b in &numbers {
93+
for &x in &numbers {
94+
black_box(black_box(x).ilog(b));
95+
}
96+
}
97+
});
98+
}
99+
100+
#[bench]
101+
fn $geometric(bench: &mut Bencher) {
102+
let bases: [$t; 16] = [2, 3, 4, 5, 7, 8, 9, 15, 16, 17, 31, 32, 33, 63, 64, 65];
103+
let base_and_numbers: Vec<($t, Vec<$t>)> = bases
104+
.iter()
105+
.map(|&b| {
106+
let numbers = (0..=<$t>::MAX.ilog(b)).map(|exp| b.pow(exp)).collect();
107+
(b, numbers)
108+
})
109+
.collect();
110+
bench.iter(|| {
111+
for (b, numbers) in &base_and_numbers {
112+
for &x in numbers {
113+
black_box(black_box(x).ilog(black_box(*b)));
114+
}
115+
}
116+
});
117+
}
118+
};
119+
}
120+
121+
int_log_bench! {u8, u8_log_random, u8_log_random_small, u8_log_geometric}
122+
int_log_bench! {u16, u16_log_random, u16_log_random_small, u16_log_geometric}
123+
int_log_bench! {u32, u32_log_random, u32_log_random_small, u32_log_geometric}
124+
int_log_bench! {u64, u64_log_random, u64_log_random_small, u64_log_geometric}
125+
int_log_bench! {u128, u128_log_random, u128_log_random_small, u128_log_geometric}

‎library/core/src/num/int_macros.rs

+3-15
Original file line numberDiff line numberDiff line change
@@ -3123,21 +3123,9 @@ macro_rules! int_impl {
31233123
if self <= 0 || base <= 1 {
31243124
None
31253125
} else {
3126-
let mut n = 0;
3127-
let mut r = self;
3128-
3129-
// Optimization for 128 bit wide integers.
3130-
if Self::BITS == 128 {
3131-
let b = Self::ilog2(self) / (Self::ilog2(base) + 1);
3132-
n += b;
3133-
r /= base.pow(b as u32);
3134-
}
3135-
3136-
while r >= base {
3137-
r /= base;
3138-
n += 1;
3139-
}
3140-
Some(n)
3126+
// Delegate to the unsigned implementation.
3127+
// The condition makes sure that both casts are exact.
3128+
(self as $UnsignedT).checked_ilog(base as $UnsignedT)
31413129
}
31423130
}
31433131

‎library/core/src/num/uint_macros.rs

+13-6
Original file line numberDiff line numberDiff line change
@@ -1095,18 +1095,25 @@ macro_rules! uint_impl {
10951095
None
10961096
} else {
10971097
let mut n = 0;
1098-
let mut r = self;
1098+
let mut r = 1;
10991099

11001100
// Optimization for 128 bit wide integers.
11011101
if Self::BITS == 128 {
1102-
let b = Self::ilog2(self) / (Self::ilog2(base) + 1);
1103-
n += b;
1104-
r /= base.pow(b as u32);
1102+
// The following is a correct lower bound for ⌊log(base,self)⌋ because
1103+
//
1104+
// log(base,self) = log(2,self) / log(2,base)
1105+
// ≥ ⌊log(2,self)⌋ / (⌊log(2,base)⌋ + 1)
1106+
//
1107+
// hence
1108+
//
1109+
// ⌊log(base,self)⌋ ≥ ⌊ ⌊log(2,self)⌋ / (⌊log(2,base)⌋ + 1) ⌋ .
1110+
n = self.ilog2() / (base.ilog2() + 1);
1111+
r = base.pow(n);
11051112
}
11061113

1107-
while r >= base {
1108-
r /= base;
1114+
while r <= self / base {
11091115
n += 1;
1116+
r *= base;
11101117
}
11111118
Some(n)
11121119
}

0 commit comments

Comments
 (0)