Hacker News Reader

Comment by giancarlostoro | Hacker News Reader

I am curious if RipGrep is faster or would be even faster if using StringZilla. RipGrep is insanely fast as it is.

I’m not an active RipGrep user, so can’t speak for all usage patterns. My guess: for plain substring searches, you probably won’t see much difference. Where StringZilla may potentially help is in character-set searches.

Nope. ripgrep uses the `memchr` crate for substring search, and in my benchmarks it's generally faster than stringzilla:

    $ rebar cmp results.csv --intersection -f huge
    benchmark                                        rust/memchr/memmem/prebuilt  stringzilla/memmem/oneshot
    ---------                                        ---------------------------  --------------------------
    memmem/pathological/md5-huge-no-hash             47.4 GB/s (1.00x)            38.1 GB/s (1.25x)
    memmem/pathological/md5-huge-last-hash           40.3 GB/s (1.00x)            23.4 GB/s (1.72x)
    memmem/pathological/rare-repeated-huge-tricky    40.4 GB/s (1.04x)            42.0 GB/s (1.00x)
    memmem/pathological/rare-repeated-huge-match     1977.7 MB/s (1.00x)          563.3 MB/s (3.51x)
    memmem/subtitles/common/huge-en-that             35.9 GB/s (1.00x)            25.3 GB/s (1.42x)
    memmem/subtitles/common/huge-en-you              15.9 GB/s (1.00x)            9.5 GB/s (1.67x)
    memmem/subtitles/common/huge-en-one-space        1376.4 MB/s (1.00x)          1364.0 MB/s (1.01x)
    memmem/subtitles/common/huge-ru-that             29.0 GB/s (1.00x)            15.5 GB/s (1.87x)
    memmem/subtitles/common/huge-ru-not              16.0 GB/s (1.00x)            3.5 GB/s (4.53x)
    memmem/subtitles/common/huge-ru-one-space        2.6 GB/s (1.00x)             2.4 GB/s (1.08x)
    memmem/subtitles/common/huge-zh-that             31.2 GB/s (1.00x)            23.8 GB/s (1.31x)
    memmem/subtitles/common/huge-zh-do-not           19.4 GB/s (1.00x)            12.1 GB/s (1.59x)
    memmem/subtitles/common/huge-zh-one-space        5.3 GB/s (1.05x)             5.6 GB/s (1.00x)
    memmem/subtitles/never/huge-en-john-watson       41.2 GB/s (1.00x)            31.2 GB/s (1.32x)
    memmem/subtitles/never/huge-en-all-common-bytes  47.9 GB/s (1.00x)            37.5 GB/s (1.28x)
    memmem/subtitles/never/huge-en-some-rare-bytes   43.4 GB/s (1.00x)            42.7 GB/s (1.02x)
    memmem/subtitles/never/huge-en-two-space         42.2 GB/s (1.00x)            30.7 GB/s (1.37x)
    memmem/subtitles/never/huge-ru-john-watson       42.2 GB/s (1.00x)            42.1 GB/s (1.00x)
    memmem/subtitles/never/huge-zh-john-watson       47.6 GB/s (1.00x)            34.0 GB/s (1.40x)
    memmem/subtitles/rare/huge-en-sherlock-holmes    40.8 GB/s (1.05x)            42.9 GB/s (1.00x)
    memmem/subtitles/rare/huge-en-sherlock           36.7 GB/s (1.16x)            42.5 GB/s (1.00x)
    memmem/subtitles/rare/huge-en-medium-needle      47.7 GB/s (1.00x)            31.3 GB/s (1.52x)
    memmem/subtitles/rare/huge-en-long-needle        44.5 GB/s (1.00x)            32.0 GB/s (1.39x)
    memmem/subtitles/rare/huge-en-huge-needle        45.7 GB/s (1.00x)            33.4 GB/s (1.37x)
    memmem/subtitles/rare/huge-ru-sherlock-holmes    42.1 GB/s (1.00x)            42.2 GB/s (1.00x)
    memmem/subtitles/rare/huge-ru-sherlock           42.3 GB/s (1.01x)            42.9 GB/s (1.00x)
    memmem/subtitles/rare/huge-zh-sherlock-holmes    46.7 GB/s (1.00x)            33.1 GB/s (1.41x)
    memmem/subtitles/rare/huge-zh-sherlock           47.4 GB/s (1.00x)            42.8 GB/s (1.11x)

But I would say they are overall pretty competitive.

