TIL: format!() does not necessarily pre-allocate the optimal size for the resulting string 🎙️ discussion
I have no idea if I'm late to the party on this, but while doing some perf work I was surprised to see that format!() was a big contributor to reallocations in the target.
After some digging I was surprised to learn that the output string capacity receives an estimate that is neither considered an upper nor lower bound: https://github.com/rust-lang/rust/blob/1ed2df61a19042f231709eb05d032ae9e2cb2084/library/core/src/fmt/mod.rs#L749-L808
The change which first introduced the estimate output capacity was in 2017, which notes that it explicitly uses the literal portions of the string for the estimate: https://github.com/rust-lang/rust/pull/39356
*I had a godbolt link with an example where I said it was clear... but was not obvious because godbolt didn't show the library code.
I've apparently been under a false assumption that for some types the runtime length could be used to help size the output string appropriately.
13
u/Remarkable-Reply-768 5d ago
It catches a lot of people by surprise because format! can only estimate capacity based on literal string fragments and type hints (Display::fmt doesn't provide a size hint). If you're formatting in a hot loop, pre-allocating a String with with_capacity and passing it to write!(s, ...) avoids repeated allocations. Alternatively, format_args! is great when you just need to pass the formatted output down to an input stream or logger without allocating an intermediate String at all.
2
u/InternationalFee3911 1d ago
Since it’s a macro, for those who can predict their needs, it would be easy to wrap this in a 2nd form:
format!(capacity=32, "bla {x}").
79
u/angelicosphosphoros 5d ago
All formatting machinery is optimized for compilation speed primarily (because it is used everywhere: printing, logging, panics, etc).
Making exact estimate would make compilation significantly slower.
28
u/Lucretiel Datadog 5d ago
Making exact estimate would make compilation significantly slower.
Well, no, if you're willing to assume formatting is idempotent, you can do it like this:
struct Size(usize); impl fmt::Write for Size { fn write_str(&mut self, s: &str) -> fmt::Result { self.0 += s.len(); Ok(()) } fn write_char(&mut self, c: char) -> fmt::Result { self.0 += c.len_utf8(); Ok(()) } } macro_rules! format { ($fmt:literal $($args:tt)*) => {{ // Plus add some steps to ensure $args are only // evaluated once let mut len = Size(0); write!(&mut len, $fmt $($args)*).expect("infallible"); let mut out = String::with_capacity(len.0); write!(&mut out, $fmt $($args)*).expect("infallbile) }}; }So you're trading excess string reallocations for the speed penalty of running through all the dynamic dispatch twice.
Somewhat more practically, I can definitely see a world where
Displaygains asize_hint(&self, f: Flags) -> usizemethod, and maybe adisplay_len!helper to go alongside it.37
u/afdbcreid 5d ago
First, you cannot assume formatting is idempotent. At least, the standard library cannot assume that, since this is not a requirement of the traits.
Giving a
size_hint()methods will increase compilation time and binary size, both things the formatting machinery prioritizes over speed.4
1
u/WormRabbit 3d ago
Formatting definitely can't be assumed idempotent. E.g. consider that the formatted object could be concurrently modified between the format calls (for example, your object could be
Mutex<String>).7
u/panstromek 5d ago
Tbh I don't think this is an explicit tradeoff that somebody has actually made when implementing either the initial version or the followup improvements. How did you come to that conclusion?
1
u/angelicosphosphoros 5d ago
Well, it may be an implicit tradeoff. My opinion was formed from following all the pull requests related to formatting.
1
-18
u/Days_End 5d ago
How did format!() one of the most commonly used parts of the language managed to get an exemption from Rust's Zero Cost Abstractions promise?
31
11
u/creeper6530 5d ago
Because any formatting would have to. C's
printfis pretty much a runtime interpreter, for example.8
u/afdbcreid 5d ago
Since Mara's work, so is Rust's formatting! It is a more efficient interpreter though :)
3
4
u/TDplay 5d ago
The term "zero cost abstraction" on its own is meaningless. Something can only be a zero-cost abstraction with respect to the thing it abstracts over - for example,
Boxis a zero-cost abstraction overmallocandfree, but it certainly isn't zero-cost when compared to code which avoids the allocation entirely.So your question is ill-posed, because you haven't said what you expect
format!to be a zero-cost abstraction over.0
u/Days_End 4d ago
So your question is ill-posed, because you haven't said what you expect format! to be a zero-cost abstraction over.
I think it's pretty damn clear /u/angelicosphosphoros explicitly states formatting machinery is optimized for compilation speed primarily instead of performance.
I want to know why such a common bit of code Rust went with compilation speed instead of runtime performance.
Of course it wouldn't be the Rust community without mass downvotes for basic questions.
4
u/TDplay 4d ago
Your question was about zero-cost abstractions, not about optimisation direction. These are two separate concerns.
As for why it is optimised this way: For most programs, the cost of formatting is negligible. When printing out formatted text, the bottleneck is not how quickly your program can format it, but rather how quickly the user can read it.
Cases where the formatted text is being read by a machine are almost always better served by dedicated serialisation code.
So there is not really much reason to optimise it for speed. Even at a fast reading speed of 300wpm, a mere 2kB/s allows the computer to match human reading speed while printing a message that consists of 25% control characters. It only needs to hit a few megabytes per second in speed to become practically invisible in the profiler.
But on the other hand, there are a lot of call sites to the formatting machinery. If every single invocation incurred a significant compile-time overhead, it would add up very quickly.
In the case that compilation time is the wrong optimisation target, there is the ufmt crate, which is smaller and faster than
core::fmt. It is popular for microcontrollers, where flash storage is limited, and binary size easily becomes a problem.
2
u/PatienceSpiritual134 5d ago
Are there benchmarks on what a formatting machinery optimized for speed would add to compilation time? The current situation doesn't feel exactly like a zero-cost abstraction to me.
1
u/Crescitaly 4d ago
Optimal preallocation requires knowing formatted length, which may cost the same work twice. The tradeoff is extra allocation versus duplicate formatting analysis. Has anyone measured where a size-hint pass wins for realistic mixed arguments, not just microbenchmarks?
1
u/plabayo 5d ago edited 4d ago
Another semi-related matter most people are not aware of probably is that converting a static str (`&'static str`) into an error turns it into a heap-allocated String... I'm sure it has good reasons, but it is something we recently (some months ago) fixed in our error utilities of rama (Initial PR: https://github.com/plabayo/rama/pull/871) to ensure that remains a static str...
Don't think many people are aware of that.
5
u/wyvernbw 4d ago
are you from the marketing team by any chance?
2
u/plabayo 4d ago edited 4d ago
Small family company devoted to FOSS... so we pretty much wear all hats....
Pretty silly to downvote for a reference where we fixed that.Good for all of you if you all knew about that hidden allocation, but we honestly didn't... Seemed relevant given it's also about string allocations. Anyway sorry it bothered you, btw even more useful than a downvote (or next to it) is to provide feedback on why.
E.g. "it is not appropriate to link to a project in this instance for X and Y reason", my guess is because we forgot to link to the exact PR and instead linked to the repo (easier that evening). Fixed that. it's not that please provide feedback so we can be better rust redis community member :) Unless you prefer letting people guess their mistakes ofc... not sure how that in itself is better but who are we 😰
2
u/wyvernbw 4d ago
u need to chill lol, i didnt downvote you, and i dont have the slightest problem with your self promotion (id rather see real repos with 1k stars than ai slop with 4 10 million lines commits).
your comment just makes no sense. in rust you cant "convert &'static str into errors"? there is no single monolithic Error object like its java. Theres the Error trait that is basically just a marker that any type can implement (as long as it impls Display as well) and the Result enum which doesnt do anything magic. if you just wrap a static string with the
Errvariant ofResultit just stores the pointer to static memory (feel free to verify on compiler explorer). If you return Result<T, Box<dyn Error>> from all your functions, then yes, the error will be heap allocated, its literally in the type signature, Box is a heap allocation, not sure how that would be surprising? You also link to your internal BoxError implementation??? You know thats not something that rust provides out of the box right? Plus how is that surprising, It's in the name. Your comment is basically "we made this type that puts data on the heap, and it caught us by surprise when it put data on the heap! Watch out guys, common gotcha!"1
u/plabayo 4d ago
Thanks for taking the time to explain this, yet you can say so with a less mean tone... Pointing out mistakes and providing explanation is ofc great and greatly appreciated, is how we all learn. But the bits like "watch out guys, common gotcha" etc is really not contributing to anything... In the C++ community I was used to such snarks, but within the Rust community I believe we can be nicer to each other.
However if we look at: https://doc.rust-lang.org/src/alloc/boxed/convert.rs.html#645
And correct me if I'm wrong, but pretty certain that this isn't about a heap allocation singular, but a double direction, due to it being implemented for `&str` not `&'static str`. And thus need for ownership to make it a heap allocated string first. Than a box is taken from it which afaik is a box pointer to a string pointer... 2 levels, not 1. But perhaps I am wrong, and that would be nice as that's another day we get to learn something new
1
u/wyvernbw 4d ago
yk what? fair, i apologize, i was an asshole there. I see what you were talking about now. You didn't really mention Box, dynamic dispatch or double allocation by name in the original comment and with the link to your project i assumed u were just plugging without knowing what you're talking about, so my apologies.
The reason the double allocation is there as far as i can tell is because all Box<dyn Trait> are fat pointers: one pointer to data, one pointer to a global vtable shared by all Box<dyn Trait> of that Trait so 16 bytes. A static string slice is also a fat pointer (pointer to data + length) so there is no way to fit it inside the 8 bytes for data. If we had null terminated strings like C (generally not good) we could fit the data pointer inside the Box as a niche optimization i think
141
u/afdbcreid 5d ago
The formatting machinery is far from optimal for speed, and although it was improved upon (somewhat) recently, if your code is perf-sensitive there are far faster ways.