Show HN: Krep a High-Performance String Search Utility Written in C

Those CPU features (AVX2 and whatnot) need to be detected at runtime, too, however.

Those ifdefs only detect if the compiler supports them, i.e. at build-time only.

So... your program only compiles with AVX2 and others if the compiler supports them; so you should compile where the compiler has all those features (because you want everything to be compiled into one executable, of course), and then use runtime checks to make sure the CPU on which the program is run has actually support for AVX2, for example, as it can select the best implementation based on the available CPU features.

To make things a bit more complicated, let me quote a part from one of the projects he has: "The detection is performed at configure time through both CPUID flags and actual instruction execution tests on the host machine, verifying support in both the CPU and operating system.". Currently what you are doing is the "OS", or rather, compiler, since you are using only macro definitions.

Once you add this, then "Automatically leverages SSE4.2 and AVX2 instructions when available for maximum throughput." from the list of features on the website will be correct / accurate.

If interested, someone I know (or rather, follow) has a single header file for detecting CPU features at runtime (for C), and he also has a build-time detection one, but that has much more features.

You can read my blog post about the project at https://dev.to/daviducolo/introducing-krep-building-a-high-p...

Homepage shows it significantly faster than ripgrep. Impressive. Would like to see how it compares across the entire ripgrep's benchmark suite[1], which also includes a few other similar utilities.

edit: Getting an error related to madvise(). Had to insert '-D_GNU_SOURCE' in Makefile's CFLAGS.

[1]: https://github.com/BurntSushi/ripgrep/blob/master/benchsuite...

Where are the test cases?

E.g. the chunk boundary stuff in the multi-threaded file search is something that would make me nervous.

It brings new edge cases into a simple search, and those edge cases are not directly related to features in the data; just to the happenstance of where the chunk boundaries land.

Just by adding one character to a file, a character that obviously lies far outside of any match, we shift the boundaries such that a match could break megabytes away from the insertion.

How do you handle disk errors and file mapping?

To give more context, if there is a disk error (logical, physical, etc.), an "fread" would simply return an error, it won't interfere with the rest.

But with memory mapped files, you have to deal this in someway. For example on Windows, through SEH (__try / __except) around blocks reading (or writing) to memory mapped files.

Just wondering...

This wouldn't build for me, so I had to apply the patch suggested by a sibling comment.

Once I got it building, my first benchmark attempt shows it as being slower:

    $ curl -LO 'https://burntsushi.net/stuff/subtitles2016-sample.en.gz'
      % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                     Dload  Upload   Total   Spent    Left  Speed
    100  265M  100  265M    0     0  48.6M      0  0:00:05  0:00:05 --:--:-- 49.9M
    $ gzip -d subtitles2016-sample.en.gz
    $ hyperfine --ignore-failure "rg -c 'ZQZQZQZQ' subtitles2016-sample.en" "krep -c 'ZQZQZQZQ' subtitles2016-sample.en"
    Benchmark 1: rg -c 'ZQZQZQZQ' subtitles2016-sample.en
      Time (mean ± σ):      80.7 ms ±   1.6 ms    [User: 57.7 ms, System: 22.7 ms]
      Range (min … max):    75.3 ms …  83.3 ms    35 runs

      Warning: Ignoring non-zero exit code.

    Benchmark 2: krep -c 'ZQZQZQZQ' subtitles2016-sample.en
      Time (mean ± σ):     122.8 ms ±   1.4 ms    [User: 372.6 ms, System: 24.4 ms]
      Range (min … max):   120.2 ms … 125.5 ms    24 runs

    Summary
      rg -c 'ZQZQZQZQ' subtitles2016-sample.en ran
        1.52 ± 0.03 times faster than krep -c 'ZQZQZQZQ' subtitles2016-sample.en

    $ hyperfine "rg -c 'the' subtitles2016-sample.en" "krep -c 'the' subtitles2016-sample.en"
    Benchmark 1: rg -c 'the' subtitles2016-sample.en
      Time (mean ± σ):     411.8 ms ±   3.6 ms    [User: 389.7 ms, System: 21.1 ms]
      Range (min … max):   404.8 ms … 415.7 ms    10 runs

    Benchmark 2: krep -c 'the' subtitles2016-sample.en
      Time (mean ± σ):     121.2 ms ±   1.9 ms    [User: 364.6 ms, System: 24.9 ms]
      Range (min … max):   113.2 ms … 123.0 ms    24 runs

    Summary
      krep -c 'the' subtitles2016-sample.en ran
        3.40 ± 0.06 times faster than rg -c 'the' subtitles2016-sample.en

    $ krep -c the subtitles2016-sample.en
    Found 29794426 matches
    $ rg -c the subtitles2016-sample.en
    6123710
    $ grep -c the subtitles2016-sample.en
    6123710

    $ rg -oc the subtitles2016-sample.en
    7739791
    $ rg -o the subtitles2016-sample.en | wc -l
    7739791
    $ grep -o the subtitles2016-sample.en | wc -l
    7739791

Pushing it a bit more, it seems like it just kind of falls over?

    $ time rg -c 'You read Sherlock Holmes to deduce that\?' subtitles2016-sample.en
    10

    real    0.076
    user    0.049
    sys     0.026
    maxmem  923 MB
    faults  0
    $ time krep -c 'You read Sherlock Holmes to deduce that?' subtitles2016-sample.en
    Found 0 matches

    real    0.935
    user    3.597
    sys     0.029
    maxmem  918 MB
    faults  0

In terms of the approach here, ripgrep is already using a pretty sophisticated substring search algorithm: https://github.com/BurntSushi/memchr?tab=readme-ov-file#algo...

And it uses memory maps (sometimes, when it thinks it will be fast, but it will do so in the single file case on Linux).

ripgrep also uses parallelism, but at inter-file level. It sounds like `krep` also uses parallelism, but will use multiple threads when searching a single file. I've considered doing the same in ripgrep, but haven't done enough experiments (or seen enough from someone else) to be convinced that it's the right way to go in general. It might edge out single threaded search in some cases for sure though.

EDIT: Looking at the timings in https://dev.to/daviducolo/introducing-krep-building-a-high-p..., I see, for example, ripgrep taking >40 seconds to search for the literal pattern `error` in a 5GB file. Even if you're reading from disk (which the OP is using an SSD), that does not seem right at all. Even for an exceptionally common word like `the` in this haystack, ripgrep can chew through a 13GB file in 5 seconds on my machine:

    $ time rg -c the full.txt
    83499915

    real    5.404
    user    5.092
    sys     0.302
    maxmem  12511 MB
    faults  0

    $ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
    $ time rg -c the full.txt
    83499915

    real    10.577
    user    5.191
    sys     2.105
    maxmem  12511 MB
    faults  42

Do you have an explanation for the obviously wrong answers in simple examples shown here?

Very cool! The repo is a reference for minimalism. Also, TIL about ifeq in Makefile. So, many thanks!

Minor nit: the "re" part of grep stands for "regular expression". That doesn't seem to be the case with krep so it's a bit misnamed maybe?

Source Code on GitHub: https://github.com/davidesantangelo/krep

It's weird that the_silver_searcher, also known as `ag` [1] is not mentioned in benchmarks, which is also implemented in C.

I wonder why...

[1] https://github.com/ggreer/the_silver_searcher

#include <snarky_comment_about_not_using_rust.h>

Seriously though... thx! this is directly applicable to current interests and the code is not a jumbled mess.