RFC: Upgrade format output to a type more efficient than String

[marcusklaas]

Rustfmt spends a lot of time concatenating strings. This involves many allocations, memcpys and deallocations. Common operations on types like ropes have much better time complexity than standard strings. Unfortunately, rustfmt is fairly fixed on using these String values to represent formatted code. Ideally, the formatting code should be more flexible as to its output type. That way, it would be very easy to experiment with other types and observe their effects on performance. Below is a rough proposal on how this could be achieved gradually, without a huge overhaul or breakage.

1. gradually replace the return type of formatting functions from Option<String> to Option<FmtString>, where FmtString is just an alias for String
2. introduce a custom trait abstracting common string operations like to_owned, push_str and push and implement it for String
3. replace method calls to String specific functions with calls to methods in the abstract trait in the
   relevant functions
4. the format! macro is also highly specific to Strings. Replace these invocations by a custom macro call doing string-like concatenation using the new trait

After this, switching to a new output type should be as simple as implementing this custom trait for your favourite string representation and setting the FmtString alias to it.

This will still be a very big undertaking, but I believe that steps 1 through 4 can be done without breaking anything. Some steps can even be done partially. And it should be worth the effort, as there are many performance gains to be had.

Proof of concept

[nrc]

I think we could get some of the way by just using a more efficient String in the FileMap and continuing using Rust strings in the visitors. That would be much easier to implement and should show the scale of the speedup we can expect

[nrc]

cc #338

[marcusklaas]

Doesn't FileMap already use a string variant that is at least fairly efficient for its task, namely StringBuffer?

[nrc]

It does, or at least tries, but it might in fact not be very efficient, or we might be able to do better. Not sure if the profiling tells us about that?