Efficient integer formatting into fixed-size buffer

[hanna-kruppe]

Proposal

Problem statement

The standard library provides highly optimized implementations of integer to decimal string conversions, but these are only accessible via the core::fmt machinery, which forces 1-2 layers of dynamic dispatch between user code and the actual formatting logic. Benchmarks in the itoa crate demonstrate that side-stepping fmt makes formatting much more efficient. Currently, any Rust user who wants that performance has to use third-party crates like itoa or lexical(-core) which essentially duplicate standard library functionality.

Motivating examples or use cases

• serde-json
• http: integer to HTTP header values
• maud: rendering integers in HTML templates
• arrow-json: converting data from the Arrow format to JSON
• ... and basically everything else that depends on itoa (the lexical* crates also include float formatting and integer/float parsing, so their list of dependents is less illustrative).
• rustix used to use itoa for putting integers (like file descriptors) into paths without intermediate allocations, but recently switched to a simplified homebrew implementation.
• compact_str uses itoa for 128 bit integers, but for smaller integers they vendor the standard library code and modify it to write directly into their custom string type's buffer. However, in this case the buffer size is based on the magnitude of the integer, not the worst-case size.

Solution sketch

impl {iN, uN, usize, isize} {
    const MAX_STR_LEN: usize;
    fn format_into(self, buf: &mut [MaybeUninit<u8>; Self::MAX_STR_LEN]) -> &str;
}

This can be used from safe code, though it's a little more noisy than the itoa API since MaybeUninit::uninit_array is slated for removal:

use_str(itoa::Buffer::new().format(n));
use_str(n.format_into(&mut [const { MaybeUninit::uninit() }; TypeOfN::MAX_STR_LEN]));
// With uninit_array the length could be inferred:
use_str(n.format_into(&mut MaybeUninit::uninit_array()));

Alternatively, unsafe code can write directly into the buffer they want, e.g., for the itoa usage in http could write directly into the spare_capacity_mut() of the BytesMut it creates. I believe it could also replace the homebrew integer formatting in rustix::DecInt. (edit: not so simple, see first reply)

Alternatives

The obvious option would be to import the API of itoa directly (single Buffer type with fn format(&mut self, n: impl SealedTrait) -> &str), since it's already widely used. However:

