]> git.lizzy.rs Git - rust.git/commit
Auto merge of #50340 - Emerentius:master, r=alexcrichton
authorbors <bors@rust-lang.org>
Fri, 1 Jun 2018 16:16:30 +0000 (16:16 +0000)
committerbors <bors@rust-lang.org>
Fri, 1 Jun 2018 16:16:30 +0000 (16:16 +0000)
commit747e655010dd200b4faef1db0910f6097920b58e
tree5231dffae509e7321a329ef6d3a3db25bdedd939
parentf91323129000b20a5e3590d03fb3775bf73d5082
parent12bd28874697d600d347518c8636053b92e81801
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("")`.