If you want to run the benchmarks yourself, you can. First, get rebar[1]. Then, from the root of the `memchr` repository[2]:

    $ rebar build -e 'rust/memchr/memmem/prebuilt' -e 'stringzilla/memmem/oneshot'
    stringzilla/memmem/oneshot: running: cd "benchmarks/./engines/stringzilla" && "cargo" "build" "--release"
    stringzilla/memmem/oneshot: build complete for version 3.12.3
    rust/memchr/memmem/prebuilt: running: cd "benchmarks/./engines/rust-memchr" && "cargo" "build" "--release"
    rust/memchr/memmem/prebuilt: build complete for version 2.7.4
    $ rebar measure -e 'rust/memchr/memmem/prebuilt' -e 'stringzilla/memmem/oneshot' | tee results.csv
    $ rebar rank results.csv
    Engine                       Version  Geometric mean of speed ratios  Benchmark count
    ------                       -------  ------------------------------  ---------------
    rust/memchr/memmem/prebuilt  2.7.4    1.14                            57
    stringzilla/memmem/oneshot   3.12.3   1.43                            54
    $ rebar cmp results.csv --intersection -f never/huge
    benchmark                                        rust/memchr/memmem/prebuilt  stringzilla/memmem/oneshot
    ---------                                        ---------------------------  --------------------------
    memmem/subtitles/never/huge-en-john-watson       41.2 GB/s (1.00x)            31.2 GB/s (1.32x)
    memmem/subtitles/never/huge-en-all-common-bytes  47.9 GB/s (1.00x)            37.5 GB/s (1.28x)
    memmem/subtitles/never/huge-en-some-rare-bytes   43.4 GB/s (1.00x)            42.7 GB/s (1.02x)
    memmem/subtitles/never/huge-en-two-space         42.2 GB/s (1.00x)            30.7 GB/s (1.37x)
    memmem/subtitles/never/huge-ru-john-watson       42.2 GB/s (1.00x)            42.1 GB/s (1.00x)
    memmem/subtitles/never/huge-zh-john-watson       47.6 GB/s (1.00x)            34.0 GB/s (1.40x)

[1]: https://github.com/BurntSushi/rebar

[2]: https://github.com/BurntSushi/memchr

It’s a very nice and detailed benchmark suite! Great effort! Can you please share the CPU model you are running on? I suspect it’s an x86 CPU without AVX-512 support.

i9-12900K, x86-64.

There is definitely no AVX-512 support on my CPU. Which is also true for most of my users. I don't bother with AVX-512 for that reason.

Another substantial population of my users are on aarch64, which memchr has optimizations for. I don't think StringZilla does.

Makes sense! I mostly focus on newer AVX-512 variants as opposed to older AVX2-only CPUs. As for aarch64, it is supported with both NEON, SVE, and SVE2 kernels for some tasks. The last two are rarely useful, unless you run on AWS Graviton 3 (previous gen) or some of the supercomputers with custom chips like Fujitsu A64FX.

> newer AVX-512 variants as opposed to older AVX2-only CPUs

This is exactly my issue with targeting AVX-512. It isn't just absent on "older AVX2-only CPUs." It's also absent on many "newer AVX2-only CPUs." For example, the i9-14900K. I don't think any of the other newer Intel CPUs have AVX-512 either. And historically, whether an x86-64 CPU supported AVX-512 at all was hit or miss.

AVX-512 has been around for a very long time now, and it has just never been consistently available.

It’s mainly available in data centers, but yes missing in consumer parts. And for a while even in data centers you wanted to be careful about using it due to Intel’s issues with clock downscaling but that hasn’t been true for a few years.

The consumer situation is changing. A few years ago, when I was working with a team on some closed source HPC stuff, we’ve got everyone Tiger Lake-based laptops to simplify AVX-512 R&D. Now, Zen4-based desktop CPUs also support it.

But its fair to say that I’m mostly focusing on the datacenter/supercomputing hardware, both on the x86 and Arm side.

If you’re targeting AVX-512 Intel consumer it’s pointless. But yes, AMD does continue to ship AVX-512 chips so completely ignoring 512 on consumer isn’t ideal.

Could you elaborate on SVE and SVE2? Is that because it's only 128 bits? I think my Macbook (Apple silicon) is one of the two

Yes, at the scale of 128-bit registers NEON is mostly enough, except for a few categories of instructions missing in that ISA subset, like scatter/gather ops, that can yield 30% boost over serial memory accesses: https://github.com/ashvardanian/less_slow.cpp/releases/tag/v...

When I implemented SIMD-accelerated string functions for FreeBSD's libc, I briefly looked at Stringzilla, but the code didn't look particularly interesting or fast. So no surprise here.

Thank you! I love RipGrep, its the one thing I install, use it for everything, even non-dev stuff.

Thank you for memchr- really!

Reply on news.ycombinator.com