• Not being able to format directly into part of a buffer you own is insufficient for some users, who end up vendoring their own integer formatting code (e.g., rustix and compact_str as mentioned under motivation). (edit: not so simple, see first reply)
• If Rust later adds const-generic u<N> and i<N> types with generous limits on N (e.g., Generic Integers V2: It's Time rfcs#3686) then a one-size-fits-all buffer may become excessively large. Even with a limit of N <= 4096, it would be well over a kilobyte. Even though the buffer doesn't have to be initialized, it'll still increase the stack frame size, which can have undesirable side effects on code generation (stack probes are generally inserted for frames larger than one page, SP-relative loads and stores need larger offsets that may no longer fit into an immediate operand).
• The trait is extra API surface. While it's useful to expose (for bounds and for accessing the associated constant MAX_STR_LEN), the general trend in the standard library is to have inherent associated functions and constants on every integer type, not traits implemented for every integer type.

Other alternatives:

• lexical-core has fn write(n: impl SomeTrait, buf: &mut [u8]) -> &[u8], but this requires unsafe to get a string out of it, and even if the return type is changed to &str, it can panic if the buffer is too small for the given n and requires a fully initialized buffer.
• lexical has fn to_string(n: impl SomeTrait) -> String but this requires alloc (not just core) and does an unnecessary heap allocation when the result is immediately copied into another buffer.

Links and related work

• Make Rust's write! faster dtolnay/itoa#1
• The discussion on the rustix PR linked above.

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[hanna-kruppe]

After more careful thought, I’m not sure whether &mut [MaybeUninit<u8>; MAX_LEN] is the right type. Writing directly into a user-provided buffer is difficult because many reasonable implementations (including the current one in core) format from least to most significant digit without calculating the output size up-front and thus write to the end of the provided buffer instead of the start. I stand by the other reasons for deviating from itoa's API, but directly writing into a user-provided &mut [MaybeUninit<u8>; N] has the risk that unsafe code ends up relying on implementation details of the formatting code.

[BurntSushi]

You can add jiff to the motivating examples.

And ripgrep as well.

I am in general in favor of something like this, but definitely have some concerns. One is the concern you bring up, although I wonder if it's that bad of an idea to just specify that behavior (that digits are written to the end of the buffer). Like it doesn't seem that bad. The other concern I have is that this API doesn't account for formatting options like padding and what not. I suspect such things can be implemented on top of this by callers, but I think we'd want to actually try it with the proposed API to make sure it's reasonable (and other types of common configurations done to decimal formatting).

Also curious to hear @dtolnay's thoughts on this as well!

[hanna-kruppe]

The other concern I have is that this API doesn't account for formatting options like padding and what not. I suspect such things can be implemented on top of this by callers, but I think we'd want to actually try it with the proposed API to make sure it's reasonable (and other types of common configurations done to decimal formatting).

This seems like a good use for the (currently unstable) core::fmt::FormattingOptions, to give access to the standard library's implementation of all that stuff without pulling in fmt::Write or fmt::Formatter or duplicating a lot of code and API surface. (Edit: well, the logic of Formatter::pad_integral would have to be separated from Formatter, but that seems manageable.)

[hanna-kruppe]

On second thought, taking a step back: the current implementations in the standard library already use essentially the proposed API (write digits into a small MaybeUninit buffer and convert to &str) and passes the result to Formatter::pad_integral. Anyone who's happy to be write into a fmt::Formatter could use that combination, though this wouldn't be any better than calling <$int as Display>::fmt directly. Everyone who wants to do padding etc. with a different sink type (say, String or impl io::Write) could use this API and re-implement pad_integral specialized to the sink type (and subset of options) they want. This suggests it's very possible to implement all of that logic on top of the proposed API. It feels like it ought to be possible to also make the pad_integral logic reusable, but it's not quite trivial because you'd have to completely abstract over the sink type. The motivation is also weaker, since the many users of itoa don't seem to need it.

[programmerjake]

what about having the destination buffer type be BorrowedBuf or BorrowedCursor, once those types are moved to core (iirc they don't need io::Error, so moving them to core should be trivial). the only downside is it's harder to return a &mut str with a useful lifetime.

maybe:

/// could be sealed
pub trait BorrowedBufIntoStr<'a>: 'a {
    fn cursor<'this>(&'this mut self) -> BorrowedCursor<'this>;
    fn borrowed_buf_into_str(self) -> &'a mut str;
}

impl<'a> BorrowedBufIntoStr<'a> for BorrowedBuf<'a> { ... }
impl<'a, 'b> BorrowedBufIntoStr<'a> for &'a mut BorrowedBuf<'b> { ... }

impl <int> {
    fn fmt_into<'a>(self, base: u32, options: FormatterOptions, buf: impl BorrowedBufIntoStr<'a>) -> Result<&'a mut str, NotEnoughSpace> { ... }
}

[hanna-kruppe]

As long as the implementation wants to write to the end of the buffer, that seems to clash with the filled < init invariant of BorrowedBuf/BorrowedCursor. It's possible to work around this by formatting into an internal buffer first and then copying into the provided buffer, but that's an extra copy for some use cases. (And for the uses that need such a copy anyway, it adds more bookkeeping to that copy, which may or may not be optimized out.)

[the8472]

Would a usize::format(self) -> Buffer work? The buffer would deref to &str and by relying on return value optimization it shouldn't cost an extra move.

[hanna-kruppe]

