Skip to content

Commit 7c896fc

Browse files
borsbors
committed
Auto merge of rust-lang#128204 - GuillaumeGomez:integers-opti, r=workingjubilee
Small optimization for integers Display implementation This is a first pass to try to speed up a bit integers `Display` implementation. The idea behind this is to reduce the stack usage for the buffer storing the output (shouldn't be visible in bench normally) and some small specialization which benefits a lot to smaller integers like `u8` and `i8`. Here are the results of the benchmarks: | bench name | current std | with this PR | |-|-|-| | bench_std_fmt::bench_i16_0 | 16.45 ns/iter (+/- 0.25) | 16.50 ns/iter (+/- 0.15) | | bench_std_fmt::bench_i16_max | 17.83 ns/iter (+/- 0.66) | 17.58 ns/iter (+/- 0.10) | | bench_std_fmt::bench_i16_min | 20.97 ns/iter (+/- 0.49) | 20.50 ns/iter (+/- 0.28) | | bench_std_fmt::bench_i32_0 | 16.63 ns/iter (+/- 0.06) | 16.62 ns/iter (+/- 0.07) | | bench_std_fmt::bench_i32_max | 19.79 ns/iter (+/- 0.43) | 19.55 ns/iter (+/- 0.14) | | bench_std_fmt::bench_i32_min | 22.97 ns/iter (+/- 0.50) | 22.08 ns/iter (+/- 0.08) | | bench_std_fmt::bench_i64_0 | 16.63 ns/iter (+/- 0.39) | 16.69 ns/iter (+/- 0.44) | | bench_std_fmt::bench_i64_half | 19.60 ns/iter (+/- 0.05) | 19.10 ns/iter (+/- 0.05) | | bench_std_fmt::bench_i64_max | 25.22 ns/iter (+/- 0.34) | 24.43 ns/iter (+/- 0.02) | | bench_std_fmt::bench_i8_0 | 16.27 ns/iter (+/- 0.32) | 15.80 ns/iter (+/- 0.17) | | bench_std_fmt::bench_i8_max | 16.71 ns/iter (+/- 0.09) | 16.25 ns/iter (+/- 0.01) | | bench_std_fmt::bench_i8_min | 20.07 ns/iter (+/- 0.22) | 19.80 ns/iter (+/- 0.30) | | bench_std_fmt::bench_u128_0 | 21.37 ns/iter (+/- 0.24) | 21.35 ns/iter (+/- 0.35) | | bench_std_fmt::bench_u128_max | 48.13 ns/iter (+/- 0.20) | 48.78 ns/iter (+/- 0.29) | | bench_std_fmt::bench_u16_0 | 16.48 ns/iter (+/- 0.46) | 16.03 ns/iter (+/- 0.39) | | bench_std_fmt::bench_u16_max | 17.31 ns/iter (+/- 0.32) | 17.41 ns/iter (+/- 0.32) | | bench_std_fmt::bench_u16_min | 16.40 ns/iter (+/- 0.45) | 16.02 ns/iter (+/- 0.39) | | bench_std_fmt::bench_u32_0 | 16.17 ns/iter (+/- 0.04) | 16.29 ns/iter (+/- 0.16) | | bench_std_fmt::bench_u32_max | 19.00 ns/iter (+/- 0.10) | 19.16 ns/iter (+/- 0.28) | | bench_std_fmt::bench_u32_min | 16.16 ns/iter (+/- 0.09) | 16.28 ns/iter (+/- 0.11) | | bench_std_fmt::bench_u64_0 | 16.22 ns/iter (+/- 0.22) | 16.14 ns/iter (+/- 0.18) | | bench_std_fmt::bench_u64_half | 19.25 ns/iter (+/- 0.07) | 18.95 ns/iter (+/- 0.05) | | bench_std_fmt::bench_u64_max | 24.31 ns/iter (+/- 0.08) | 24.18 ns/iter (+/- 0.08) | | bench_std_fmt::bench_u8_0 | 15.76 ns/iter (+/- 0.08) | 15.66 ns/iter (+/- 0.08) | | bench_std_fmt::bench_u8_max | 16.53 ns/iter (+/- 0.03) | 16.29 ns/iter (+/- 0.02) | | bench_std_fmt::bench_u8_min | 15.77 ns/iter (+/- 0.06) | 15.67 ns/iter (+/- 0.02) | The source code is: <details> <summary>source code</summary> ```rust #![feature(test)] #![allow(non_snake_case)] #![allow(clippy::cast_lossless)] extern crate test; macro_rules! benches { ($($name:ident($value:expr))*) => { mod bench_std_fmt { use std::io::Write; use test::{Bencher, black_box}; $( #[bench] fn $name(b: &mut Bencher) { let mut buf = Vec::with_capacity(40); b.iter(|| { buf.clear(); write!(&mut buf, "{}", black_box($value)).unwrap(); black_box(&buf); }); } )* } } } benches! { bench_u64_0(0u64) bench_u64_half(u32::max_value() as u64) bench_u64_max(u64::max_value()) bench_i64_0(0i64) bench_i64_half(i32::max_value() as i64) bench_i64_max(i64::max_value()) bench_u16_0(0u16) bench_u16_min(u16::min_value()) bench_u16_max(u16::max_value()) bench_i16_0(0i16) bench_i16_min(i16::min_value()) bench_i16_max(i16::max_value()) bench_u128_0(0u128) bench_u128_max(u128::max_value()) bench_i8_0(0i8) bench_i8_min(i8::min_value()) bench_i8_max(i8::max_value()) bench_u8_0(0u8) bench_u8_min(u8::min_value()) bench_u8_max(u8::max_value()) bench_u32_0(0u32) bench_u32_min(u32::min_value()) bench_u32_max(u32::max_value()) bench_i32_0(0i32) bench_i32_min(i32::min_value()) bench_i32_max(i32::max_value()) } ``` </details> And then I ran the equivalent code (source code below) in callgrind with [callgrind_differ](https://github.com/Ethiraric/callgrind_differ) to generate a nice output and here's the result: ``` core::fmt::num::imp::<impl core::fmt::Display for i16>::fmt | 1300000 | - 70000 - 5.385% 1230000 core::fmt::num::imp::<impl core::fmt::Display for i32>::fmt | 1910000 | - 100000 - 5.236% 1810000 core::fmt::num::imp::<impl core::fmt::Display for i64>::fmt | 2430000 | - 110000 - 4.527% 2320000 core::fmt::num::imp::<impl core::fmt::Display for i8>::fmt | 1080000 | - 170000 - 15.741% 910000 core::fmt::num::imp::<impl core::fmt::Display for u16>::fmt | 960000 | + 10000 + 1.042% 970000 core::fmt::num::imp::<impl core::fmt::Display for u32>::fmt | 1300000 | + 30000 + 2.308% 1330000 core::fmt::num::imp::<impl core::fmt::Display for u8>::fmt | 820000 | - 30000 - 3.659% 790000 ``` <details> <summary>Source code</summary> ```rust #![feature(test)] extern crate test; use std::io::{stdout, Write}; use std::io::StdoutLock; use test::black_box; macro_rules! benches { ($handle:ident, $buf:ident, $($name:ident($value:expr))*) => { $( fn $name(handle: &mut StdoutLock, buf: &mut Vec<u8>) { for _ in 0..10000 { buf.clear(); write!(buf, "{}", black_box($value)).unwrap(); handle.write_all(buf); } } $name(&mut $handle, &mut $buf); )* } } fn main() { let mut handle = stdout().lock(); let mut buf = Vec::with_capacity(40); benches! { handle, buf, bench_u64_0(0u64) bench_u64_half(u32::max_value() as u64) bench_u64_max(u64::max_value()) bench_i64_0(0i64) bench_i64_half(i32::max_value() as i64) bench_i64_max(i64::max_value()) bench_u16_0(0u16) bench_u16_min(u16::min_value()) bench_u16_max(u16::max_value()) bench_i16_0(0i16) bench_i16_min(i16::min_value()) bench_i16_max(i16::max_value()) bench_u128_0(0u128) bench_u128_max(u128::max_value()) bench_i8_0(0i8) bench_i8_min(i8::min_value()) bench_i8_max(i8::max_value()) bench_u8_0(0u8) bench_u8_min(u8::min_value()) bench_u8_max(u8::max_value()) bench_i32_0(0i32) bench_i32_min(i32::min_value()) bench_i32_max(i32::max_value()) bench_u32_0(0u32) bench_u32_min(u32::min_value()) bench_u32_max(u32::max_value()) } } ``` </details> The next step would be to specialize the `ToString` implementation so it doesn't go through the `Display` trait. I'm not sure if it will improve anything but I think it's worth a try. r? `@Amanieu`
2 parents a575a8b + 4451aee commit 7c896fc

File tree

1 file changed

+131
-81
lines changed

1 file changed

+131
-81
lines changed

‎core/src/fmt/num.rs

+131-81
Original file line numberDiff line numberDiff line change
@@ -208,75 +208,119 @@ static DEC_DIGITS_LUT: &[u8; 200] = b"0001020304050607080910111213141516171819\
208208
8081828384858687888990919293949596979899";
209209

210210
macro_rules! impl_Display {
211-
($($t:ident),* as $u:ident via $conv_fn:ident named $name:ident) => {
212-
#[cfg(not(feature = "optimize_for_size"))]
213-
fn $name(mut n: $u, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
214-
// 2^128 is about 3*10^38, so 39 gives an extra byte of space
215-
let mut buf = [MaybeUninit::<u8>::uninit(); 39];
216-
let mut curr = buf.len();
217-
let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
218-
let lut_ptr = DEC_DIGITS_LUT.as_ptr();
211+
($($t:ident $(as $positive:ident)? named $name:ident,)* ; as $u:ident via $conv_fn:ident named $gen_name:ident) => {
219212

220-
// SAFETY: Since `d1` and `d2` are always less than or equal to `198`, we
221-
// can copy from `lut_ptr[d1..d1 + 1]` and `lut_ptr[d2..d2 + 1]`. To show
222-
// that it's OK to copy into `buf_ptr`, notice that at the beginning
223-
// `curr == buf.len() == 39 > log(n)` since `n < 2^128 < 10^39`, and at
224-
// each step this is kept the same as `n` is divided. Since `n` is always
225-
// non-negative, this means that `curr > 0` so `buf_ptr[curr..curr + 1]`
226-
// is safe to access.
227-
unsafe {
228-
// need at least 16 bits for the 4-characters-at-a-time to work.
229-
assert!(crate::mem::size_of::<$u>() >= 2);
213+
$(
214+
#[stable(feature = "rust1", since = "1.0.0")]
215+
impl fmt::Display for $t {
216+
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
217+
// If it's a signed integer.
218+
$(
219+
let is_nonnegative = *self >= 0;
230220

231-
// eagerly decode 4 characters at a time
232-
while n >= 10000 {
233-
let rem = (n % 10000) as usize;
234-
n /= 10000;
221+
#[cfg(not(feature = "optimize_for_size"))]
222+
{
223+
if !is_nonnegative {
224+
// convert the negative num to positive by summing 1 to its 2s complement
225+
return (!self as $positive).wrapping_add(1)._fmt(false, f);
226+
}
227+
}
228+
#[cfg(feature = "optimize_for_size")]
229+
{
230+
if !is_nonnegative {
231+
// convert the negative num to positive by summing 1 to its 2s complement
232+
return $gen_name((!self.$conv_fn()).wrapping_add(1), false, f);
233+
}
234+
}
235+
)?
236+
// If it's a positive integer.
237+
#[cfg(not(feature = "optimize_for_size"))]
238+
{
239+
self._fmt(true, f)
240+
}
241+
#[cfg(feature = "optimize_for_size")]
242+
{
243+
$gen_name(self.$conv_fn(), true, f)
244+
}
245+
}
246+
}
235247

236-
let d1 = (rem / 100) << 1;
237-
let d2 = (rem % 100) << 1;
238-
curr -= 4;
248+
#[cfg(not(feature = "optimize_for_size"))]
249+
impl $t {
250+
fn _fmt(mut self: $t, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
251+
const SIZE: usize = $t::MAX.ilog(10) as usize + 1;
252+
let mut buf = [MaybeUninit::<u8>::uninit(); SIZE];
253+
let mut curr = SIZE;
254+
let buf_ptr = MaybeUninit::slice_as_mut_ptr(&mut buf);
255+
let lut_ptr = DEC_DIGITS_LUT.as_ptr();
256+
257+
// SAFETY: Since `d1` and `d2` are always less than or equal to `198`, we
258+
// can copy from `lut_ptr[d1..d1 + 1]` and `lut_ptr[d2..d2 + 1]`. To show
259+
// that it's OK to copy into `buf_ptr`, notice that at the beginning
260+
// `curr == buf.len() == 39 > log(n)` since `n < 2^128 < 10^39`, and at
261+
// each step this is kept the same as `n` is divided. Since `n` is always
262+
// non-negative, this means that `curr > 0` so `buf_ptr[curr..curr + 1]`
263+
// is safe to access.
264+
unsafe {
265+
// need at least 16 bits for the 4-characters-at-a-time to work.
266+
#[allow(overflowing_literals)]
267+
#[allow(unused_comparisons)]
268+
// This block will be removed for smaller types at compile time and in the worst
269+
// case, it will prevent to have the `10000` literal to overflow for `i8` and `u8`.
270+
if core::mem::size_of::<$t>() >= 2 {
271+
// eagerly decode 4 characters at a time
272+
while self >= 10000 {
273+
let rem = (self % 10000) as usize;
274+
self /= 10000;
275+
276+
let d1 = (rem / 100) << 1;
277+
let d2 = (rem % 100) << 1;
278+
curr -= 4;
279+
280+
// We are allowed to copy to `buf_ptr[curr..curr + 3]` here since
281+
// otherwise `curr < 0`. But then `n` was originally at least `10000^10`
282+
// which is `10^40 > 2^128 > n`.
283+
ptr::copy_nonoverlapping(lut_ptr.add(d1 as usize), buf_ptr.add(curr), 2);
284+
ptr::copy_nonoverlapping(lut_ptr.add(d2 as usize), buf_ptr.add(curr + 2), 2);
285+
}
286+
}
239287

240-
// We are allowed to copy to `buf_ptr[curr..curr + 3]` here since
241-
// otherwise `curr < 0`. But then `n` was originally at least `10000^10`
242-
// which is `10^40 > 2^128 > n`.
243-
ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
244-
ptr::copy_nonoverlapping(lut_ptr.add(d2), buf_ptr.add(curr + 2), 2);
245-
}
288+
// if we reach here numbers are <= 9999, so at most 4 chars long
289+
let mut n = self as usize; // possibly reduce 64bit math
246290

247-
// if we reach here numbers are <= 9999, so at most 4 chars long
248-
let mut n = n as usize; // possibly reduce 64bit math
291+
// decode 2 more chars, if > 2 chars
292+
if n >= 100 {
293+
let d1 = (n % 100) << 1;
294+
n /= 100;
295+
curr -= 2;
296+
ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
297+
}
249298

250-
// decode 2 more chars, if > 2 chars
251-
if n >= 100 {
252-
let d1 = (n % 100) << 1;
253-
n /= 100;
254-
curr -= 2;
255-
ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
299+
// if we reach here numbers are <= 100, so at most 2 chars long
300+
// The biggest it can be is 99, and 99 << 1 == 198, so a `u8` is enough.
301+
// decode last 1 or 2 chars
302+
if n < 10 {
303+
curr -= 1;
304+
*buf_ptr.add(curr) = (n as u8) + b'0';
305+
} else {
306+
let d1 = n << 1;
307+
curr -= 2;
308+
ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
309+
}
256310
}
257311

258-
// decode last 1 or 2 chars
259-
if n < 10 {
260-
curr -= 1;
261-
*buf_ptr.add(curr) = (n as u8) + b'0';
262-
} else {
263-
let d1 = n << 1;
264-
curr -= 2;
265-
ptr::copy_nonoverlapping(lut_ptr.add(d1), buf_ptr.add(curr), 2);
266-
}
312+
// SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
313+
// UTF-8 since `DEC_DIGITS_LUT` is
314+
let buf_slice = unsafe {
315+
str::from_utf8_unchecked(
316+
slice::from_raw_parts(buf_ptr.add(curr), buf.len() - curr))
317+
};
318+
f.pad_integral(is_nonnegative, "", buf_slice)
267319
}
268-
269-
// SAFETY: `curr` > 0 (since we made `buf` large enough), and all the chars are valid
270-
// UTF-8 since `DEC_DIGITS_LUT` is
271-
let buf_slice = unsafe {
272-
str::from_utf8_unchecked(
273-
slice::from_raw_parts(buf_ptr.add(curr), buf.len() - curr))
274-
};
275-
f.pad_integral(is_nonnegative, "", buf_slice)
276-
}
320+
})*
277321

278322
#[cfg(feature = "optimize_for_size")]
279-
fn $name(mut n: $u, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
323+
fn $gen_name(mut n: $u, is_nonnegative: bool, f: &mut fmt::Formatter<'_>) -> fmt::Result {
280324
// 2^128 is about 3*10^38, so 39 gives an extra byte of space
281325
let mut buf = [MaybeUninit::<u8>::uninit(); 39];
282326
let mut curr = buf.len();
@@ -306,21 +350,6 @@ macro_rules! impl_Display {
306350
};
307351
f.pad_integral(is_nonnegative, "", buf_slice)
308352
}
309-
310-
$(#[stable(feature = "rust1", since = "1.0.0")]
311-
impl fmt::Display for $t {
312-
#[allow(unused_comparisons)]
313-
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
314-
let is_nonnegative = *self >= 0;
315-
let n = if is_nonnegative {
316-
self.$conv_fn()
317-
} else {
318-
// convert the negative num to positive by summing 1 to it's 2 complement
319-
(!self.$conv_fn()).wrapping_add(1)
320-
};
321-
$name(n, is_nonnegative, f)
322-
}
323-
})*
324353
};
325354
}
326355

@@ -374,7 +403,6 @@ macro_rules! impl_Exp {
374403
(n, exponent, exponent, added_precision)
375404
};
376405

377-
// 39 digits (worst case u128) + . = 40
378406
// Since `curr` always decreases by the number of digits copied, this means
379407
// that `curr >= 0`.
380408
let mut buf = [MaybeUninit::<u8>::uninit(); 40];
@@ -469,7 +497,7 @@ macro_rules! impl_Exp {
469497
let n = if is_nonnegative {
470498
self.$conv_fn()
471499
} else {
472-
// convert the negative num to positive by summing 1 to it's 2 complement
500+
// convert the negative num to positive by summing 1 to its 2s complement
473501
(!self.$conv_fn()).wrapping_add(1)
474502
};
475503
$name(n, is_nonnegative, false, f)
@@ -484,7 +512,7 @@ macro_rules! impl_Exp {
484512
let n = if is_nonnegative {
485513
self.$conv_fn()
486514
} else {
487-
// convert the negative num to positive by summing 1 to it's 2 complement
515+
// convert the negative num to positive by summing 1 to its 2s complement
488516
(!self.$conv_fn()).wrapping_add(1)
489517
};
490518
$name(n, is_nonnegative, true, f)
@@ -499,8 +527,17 @@ macro_rules! impl_Exp {
499527
mod imp {
500528
use super::*;
501529
impl_Display!(
502-
i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
503-
as u64 via to_u64 named fmt_u64
530+
i8 as u8 named fmt_i8,
531+
u8 named fmt_u8,
532+
i16 as u16 named fmt_i16,
533+
u16 named fmt_u16,
534+
i32 as u32 named fmt_i32,
535+
u32 named fmt_u32,
536+
i64 as u64 named fmt_i64,
537+
u64 named fmt_u64,
538+
isize as usize named fmt_isize,
539+
usize named fmt_usize,
540+
; as u64 via to_u64 named fmt_u64
504541
);
505542
impl_Exp!(
506543
i8, u8, i16, u16, i32, u32, i64, u64, usize, isize
@@ -511,8 +548,21 @@ mod imp {
511548
#[cfg(not(any(target_pointer_width = "64", target_arch = "wasm32")))]
512549
mod imp {
513550
use super::*;
514-
impl_Display!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named fmt_u32);
515-
impl_Display!(i64, u64 as u64 via to_u64 named fmt_u64);
551+
impl_Display!(
552+
i8 as u8 named fmt_i8,
553+
u8 named fmt_u8,
554+
i16 as u16 named fmt_i16,
555+
u16 named fmt_u16,
556+
i32 as u32 named fmt_i32,
557+
u32 named fmt_u32,
558+
isize as usize named fmt_isize,
559+
usize named fmt_usize,
560+
; as u32 via to_u32 named fmt_u32);
561+
impl_Display!(
562+
i64 as u64 named fmt_i64,
563+
u64 named fmt_u64,
564+
; as u64 via to_u64 named fmt_u64);
565+
516566
impl_Exp!(i8, u8, i16, u16, i32, u32, isize, usize as u32 via to_u32 named exp_u32);
517567
impl_Exp!(i64, u64 as u64 via to_u64 named exp_u64);
518568
}
@@ -619,7 +669,7 @@ impl fmt::Display for i128 {
619669
let n = if is_nonnegative {
620670
self.to_u128()
621671
} else {
622-
// convert the negative num to positive by summing 1 to it's 2 complement
672+
// convert the negative num to positive by summing 1 to its 2s complement
623673
(!self.to_u128()).wrapping_add(1)
624674
};
625675
fmt_u128(n, is_nonnegative, f)

0 commit comments

Comments
 (0)