Auto merge of #39356 - krdln:format-with-capacity, r=aturon

Use `String::with_capacity` in `format!`

Add an `Arguments::estimated_capacity` to estimate the length of formatted text and use it in `std::fmt::format` as the initial capacity of the buffer.

The capacity is calculated based on the literal parts of format string, see the details in the implementation.

Some benches:
```rust
empty:       format!("{}", black_box(""))
literal:     format!("Literal")
long:        format!("Hello Hello Hello Hello, {}!", black_box("world"))
long_rev:    format!("{}, hello hello hello hello!", black_box("world"))
long_rev_2:  format!("{}{}, hello hello hello hello!", 1, black_box("world"))
short:       format!("Hello, {}!", black_box("world"))
short_rev:   format!("{}, hello!", black_box("world"))
short_rev_2: format!("{}{}, hello!", 1, black_box("world"))
surround:    format!("aaaaa{}ccccc{}eeeee", black_box("bbbbb"), black_box("eeeee"))
two_spaced:  format!("{} {}", black_box("bbbbb"), black_box("eeeee"))
worst_case:  format!("{} a long piece...", black_box("and even longer argument. not sure why it has to be so long"))
```
```
 empty        25            28                      3   12.00%
 literal      35            29                     -6  -17.14%
 long         80            46                    -34  -42.50%
 long_rev     79            45                    -34  -43.04%
 long_rev_2   111           66                    -45  -40.54%
 short        73            46                    -27  -36.99%
 short_rev    74            76                      2    2.70%
 short_rev_2  107           108                     1    0.93%
 surround     142           65                    -77  -54.23%
 two_spaced   111           115                     4    3.60%
 worst_case   89            101                    12   13.48%
```

4 files changed, 39 insertions, 1 deletions

diff --git a/src/libcollections/fmt.rs b/src/libcollections/fmt.rs
index 883417e9f4e..bd74848a01d 100644
--- a/src/libcollections/fmt.rs
+++ b/src/libcollections/fmt.rs
@@ -539,7 +539,8 @@ use string;
 /// [format!]: ../macro.format.html
 #[stable(feature = "rust1", since = "1.0.0")]
 pub fn format(args: Arguments) -> string::String {
-    let mut output = string::String::new();
+    let capacity = args.estimated_capacity();
+    let mut output = string::String::with_capacity(capacity);
     let _ = output.write_fmt(args);
     output
 }
diff --git a/src/libcore/fmt/mod.rs b/src/libcore/fmt/mod.rs
index 2ba7d6e8bd1..a989f914db6 100644
--- a/src/libcore/fmt/mod.rs
+++ b/src/libcore/fmt/mod.rs
@@ -265,6 +265,32 @@ impl<'a> Arguments<'a> {
             args: args
         }
     }
+
+    /// Estimates the length of the formatted text.
+    ///
+    /// This is intended to be used for setting initial `String` capacity
+    /// when using `format!`. Note: this is neither the lower nor upper bound.
+    #[doc(hidden)] #[inline]
+    #[unstable(feature = "fmt_internals", reason = "internal to format_args!",
+               issue = "0")]
+    pub fn estimated_capacity(&self) -> usize {
+        let pieces_length: usize = self.pieces.iter()
+            .map(|x| x.len()).sum();
+
+        if self.args.is_empty() {
+            pieces_length
+        } else if self.pieces[0] == "" && pieces_length < 16 {
+            // If the format string starts with an argument,
+            // don't preallocate anything, unless length
+            // of pieces is significant.
+            0
+        } else {
+            // There are some arguments, so any additional push
+            // will reallocate the string. To avoid that,
+            // we're "pre-doubling" the capacity here.
+            pieces_length.checked_mul(2).unwrap_or(0)
+        }
+    }
 }
 
 /// This structure represents a safely precompiled version of a format string
diff --git a/src/libcoretest/fmt/mod.rs b/src/libcoretest/fmt/mod.rs
index ed33596e1c2..5d204c7d523 100644
--- a/src/libcoretest/fmt/mod.rs
+++ b/src/libcoretest/fmt/mod.rs
@@ -28,3 +28,13 @@ fn test_pointer_formats_data_pointer() {
     assert_eq!(format!("{:p}", s), format!("{:p}", s.as_ptr()));
     assert_eq!(format!("{:p}", b), format!("{:p}", b.as_ptr()));
 }
+
+#[test]
+fn test_estimated_capacity() {
+    assert_eq!(format_args!("").estimated_capacity(), 0);
+    assert_eq!(format_args!("{}", "").estimated_capacity(), 0);
+    assert_eq!(format_args!("Hello").estimated_capacity(), 5);
+    assert_eq!(format_args!("Hello, {}!", "").estimated_capacity(), 16);
+    assert_eq!(format_args!("{}, hello!", "World").estimated_capacity(), 0);
+    assert_eq!(format_args!("{}. 16-bytes piece", "World").estimated_capacity(), 32);
+}
diff --git a/src/libcoretest/lib.rs b/src/libcoretest/lib.rs
index 87f3afd6889..e06b757691e 100644
--- a/src/libcoretest/lib.rs
+++ b/src/libcoretest/lib.rs
@@ -34,6 +34,7 @@
 #![feature(ordering_chaining)]
 #![feature(ptr_unaligned)]
 #![feature(move_cell)]
+#![feature(fmt_internals)]
 
 extern crate core;
 extern crate test;