Display impl for u128 and i128 is slow

[dtolnay]

@henninglive has a significantly faster one in dtolnay/itoa#10 (comment). Let's provide the faster one in std::fmt!

Unoptimized:
	test bench_itoa::bench_u128_max ... bench:       3,009 ns/iter (+/- 99)

Manual linking:
	test bench_itoa::bench_u128_max ... bench:       1,537 ns/iter (+/- 59)

Inlined:
	test bench_itoa::bench_u128_max ... bench:       1,289 ns/iter (+/- 54)

[henninglive]

The implementation is copied from std::fmt, the only change is that I have inlined the __udivmodti4() implementation to work around #44545 until LLVM is smart enough combine the calls. This is probably not relevant for std.

[dtolnay]

I guess I haven't looked at the two implementations carefully. Can we not inline __udivmodti4() in std?

[henninglive]

It’s possible, but we probably don’t want to do that. __udivmodti4() is an intrinsic passed to LLVM to be used to implement division for i128/u128 on architectures without native 128-bit support. It is an implementation detail of the architecture and is currently defined separately from the compiler itself. Std is going to nearly as fast as the inlined version when #44545 is eventually fixed. We should proberly wait for that or we could let std link __udivmodti4() as it did in the past, rust-lang/rfcs#914.

[cuviper]

For platforms that don't have native 128-bit division, it may be faster to break it into parts that can do native division from there. Bases 2, 8, and 16 can split directly to 64-bit parts, and base-10 can split into three base-10¹³ parts. If some 32-bit targets don't have native 64-bit division, they may do even better with 5 base-10⁸ parts stored in 32-bit, etc.

[cuviper]

Hmm, I just read the implementation, and it already chunks it by 10000, so that much is probably pretty good already.

[henninglive]

I haven’t tried it, but I believe the current implementation is going to be pretty terrible on platforms without u64. If I understand this code correctly, the __udivmodti4() implementation as going use __udivmoddi4 and its brothers to do u64 operations, which a lot of non inlined functions calls to divide two u128s.

[dtolnay]

I have yet another implementation in dtolnay/itoa#12. This one is 13x faster than std::fmt on my machine.

[steveklabnik]

Triage: this appears to have gotten even more extreme over time:

running 2 tests
test itoa   ... bench:         216 ns/iter (+/- 28)
test stdlib ... bench:       1,377 ns/iter (+/- 123)

The reproduction involves cargo features and so cannot be done on the playground, details below.

Details

Cargo.toml:

[package]
name = "itoatest"
version = "0.1.0"
authors = ["Steve Klabnik <steve@steveklabnik.com>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies.itoa]
version = "*"
features = ["std", "i128"]

in benches/bench.rs:

#![feature(test)]
extern crate test;
extern crate itoa;

use test::Bencher;

#[bench]
fn stdlib(b: &mut Bencher) {
    b.iter(|| {
        let s = format!("{}", u128::max_value());
        std::hint::black_box(s);
    });
}

#[bench]
fn itoa(b: &mut Bencher) {

    b.iter(|| {
        let mut s = String::new();
        itoa::fmt(&mut s, u128::max_value()).unwrap();
        std::hint::black_box(s);
    });
}