Auto merge of #50340 - Emerentius:master, r=alexcrichton

optimize joining for slices

This improves the speed of string joining up to 3x.
It removes the boolean flag check every iteration, eliminates repeated bounds checks and adds a fast paths for small separators up to a len of 4 bytes
These optimizations gave me ~10%, ~50% and ~80% improvements respectively over the previous speed. Those are multiplicative.

3x improvement happens for the optimal case of joining many small strings together in my microbenchmarks. Improvements flatten out for larger strings of course as more time is spent copying bits around. I've run a few benchmarks [with this code](https://github.com/Emerentius/join_bench). They are pretty noise despite high iteration counts, but in total one can see the trends.

```
len_separator  len_string   n_strings     speedup
           4          10          10        2.38
           4          10         100        3.41
           4          10        1000        3.43
           4          10       10000        3.25
           4         100          10        2.23
           4         100         100        2.73
           4         100        1000        1.33
           4         100       10000        1.14
           4        1000          10        1.33
           4        1000         100        1.15
           4        1000        1000        1.08
           4        1000       10000        1.04
          10          10          10        1.61
          10          10         100        1.74
          10          10        1000        1.77
          10          10       10000        1.75
          10         100          10        1.58
          10         100         100        1.65
          10         100        1000        1.24
          10         100       10000        1.12
          10        1000          10        1.23
          10        1000         100        1.11
          10        1000        1000        1.05
          10        1000       10000       0.997
         100          10          10        1.66
         100          10         100        1.78
         100          10        1000        1.28
         100          10       10000        1.16
         100         100          10        1.37
         100         100         100        1.26
         100         100        1000        1.09
         100         100       10000         1.0
         100        1000          10        1.19
         100        1000         100        1.12
         100        1000        1000        1.05
         100        1000       10000        1.12
```

The string joining with small or empty separators is now ~50% faster than the old concatenation (small strings). The same approach can also improve the performance of joining into vectors.

If this approach is acceptable, I can apply it for concatenation and for vectors as well. Alternatively, concat could just call `.join("")`.

2 files changed, 22 insertions, 0 deletions

diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs
index 6fd0b33f02a..3b7eec38609 100644
--- a/src/liballoc/tests/slice.rs
+++ b/src/liballoc/tests/slice.rs
@@ -610,6 +610,15 @@ fn test_join() {
 }
 
 #[test]
+fn test_join_nocopy() {
+    let v: [String; 0] = [];
+    assert_eq!(v.join(","), "");
+    assert_eq!(["a".to_string(), "ab".into()].join(","), "a,ab");
+    assert_eq!(["a".to_string(), "ab".into(), "abc".into()].join(","), "a,ab,abc");
+    assert_eq!(["a".to_string(), "ab".into(), "".into()].join(","), "a,ab,");
+}
+
+#[test]
 fn test_insert() {
     let mut a = vec![1, 2, 4];
     a.insert(2, 3);
diff --git a/src/liballoc/tests/str.rs b/src/liballoc/tests/str.rs
index d11bf5dc3e9..03d295d16e6 100644
--- a/src/liballoc/tests/str.rs
+++ b/src/liballoc/tests/str.rs
@@ -162,6 +162,19 @@ fn test_join_for_different_lengths() {
     test_join!("-a-bc", ["", "a", "bc"], "-");
 }
 
+// join has fast paths for small separators up to 4 bytes
+// this tests the slow paths.
+#[test]
+fn test_join_for_different_lengths_with_long_separator() {
+    assert_eq!("～～～～～".len(), 15);
+
+    let empty: &[&str] = &[];
+    test_join!("", empty, "～～～～～");
+    test_join!("a", ["a"], "～～～～～");
+    test_join!("a～～～～～b", ["a", "b"], "～～～～～");
+    test_join!("～～～～～a～～～～～bc", ["", "a", "bc"], "～～～～～");
+}
+
 #[test]
 fn test_unsafe_slice() {
     assert_eq!("ab", unsafe {"abc".slice_unchecked(0, 2)});