Tracking issue for improving std::fmt::Arguments and format_args!()

[m-ou-se]

Earlier this year in the libs team meeting, I presented several different ideas for alternative implementations of std::fmt::Arguments which could result in smaller binary size or higher performance. Now that #93740 is mostly done, I'll be shifting my focus to fmt::Arguments and exploring those ideas.

Currently, fmt::Arguments is the size of six pointers, and refers to three slices:

• A &'static [&'static str] containing the literal parts around the formatting placeholders. E.g. for "a{}b{}c", these are ["a", "b", "c"].
• A &[&(ptr, fn_ptr)] which is basically a &[&dyn Display] (but can point to Debug or Hex etc. too), pointing to the arguments. This one is not 'static, as it points to the actual arguments to be formatted.
• A Option<&'static [FmtArgument]>, where FmtArgument is a struct containing all the options like precision, width, alignment, fill character, etc. This is unused (None) when all placeholders have no options, like in "{} {}", but is used and filled in for all place holders as soon as any placeholder uses any options, like in "{:.5} {}".

Here's a visualisation of that, for a "a{}b{:.5}c" format string:

An important part of this design is that most of it can be stored in static storage, to minimize the amount of work that a function that needs to create/pass a fmt::Arguments needs to do. It can just refer to the static data, and only fill in a slice of the arguments.

Some downsides:

