Software Bits

Software Bits

Avoiding allocations at all costs.

Avoiding allocations at all costs.

Or spending CPU cycles to prevent allocations.

While browsing Apache Arrow project, I have noticed the usage of a string replacement function:

let re_pattern = pat.replace("%", ".*").replace("_", ".");

and started to wonder what happens when pat contains neither % nor _. I expected replace function to return the original string although its documentation got me worried:

replace creates a new String, and copies the data from this string slice into it. While doing so, it attempts to find matches of a pattern. If it finds any, it replaces them with the replacement string slice.

So let's take a look at the source code

pub fn replace<'a, P: Pattern<'a>>(&'a self, from: P, to: &str) -> String {
        let mut result = String::new();
...

So replace most certainly allocates a new String no matter what. What does it mean in practice? Let's use 2 benchmarks to compare performance of a replacement without a match and a check for a match:

    #[bench]
    fn bench_naive_replace_no_match(b: &mut Bencher) {
        b.iter(|| "foobarbazz".replace("0", "foo"))
    }

    #[bench]
    fn bench_replace_with_check_no_match(b: &mut Bencher) {
        b.iter(|| "foobarbazz".contains("0"))
    }

The numbers are somewhat expected and demonstrate that check is ~5X faster than a replacement without a match:

test tests::bench_naive_replace_no_match      ... bench:         109 ns/iter (+/- 10)
test tests::bench_replace_with_check_no_match ... bench:          22 ns/iter (+/- 4)

Go's strings.Replace takes into account this fact and performs a number of checks to avoid allocations:

func Replace(s, old, new string, n int) string {
    if old == new || n == 0 {
        return s // avoid allocation
    }

    // Compute number of replacements.
    if m := Count(s, old); m == 0 {
        return s // avoid allocation
    } else if n < 0 || m < n {
        n = m
    }
...

Arguably, allocations are more expensive in managed languages like Go, since in addition to allocation cost, they contribute to GC pressure, so it's not surprising to see this level of attention in Go's codebase. At the same time, depending on how common no-match scenario is, it may be worthwhile to handle it separately in Rust.

 
Share this