String::push is slow
#116235
Comments
rustbot
added
the
needs-triage
|
Since you already wrote the code, make a PR? Though you might want to look into using |
the8472
added
I-slow
|
the debug asserts rust/library/core/src/slice/index.rs Lines 237 to 240 in 42faef5 |
|
I have no opinion on push_unchecked, you can just make it a private function if you don't have a reason to expose it. |
|
@the8472 it seems that the debug assert only applies if you compile core from source. As for I managed to make it identical to the |
|
If you want to add API you may want to open an ACP first. |
|
Although the Another solution is to add a new function |
|
Another thing to note is that this version, unlike the current one, is unable to elide the capacity check in a simple ASCII push loop with a pre-allocated string. Both versions fail on non-ASCII and on long strings, though. It seems that the current version is able to elide the check because it uses If we put the reserve call behind Despite the issue, my version still outperforms the original in a benchmark with pre-allocated strings. current new (you can see a small regression in however, both versions work much worse than bench.rs#![no_std]
#![feature(test)]
extern crate alloc;
extern crate test;
use alloc::string::String;
use test::{black_box, Bencher};
// #[inline]
// fn push(s: &mut String, ch: char) {
// s.push(ch);
// }
#[inline]
fn push(s: &mut String, ch: char) {
s.reserve(ch.len_utf8());
unsafe { s.push_unchecked(ch) };
}
const TAG_CONT: u8 = 0b1000_0000;
const TAG_TWO_B: u8 = 0b1100_0000;
const TAG_THREE_B: u8 = 0b1110_0000;
const TAG_FOUR_B: u8 = 0b1111_0000;
const MAX_ONE_B: u32 = 0x80;
const MAX_TWO_B: u32 = 0x800;
const MAX_THREE_B: u32 = 0x10000;
#[inline]
const fn len_utf8(code: u32) -> usize {
if code < MAX_ONE_B {
1
} else if code < MAX_TWO_B {
2
} else if code < MAX_THREE_B {
3
} else {
4
}
}
#[inline]
unsafe fn encode_utf8_raw_unchecked(code: u32, dst: &mut [u8]) -> &mut [u8] {
let len = len_utf8(code);
match len {
1 => {
*dst.get_unchecked_mut(0) = code as u8;
}
2 => {
*dst.get_unchecked_mut(0) = (code >> 6 & 0x1F) as u8 | TAG_TWO_B;
*dst.get_unchecked_mut(1) = (code & 0x3F) as u8 | TAG_CONT;
}
3 => {
*dst.get_unchecked_mut(0) = (code >> 12 & 0x0F) as u8 | TAG_THREE_B;
*dst.get_unchecked_mut(1) = (code >> 6 & 0x3F) as u8 | TAG_CONT;
*dst.get_unchecked_mut(2) = (code & 0x3F) as u8 | TAG_CONT;
}
4 => {
*dst.get_unchecked_mut(0) = (code >> 18 & 0x07) as u8 | TAG_FOUR_B;
*dst.get_unchecked_mut(1) = (code >> 12 & 0x3F) as u8 | TAG_CONT;
*dst.get_unchecked_mut(2) = (code >> 6 & 0x3F) as u8 | TAG_CONT;
*dst.get_unchecked_mut(3) = (code & 0x3F) as u8 | TAG_CONT;
}
_ => core::hint::unreachable_unchecked(),
};
dst.get_unchecked_mut(..len)
}
trait PushUnchecked<T> {
unsafe fn push_unchecked(&mut self, value: T);
}
impl PushUnchecked<char> for String {
#[inline]
unsafe fn push_unchecked(&mut self, ch: char) {
let len = self.len();
let count = ch.len_utf8();
let spare = core::slice::from_raw_parts_mut(
self.as_mut_vec().as_mut_ptr().add(len),
self.capacity() - len,
);
encode_utf8_raw_unchecked(ch as u32, spare);
self.as_mut_vec().set_len(len + count);
}
}
const ITERATIONS: u64 = 10_000;
#[bench]
fn bench_push_1_byte_prealloc(bencher: &mut Bencher) {
const CHAR: char = '0';
assert_eq!(CHAR.len_utf8(), 1);
bencher.bytes = ITERATIONS;
bencher.iter(|| {
let mut s = String::with_capacity(ITERATIONS as _);
for _ in 0..ITERATIONS {
push(&mut s, CHAR);
}
s
// vec![CHAR; ITERATIONS as _]
});
}
#[bench]
fn bench_push_2_bytes_prealloc(bencher: &mut Bencher) {
const CHAR: char = 'д';
assert_eq!(CHAR.len_utf8(), 2);
bencher.bytes = 2 * ITERATIONS;
bencher.iter(|| {
let mut s = String::with_capacity((2 * ITERATIONS) as _);
for _ in 0..ITERATIONS {
push(&mut s, CHAR);
}
s
// vec![CHAR; ITERATIONS as _]
});
}
#[bench]
fn bench_push_3_bytes_prealloc(bencher: &mut Bencher) {
const CHAR: char = '❗';
assert_eq!(CHAR.len_utf8(), 3);
bencher.bytes = 3 * ITERATIONS;
bencher.iter(|| {
let mut s = String::with_capacity((3 * ITERATIONS) as _);
for _ in 0..ITERATIONS {
push(&mut s, CHAR);
}
s
// vec![CHAR; ITERATIONS as _]
});
}
#[bench]
fn bench_push_4_bytes_prealloc(bencher: &mut Bencher) {
const CHAR: char = '🤨';
assert_eq!(CHAR.len_utf8(), 4);
bencher.bytes = 4 * ITERATIONS;
bencher.iter(|| {
let mut s = String::with_capacity((4 * ITERATIONS) as _);
for _ in 0..ITERATIONS {
push(&mut s, CHAR);
}
s
// vec![CHAR; ITERATIONS as _]
});
}
#[bench]
fn bench_push_1_byte_prealloc_blackbox(bencher: &mut Bencher) {
const CHAR: char = '0';
assert_eq!(CHAR.len_utf8(), 1);
bencher.bytes = ITERATIONS;
bencher.iter(|| {
let mut s = String::with_capacity(ITERATIONS as _);
for _ in 0..black_box(ITERATIONS) {
push(&mut s, black_box(CHAR));
}
s
});
}
#[bench]
fn bench_push_2_bytes_prealloc_blackbox(bencher: &mut Bencher) {
const CHAR: char = 'д';
assert_eq!(CHAR.len_utf8(), 2);
bencher.bytes = 2 * ITERATIONS;
bencher.iter(|| {
let mut s = String::with_capacity((2 * ITERATIONS) as _);
for _ in 0..black_box(ITERATIONS) {
push(&mut s, black_box(CHAR));
}
s
});
}
#[bench]
fn bench_push_3_bytes_prealloc_blackbox(bencher: &mut Bencher) {
const CHAR: char = '❗';
assert_eq!(CHAR.len_utf8(), 3);
bencher.bytes = 3 * ITERATIONS;
bencher.iter(|| {
let mut s = String::with_capacity((3 * ITERATIONS) as _);
for _ in 0..black_box(ITERATIONS) {
push(&mut s, black_box(CHAR));
}
s
});
}
#[bench]
fn bench_push_4_bytes_prealloc_blackbox(bencher: &mut Bencher) {
const CHAR: char = '🤨';
assert_eq!(CHAR.len_utf8(), 4);
bencher.bytes = 4 * ITERATIONS;
bencher.iter(|| {
let mut s = String::with_capacity((4 * ITERATIONS) as _);
for _ in 0..black_box(ITERATIONS) {
push(&mut s, black_box(CHAR));
}
s
});
} |
An alternative implementation of
String::push, which reserves space if needed and then performspush_unchecked, gives a significant performance improvement.current
push:new
push:bench.rs
It's worth noting that the current
String::pushimplementation encodes characters into a temporary zero-initialized buffer. The zeroing alone is an unnecessary instruction, but this method is used in several places, notablyString::insertand the defaultWrite::write_char.The text was updated successfully, but these errors were encountered: