Rollup merge of #48657 - sinkuu:opt_str_repeat, r=dtolnay

Optimize str::repeat

Improves the performance of `str::repeat` by bulk copying. Here is the benchmarks of `"abcde".repeat(n)`:

|`n`|old [ns/iter]|new [ns/iter]|diff [%]|
---|---|---|---
|1|27.205|27.421|+0.794|
|2|27.500|27.516|+0.0581|
|3|27.923|27.648|-0.985|
|4|31.206|30.145|-3.40|
|5|35.144|31.861|-9.34|
|7|43.131|34.621|-19.7|
|10|54.945|36.203|-34.1|
|100|428.31|52.895|-87.7|

2 files changed, 55 insertions, 3 deletions

diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index d250cfe1880..cb43d5bee78 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -124,6 +124,7 @@
 #![feature(allocator_internals)]
 #![feature(on_unimplemented)]
 #![feature(exact_chunks)]
+#![feature(pointer_methods)]
 
 #![cfg_attr(not(test), feature(fused, fn_traits, placement_new_protocol, swap_with_slice, i128))]
 #![cfg_attr(test, feature(test, box_heap))]
diff --git a/src/liballoc/str.rs b/src/liballoc/str.rs
index a00e3d17dd0..64e815b1fba 100644
--- a/src/liballoc/str.rs
+++ b/src/liballoc/str.rs
@@ -43,6 +43,7 @@ use core::str as core_str;
 use core::str::pattern::Pattern;
 use core::str::pattern::{Searcher, ReverseSearcher, DoubleEndedSearcher};
 use core::mem;
+use core::ptr;
 use core::iter::FusedIterator;
 use std_unicode::str::{UnicodeStr, Utf16Encoder};
 
@@ -2066,9 +2067,59 @@ impl str {
     /// ```
     #[stable(feature = "repeat_str", since = "1.16.0")]
     pub fn repeat(&self, n: usize) -> String {
-        let mut s = String::with_capacity(self.len() * n);
-        s.extend((0..n).map(|_| self));
-        s
+        if n == 0 {
+            return String::new();
+        }
+
+        // If `n` is larger than zero, it can be split as
+        // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.
+        // `2^expn` is the number represented by the leftmost '1' bit of `n`,
+        // and `rem` is the remaining part of `n`.
+
+        // Using `Vec` to access `set_len()`.
+        let mut buf = Vec::with_capacity(self.len() * n);
+
+        // `2^expn` repetition is done by doubling `buf` `expn`-times.
+        buf.extend(self.as_bytes());
+        {
+            let mut m = n >> 1;
+            // If `m > 0`, there are remaining bits up to the leftmost '1'.
+            while m > 0 {
+                // `buf.extend(buf)`:
+                unsafe {
+                    ptr::copy_nonoverlapping(
+                        buf.as_ptr(),
+                        (buf.as_mut_ptr() as *mut u8).add(buf.len()),
+                        buf.len(),
+                    );
+                    // `buf` has capacity of `self.len() * n`.
+                    let buf_len = buf.len();
+                    buf.set_len(buf_len * 2);
+                }
+
+                m >>= 1;
+            }
+        }
+
+        // `rem` (`= n - 2^expn`) repetition is done by copying
+        // first `rem` repetitions from `buf` itself.
+        let rem_len = self.len() * n - buf.len(); // `self.len() * rem`
+        if rem_len > 0 {
+            // `buf.extend(buf[0 .. rem_len])`:
+            unsafe {
+                // This is non-overlapping since `2^expn > rem`.
+                ptr::copy_nonoverlapping(
+                    buf.as_ptr(),
+                    (buf.as_mut_ptr() as *mut u8).add(buf.len()),
+                    rem_len,
+                );
+                // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`).
+                let buf_cap = buf.capacity();
+                buf.set_len(buf_cap);
+            }
+        }
+
+        unsafe { String::from_utf8_unchecked(buf) }
     }
 
     /// Checks if all characters in this string are within the ASCII range.