I think it would work if it was Buffer<$int> to avoid the "one buffer size fits all" forward-compat trap, though it requires the Buffer type to store a length as well (i.e., ArrayVec<u8, N> rather than [MaybeUninit<u8>; N]). But I don't love relying on RVO so much since it's not fully reliable in my experience.

If we do want to have a dedicated type for the buffer, instead of raw "array of MaybeUninit" I think most of the ergonomic gains can be had with the signature fn format_into(self, &mut Buffer<Self>) -> &str plus a constructor like Buffer::new(). Is there a use case that requires moving the buffer after it's been filled and still accessing the string previously written into it? itoa and lexical-core don't support that, and lexical only supports it by returning String.

[programmerjake]

I think it would work if it was Buffer<$int> to avoid the "one buffer size fits all" forward-compat trap

if you're formatting in base >= 7 (so out of the common bases, octal, decimal, and hexadecimal, but not binary), then 3 times the input number's size is sufficient to store all the formatted digits (assuming unsigned, or signed decimal and bigger than i8), so we could have:

union BufferData<T> {
    ints: MaybeUninit<[T; 3]>,
    i8_bytes: MaybeUninit<[u8; 4]>, // enough space for "-128"
}

pub struct Buffer<T> {
    data: BufferData<T>,
    start: usize, // formatting likes to write from the end to the start
}

impl<T> Buffer<T> {
    pub const new() -> Self {
        Self {
            data: BufferData { ints: MaybeUninit::uninit() },
            start: mem::size_of::<Self>(),
        }
    }
    pub const fn clear(&mut self) {
        self.start = mem::size_of::<Self>();
    }
    pub const fn as_str(&self) -> &str {
        unsafe {
            let v = slice::from_raw_parts(&raw const self.data as *const u8, mem::size_of::<Self>());
            str::from_utf8_unchecked(v.get_unchecked(self.start..))
        }
    }
    const unsafe fn data_mut(&mut self) -> &mut [MaybeUninit<u8>] {
        unsafe {
            slice::from_raw_parts_mut(&raw mut self.data as *mut u8, mem::size_of::<Self>())
        }
    }
    const unsafe fn push_front(&mut self, v: u8) {
        self.start -= 1;
        unsafe {
            self.data_mut()[self.start] = MaybeUninit::new(v);
        }
    }
}

impl<T> Deref for Buffer<T> {
    type Target = str;

    fn deref(&self) -> &Self::Target {
        self.as_str()
    }
}

impl <signed-int> {
    pub const fn format(self, buf: &mut Buffer<Self>) -> &str {
        self.unsigned_abs().format(unsafe { &mut *(buf as *mut Buffer<Self> as *mut Buffer<<unsigned-int>>) });
        if self < 0 {
            unsafe { buf.push_front(b'-') };
        }
        buf.as_str()
    }
}

impl <unsigned-int> {
    pub const fn format(mut self, buf: &mut Buffer<Self>) -> &str {
        buf.clear();
        // not the most efficient algorithm...
        unsafe {
            loop {
                self.push_front(b'0' + (self % 10) as u8);
                self /= 10;
                if self == 0 {
                    break;
                }
            }
        }
        buf.as_str()
    }
}

[kennytm]

impl <signed-int> {
    pub const fn format(self, buf: &mut Buffer<Self>) -> &str {
        self.unsigned_abs().format(buf);

One little issue here is that you can't pass the &mut Buffer<i32> into u32::format which expects a &mut Buffer<u32>, unless you unsafe-cast it.

[Amanieu]

We discussed this in a libs-api meeting: we're happy to accept this, but would prefer an API closer to that of the itoa crate. Notably, we felt there was no need to expose the slice of MaybeUninit: instead an opaque NumBuffer type should be used.

We ended up with the following API:

// core::num

struct NumBuffer { .. }
impl NumBuffer {
    fn new() -> Self;
}

impl $Int {
    fn format_into(self, &mut NumBuffer) -> &str;
}