• A fmt::Arguments is still relatively big (six pointers in size), and not a great type to pass by value. It could be just two pointers in size (one to static data, one to dynamic data), such that it fits in a register pair.
• It costs quite a lot of static storage for some simple format strings. For example, "a{}b{}c" needs a &["a", "b", "c"], which is stored in memory as a (ptr, size) pair referencing three (ptr, size) pairs referencing one byte each, which is a lot of overhead. Small string literals with just a newline or a space are very common in formatting.
• When even just a single formatting placeholder uses any non-standard options, such as "{:02x}", a relatively large array with all the (mostly default) formatting options is stored for all placeholders.
• The non-static part that contains the pointers to the arguments contains the pointers to the relevant Display/Debug/etc. implementation as well, even though that second part is constant and could be static. (It's a bit tricky to split those, though.)
• Even when formatting a simple &str argument with a simple "{}" placeholder, the full Display implementation for &str is pulled in, which include code for all the unused options like padding, alignment, etc.

Issues like those are often reason to avoid formatting in some situations, which is a shame.

None of these things are trivial to fix, and all involve a trade off between compile time, code size, runtime performance, and implementation complexity. It's also very tricky to make these tradeoffs for many different use cases at once, as the ways in which formatting is used in a program differs vastly per type of Rust program.

Still, there are many ideas that are worth exploring. It's hard to predict which one will end up being best, so this will involve several different implementations to test and benchmark.

I'll explain the different ideas one by one in the comments below as I explore them.

---

To do:

• Simplify and clean up format_args!() implementation so we can more easily work on it.
  • Simplify format_args builtin macro implementation. #100277
  • Rewrite and refactor format_args!() builtin macro. #100996
  • Separate CountIsStar from CountIsParam in rustc_parse_format. #101000
  • Replace format flags u32 by enums and bools. #106806
  • Don't re-export private/unstable ArgumentV1 from alloc. #101569
  • Change formatting items to lang items (part of Move format_args!() into AST (and expand it during AST lowering) #106745)
  • Remove all public exports of the lang items, after the beta 1.69 bump: Remove public doc(hidden) core::fmt::rt::v1 #110616
  • Remove the V1 suffix from the ArgumentV1 and FlagV1 types: More core::fmt::rt cleanup. #110766
• Move format args into the AST, so we can do more with it.
  • MCP: Make format_args!() its own AST node (ast::ExprKind::FormatArgs) compiler-team#541
  • Move to AST: Move format_args!() into AST (and expand it during AST lowering) #106745
    • Explore variation: Experiment: variation on #106745 #106770
      • Accidentally solve #69455: Deprioritize fulfillment errors that come from expansions. #106820
    • Work around Exponential (?) time complexity in evaluate_trait_predicate_recursively in rustdoc when proving Send/Sync #106930
• Remove Clippy's dependence on format_args's implementation details, to allow refactoring format_args without having to fix clippy every time.
  • Zulip discussion
  • Update lint implementations Migrate format_args!() lints to to ast::FormatArgs rust-clippy#10233
    • UselessFormat lint: Replace remaining usage of FormatArgsExpn rust-clippy#10561
    • FormatArgs lints: Migrate format_args.rs to rustc_ast::FormatArgs rust-clippy#10484
    • FormatImpl lints: Replace remaining usage of FormatArgsExpn rust-clippy#10561
    • ManualAssert lint: Don't depend on FormatArgsExpn in ManualAssert. rust-clippy#10276
    • ExplicitWrite lint: Replace remaining usage of FormatArgsExpn rust-clippy#10561
    • Write lints: Migrate write.rs to rustc_ast::FormatArgs rust-clippy#10275
    • expect_fun_call lint: Replace remaining usage of FormatArgsExpn rust-clippy#10561
  • Synchronize the cilppy subtree: Update Clippy #110003
• Optimizations for format_args!() within the compiler (independent of std::fmt::Arguments)
  • Inlining and flattening: format_args!() could 'inline' literal arguments #78356
    • Update API docs to allow this for std::fmt::Arguments::as_str(): Allow fmt::Arguments::as_str() to return more Some(_). #106823
    • Implementation as unstable option: Flatten/inline format_args!() and (string and int) literal arguments into format_args!() #106824
    • Enable it by default: Enable flatten-format-args by default. #109999
    • Accidentally introduce a bug: format_args!() inlining/flattening allows for longer lifetimes #110769
    • Fix the bug: Limit lifetime of format_args!() with inlined args. #110770
• Reduce size of FormattingOptions
  • Reduce formatting width and precision to 16 bits #136932
  • Reduce FormattingOptions to 64 bits #136974
• New fmt::Arguments representation to reduce size and allow conversion from &str: New fmt::Arguments representation. #115129
• Reduce amount of (unnecessary) fmt code pulled in
  • Optimize format_args placeholders without options: Display::simple_fmt #104525
• Make sure write!(f, "literal") is just as efficient as f.write_str("literal")
  • perf: improve write_fmt to handle simple strings #121001
  • ... (?)
• Experiment with various ideas for changing format_args and fmt::Arguments.
  • Implement and try out the closure idea. Experiment: fmt::Arguments as closure #101568
    (Impact on compile time too big, because of all the extra code generation.)
  • Implement and try out the "encoded formatting instructions" idea.
    • First partial attempt: [do not merge] fmt::Arguments experiment #84823
    • ...
  • Implement and try out the "two pointers" idea: Experiment: New format_args!() representation #137294
• Implement the winning design
  • ... (?)

[m-ou-se]

Most likely, the best alternative will look vaguely like this:

That is, it tries to:

• Make fmt::Arguments as small as possible. (Two pointers.)
• Move as much data as possible into static storage. (Everything except for the pointers to the arguments, which must be dynamic.)

The most interesting question is what goes in the block with the question marks, the static data that encodes the format string. (Perhaps it could even include the three strings, to save the overhead of the pointers and indirection, at least in the case of tiny strings like these.)

There are many ways to represent a format string in a data structure. There's a trade off to be made between the size of that structure, runtime performance, and complexity.

One of the ideas I want to explore more is to represent it as a single array of 'commands' such as print string "a" set precision to 5 print argument 0 etc. Effectively making a (tiny, trivial) domain specific 'virtual machine' with just ~10 instructions that's easily interpreted by std::fmt::write.

This direction is something I experimented a bit with in #84823, but still requires a lot more exploration to get it to something that can be a good alternative.

Another option we discussed in the libs meeting earlier this year, is to represent it as compiled code instead of a regular data structure. format_args!() would expand to a closure, and fmt::Arguments would effectively be a &dyn Fn. This allows for inlining and optimizing the Display implementations that it uses (which might result in smaller code size if much can be optimized away), but it also means that every single format_args!() will result in its own closure, which can blow up code size and compilation time for programs that do a lot of formatting.

Unfortunately, it takes quite some time to build every single experiment, as it requires a re-implementation of not only fmt::Arguments, but als of the format_args!() macro, every time.

[m-ou-se]

An interesting case is something like format_args!("{} {}", arg0, "string literal"). Ideally, that would optimize to format_args!("{} string literal", arg0), which is an idea that's tracked here: #78356

However, if that second argument is a dynamically chosen &str, we cannot optimize it away, and we end up with an unfortunate amount of indirection thanks to how format_args!() captures all arguments by reference: it captures a &&str. That looks something like this:

It means that the &str needs to be temporarily placed on the stack such that a &&str can reference it. Additionally, it's unfortunate that the entire String as Display implementation is included, even though just f.write_str() would've been enough, as no special formatting options are used.

If we go for the closure idea, we could instead get something that looks like this:

So,

• A compiler-generated structure for the captures, since we now simply make use of the capturing behavior of a regular closure. It could decide to capture a copy of &str instead of requiring a &&str. (It could even just reference the outer stack frame, such that the 'captures' structure is simply the stack frame that already exists.)
• It could inline <String as Display>::fmt and optimize away nearly all of it. (Alternatively, we could teach the builtin format_args!() macro to generate a simple write_str call for a "{}"-formatted &str, instead of a call to Display::fmt.)

[m-ou-se]

A tricky problem with the closure approach, is how to implement fmt::Arguments::as_str(). It's not impossible, but it's a tricky to encode a special case for fmt::Arguments that are just a single static string literal, if fmt::Arguments just encode something like a &dyn Fn. (Without making the structure larger again. It'd be really nice if it fits in a register pair.)

[m-ou-se]

If we do not go for the closure approach, a tricky problem is how to make format_args!("{}", a) expand to include the right <T as Display>::fmt function pointer in the static data, since we don't have a typeof(a) operator in Rust.

Currently we just make use of something like &dyn Display which handles that for us, but that means that the function pointer ends up in the dynamic part together with the pointer to the argument (as part of a wide pointer), instead of separately as part of the static data.

One possibility of handling this is described in #44343, but it's quite tricky to get that right. The last comment there is a comment from me from 2020 saying that I'd try to implement it. I tried it, but it turned out to be quite tricky to get right and make it compile in all cases, and it got messy quite fast. Specifically, creating just a [fn(*const Opaque); N] with that approach works out okay-ish, but creating a structure that also contains other information (flags, precision, string pieces, etc.) gets quite complicated. Perhaps there's an easier approach possible nowadays, maybe with the help of some (to be created) (unstable) const eval related feature.

[joboet]

In the VM approach, the "opcodes" can be encoded together with the static string: since in UTF-8, byte values >= 0xf5 are not allowed, they can be used to encode up to 10 opcodes, which could either specify formatting options or indicate that the next bytes are a pointer to a formatting function. Additionally, by using an "end" opcode, the string pointer does not need to include size, while at the same time allowing internal NUL-bytes.

[kadiwa4]

What about putting all the &'static strs into a single one and then only storing the index where each of the parts end? So for format!("a{}bc{}d", …) there would be a string literal "abcd", stored as a thin pointer to the first byte, and one end index for each slice that needs to be extracted from the string ([1, 3, 4] in this case; to extract "a", "bc" and "d").

This would almost cut the size of the current &'static [&'static str] in half.

[Amanieu]

A tricky problem with the closure approach, is how to implement fmt::Arguments::as_str(). It's not impossible, but it's a tricky to encode a special case for fmt::Arguments that are just a single static string literal, if fmt::Arguments just encode something like a &dyn Fn. (Without making the structure larger again. It'd be really nice if it fits in a register pair.)

Would using a custom trait instead of Fn help here? It would have 2 methods: one which corresponds to the original Fn and one which returns an Option<&'static str>.

[m-ou-se]

I've opened a compiler MCP for changing how format_args!() expands, to make it easier to work on these improvements.

[m-ou-se]

The implementation of the format_args!() builtin macro (compiler/rustc_builtin_macros/src/format.rs) currently takes the output of rustc_parse_format and processes it, resolves numeric and named arguments (e.g. matches {a} to a = 1, etc.), figures out the right display trait (e.g. UpperHex for {:X}) produces diagnostics about invalid options or missing arguments (etc.), and generates the code that format_args!() will expand to that will eventually create a fmt::Arguments object.

It's a lot of code.

Any new implementation of fmt::Arguments will need big modifications to this code.

I'm now working on splitting this code into a part into two steps:

1. Resolving the arguments, resolving the display trait, producing diagnostics/errors, etc.
2. Generating the code.

Between step 1 and 2, there will be a (relatively simple) intermediate representation. Then a new implementation of fmt::Arguments only needs a new implementation of step 2: converting this intermediate representation to code. Then we can leave the first step alone.

Currently, these two steps are quite interwoven, so it'll take some time and effort to separate.

Additionaly, I think it'd be nice if we could delay step 2 until later in the compilation process, making the intermediate representation part of the AST and HIR, which is what my opened an MCP for: rust-lang/compiler-team#541

[m-ou-se]

I made a template PR for those who want to help out by experimenting with a new fmt::Arguments implementation: #101272

Unfortunately, it's a lot of work to try out a new idea for a fmt::Arguments implementation, since it requires not only updating the fmt::Arguments struct and its methods, but also a new core::fmt::write() implementation, and a new format_args!() builtin macro implementation.

The template PR provides a starting point that points out exactly what to implement.

I'll work on getting #100996 merged (which is for now included in the template PR), and will start on the closure approach right after. Please feel free to try out another approach (like that 'VM' idea or something else) and leave a comment here with what you're working on, and ping me when you have something ready to test. :)

There's a few benchmarks here thanks to @mojave2. It'd be nice if we could also include a representative performance benchmark for formatting in https://perf.rust-lang.org/ or at least as an optional #[bench] test in rust-lang/rust, so we have a good way to measure results.

[Kobzol]

We're now in the process of adding an experimental version of runtime benchmarks into rustc-perf (rust-lang/rustc-perf#1423), I'll try to add some fmt benchmarks once/if it gets merged.

[m-ou-se]

Some very promising first results from the closure approach: #101568 (comment)

[m-ou-se]

Update: The compiler MCP for making format_args!() its own ast node has been accepted, and #100996 has been reviewed and approved, and is about to be merged.

The closure approach produces some great results for small programs, but doesn't perform as well in all situations. It also can significantly increase compilation time.

Once #100996 is merged, I'll be much easier to make changes to fmt::Arguments. I'll start with a few small incremental changes that should be easy to review, before continuing with more experimental ideas again.

Now that the compiler MCP has been accepted, I'll also work on moving the data types from ast.rs of #100996 into the actual AST, moving the 'actual' expansion to a later point in the compilation process, to kickstart the work on #78356.