4 ms·

You can read my blog post about the project at https://dev.to/daviducolo/introducing-krep-building-a-high-performance-string-search-utility-2pdo https://dev.to/

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

geocar 2y ago
Hi David. $ (for x in `seq 1 100000`; do echo 'I am a Test Vector HeLlO World '"$x"; done) > /dev/shm/krep_tmp Best of three runs shown: $ time ./krep -i hello /dev/shm/krep_tmp Found 43721 matches Search completed in 0.0017 seconds (2017.44 MB/s) Search details: - File size: 3.52 MB - Pattern length: 5 characters - Using AVX2 acceleration - Case-insensitive search real 0m0,005s user 0m0,001s sys 0m0,004s $ time ./krep HeLlO /dev/shm/krep_tmp Found 82355 matches Search completed in 0.0014 seconds (1259.72 MB/s) Search details: - File size: 1.71 MB - Pattern length: 5 characters - Using AVX2 acceleration - Case-sensitive search real 0m0,004s user 0m0,003s sys 0m0,004s $ time ./krep -i "HeLlO World" /dev/shm/krep_tmp Found 99958 matches Search completed in 0.0021 seconds (1700.54 MB/s) Search details: - File size: 3.52 MB - Pattern length: 11 characters - Using AVX2 acceleration - Case-insensitive search real 0m0,005s user 0m0,002s sys 0m0,004s $ time ./krep "I am a Test Vector HeLlO World" /dev/shm/krep_tmp Found 3964 matches Search completed in 0.0149 seconds (235.83 MB/s) Search details: - File size: 3.52 MB - Pattern length: 30 characters - Using AVX2 acceleration - Case-sensitive search real 0m0,016s user 0m0,015s sys 0m0,001s $ time ./krep -i "I am a Test Vector hello World" /dev/shm/krep_tmp Found 3964 matches Search completed in 0.0178 seconds (197.70 MB/s) Search details: - File size: 3.52 MB - Pattern length: 30 characters - Using AVX2 acceleration - Case-insensitive search real 0m0,021s user 0m0,017s sys 0m0,004s Benchmark with fgrep (the first run was good enough): $ time fgrep -ci hello /dev/shm/krep_tmp 100000 real 0m0,003s user 0m0,003s sys 0m0,000s $ time fgrep -ci "I am a Test Vector hello World" /dev/shm/krep_tmp 100000 real 0m0,010s user 0m0,009s sys 0m0,000s $ time fgrep -c "I am a Test Vector HeLlO World" /dev/shm/krep_tmp 100000 real 0m0,005s user 0m0,004s sys 0m0,001s This is a model name: Intel(R) Core(TM) i9-10900K CPU @ 3.70GHz. There's 40gb of ram free and 10 cores doing nothing. shell is cpuset. On commit 95ed1853b561396c8a8bcbbdd115ed6273848e3f (HEAD -> main, origin/main, origin/HEAD). gcc is 13.3.0-6ubuntu2~24.04 tl;dr: krep produces obviously wrong results slower than fgrep.
- burntsushi 2y ago
  Consider using a bigger haystack. Your timings are so short that you're mostly just measuring the overhead of running a process. This is relevant to krep because it spawns threads to search files (I guess for files over 1MB?). This does not mean your benchmark is worthless. It just means you can't straight-forwardly generalize from it.
  - globnomulous 2y ago
    That's a good point, though the readme does flatly state that krep "is designed with performance as a primary goal," so the lede's generalization that it is "blazingly fast" isn't correct, despite the later, more deeply buried caveat that "Performance may vary based on hardware, file characteristics, and search pattern" (which describes all software). And the comment you answered doesn't say just that krep is "slower" than fgrep; it says krep "produces obviously wrong results" slower. Edit: and the fact that krep lacks regular-expression support means it's not a replacement for grep or meaningfully comparable with it.
    - burntsushi 2y ago
      I try my best to interpret pithy phrases describing a project as first order approximations, rather than literal statements of truth that perfectly generalize. Pithiness is important for communicating ideas quickly, but precision and pithiness are often in tension with one another. So I adjust my expectations accordingly. Yes, I agree that the wrong results are bad. But that doesn't invalidate my point. I even went out of my way to clarify that the benchmark wasn't worthless. Benchmarking the small input case is absolutely worth it. You just can't tell much about its scaling properties when your measurement is basically "how fast does the process start and stop." Which, again, to be clear, IT MATTERS. It just probably doesn't matter as much as readers might think it matters when they see it. So treat my comment as adding helpful context for readers that aren't experts in benchmarking grep tools from someone experienced in... benchmarking grep tools. :-) (And regexes in general. See: https://github.com/BurntSushi/rebar https://github.com/BurntSushi/rebar)
  - fanf2 2y ago
gwbas1c 2y ago
I'm curious why krep runs faster with large files in a multithreaded manner? Naively, isn't IO the bottleneck? IE, I'd think that loading a file would be slow enough that krep would be IO-bound? Do you have a typical ratio of IO time to search time on a modern disk and CPU? What about a producer-consumer model where one thread reads files and creates an in-memory queue of file contents; and a different thread handles the actual searching without pauses for IO? Edit: If you're truly CPU-bound, another variation of producer-consumer is to have a single thread read files into queues, and then multiple threads searching through files. Each thread would search through a single file at a time. This eliminates the shared memory issue that you allude to with overlap.
- lainzhow 2y ago
  I didn't read the source, but from the description it says it uses memory mapping. So my guess here is that IO isn't so much of an issue since prefetching can hide away the latency if you are able to memory map a large enough segment of the file. Iff the statement about prefetching is true though, I wonder how the prefetching wouldn't be bamboozled by the multiple threads accessing the file.
  - gwbas1c 2y ago
    Forgot about memory mapping. In that case it probably makes more sense to have a shared queue of files, and each thread handles a single file at a time. It'll avoid the overlap issue.
MattPalmer1086 2y ago
Interesting. You may be interested in a more modern search algorithm to replace Boyer Moore. I recently presented HashChain, a very fast sublinear search algorithm at the Symposium of Experimental Algorithms. https://drops.dagstuhl.de/storage/00lipics/lipics-vol301-sea2024/LIPIcs.SEA.2024.24/LIPIcs.SEA.2024.24.pdf https://drops.dagstuhl.de/storage/00lipics/lipics-vol301-sea... It's the fastest sublinear search algorithm around in almost all cases. I also have a guaranteed worst-case linear version (which is still sublinear and much faster than Boyer Moore in the average case). Sample code is available here: https://github.com/nishihatapalmer/HashChain https://github.com/nishihatapalmer/HashChain If you're interested, let me know.
- rurban 2y ago
  A benchmark of all good string-search algos is here: https://rurban.github.io/smart/results/best20/ https://rurban.github.io/smart/results/best20/ The ones parent picked are not amongst the best at all. I added a ticket to add your HashChain algos to be tested also. Preliminary testing shows indeed excellent numbers for hc2-hc4. Comes close to musl
  - MattPalmer1086 2y ago
    Amazing, thanks. The sample code is already written to integrate with smart (I have also contributed to the smart tool!). You may want to add the linear version of HashChain too (in the same GitHub repo).
  - MattPalmer1086 2y ago
    Looks like musl is using pointer arithmetic? Can speed up most of the algorithms in smart by using that. It's faster than using array indexing generally. I didn't do that in the sample code for HashChain simply because it would be an unfair comparison with the others.
  - MattPalmer1086 2y ago
    The musl timings are actually incorrect, because it resets the timer on each iteration of the main loop used to count matches. So you only record the time to make the last match, not the total time. I've raised an issue on the GitHub for smart.
rafram 2y ago
Was this entire blog post written by AI too? Honestly, this is an impressive feat if so, but the fake benchmarks are really not a good look.

geocar 2y ago

Hi David. $ (for x in `seq 1 100000`; do echo 'I am a Test Vector HeLlO World '"$x"; done) > /dev/shm/krep_tmp Best of three runs shown: $ time ./krep -i hello /dev/shm/krep_tmp Found 43721 matches Search completed in 0.0017 seconds (2017.44 MB/s) Search details: - File size: 3.52 MB - Pattern length: 5 characters - Using AVX2 acceleration - Case-insensitive search real 0m0,005s user 0m0,001s sys 0m0,004s $ time ./krep HeLlO /dev/shm/krep_tmp Found 82355 matches Search completed in 0.0014 seconds (1259.72 MB/s) Search details: - File size: 1.71 MB - Pattern length: 5 characters - Using AVX2 acceleration - Case-sensitive search real 0m0,004s user 0m0,003s sys 0m0,004s $ time ./krep -i "HeLlO World" /dev/shm/krep_tmp Found 99958 matches Search completed in 0.0021 seconds (1700.54 MB/s) Search details: - File size: 3.52 MB - Pattern length: 11 characters - Using AVX2 acceleration - Case-insensitive search real 0m0,005s user 0m0,002s sys 0m0,004s $ time ./krep "I am a Test Vector HeLlO World" /dev/shm/krep_tmp Found 3964 matches Search completed in 0.0149 seconds (235.83 MB/s) Search details: - File size: 3.52 MB - Pattern length: 30 characters - Using AVX2 acceleration - Case-sensitive search real 0m0,016s user 0m0,015s sys 0m0,001s $ time ./krep -i "I am a Test Vector hello World" /dev/shm/krep_tmp Found 3964 matches Search completed in 0.0178 seconds (197.70 MB/s) Search details: - File size: 3.52 MB - Pattern length: 30 characters - Using AVX2 acceleration - Case-insensitive search real 0m0,021s user 0m0,017s sys 0m0,004s Benchmark with fgrep (the first run was good enough): $ time fgrep -ci hello /dev/shm/krep_tmp 100000 real 0m0,003s user 0m0,003s sys 0m0,000s $ time fgrep -ci "I am a Test Vector hello World" /dev/shm/krep_tmp 100000 real 0m0,010s user 0m0,009s sys 0m0,000s $ time fgrep -c "I am a Test Vector HeLlO World" /dev/shm/krep_tmp 100000 real 0m0,005s user 0m0,004s sys 0m0,001s This is a model name: Intel(R) Core(TM) i9-10900K CPU @ 3.70GHz. There's 40gb of ram free and 10 cores doing nothing. shell is cpuset. On commit 95ed1853b561396c8a8bcbbdd115ed6273848e3f (HEAD -> main, origin/main, origin/HEAD). gcc is 13.3.0-6ubuntu2~24.04 tl;dr: krep produces obviously wrong results slower than fgrep.

burntsushi 2y ago
Consider using a bigger haystack. Your timings are so short that you're mostly just measuring the overhead of running a process. This is relevant to krep because it spawns threads to search files (I guess for files over 1MB?). This does not mean your benchmark is worthless. It just means you can't straight-forwardly generalize from it.
- globnomulous 2y ago
  That's a good point, though the readme does flatly state that krep "is designed with performance as a primary goal," so the lede's generalization that it is "blazingly fast" isn't correct, despite the later, more deeply buried caveat that "Performance may vary based on hardware, file characteristics, and search pattern" (which describes all software). And the comment you answered doesn't say just that krep is "slower" than fgrep; it says krep "produces obviously wrong results" slower. Edit: and the fact that krep lacks regular-expression support means it's not a replacement for grep or meaningfully comparable with it.
  - burntsushi 2y ago
    I try my best to interpret pithy phrases describing a project as first order approximations, rather than literal statements of truth that perfectly generalize. Pithiness is important for communicating ideas quickly, but precision and pithiness are often in tension with one another. So I adjust my expectations accordingly. Yes, I agree that the wrong results are bad. But that doesn't invalidate my point. I even went out of my way to clarify that the benchmark wasn't worthless. Benchmarking the small input case is absolutely worth it. You just can't tell much about its scaling properties when your measurement is basically "how fast does the process start and stop." Which, again, to be clear, IT MATTERS. It just probably doesn't matter as much as readers might think it matters when they see it. So treat my comment as adding helpful context for readers that aren't experts in benchmarking grep tools from someone experienced in... benchmarking grep tools. :-) (And regexes in general. See: https://github.com/BurntSushi/rebar https://github.com/BurntSushi/rebar)
- fanf2 2y ago

gwbas1c 2y ago

I'm curious why krep runs faster with large files in a multithreaded manner? Naively, isn't IO the bottleneck? IE, I'd think that loading a file would be slow enough that krep would be IO-bound? Do you have a typical ratio of IO time to search time on a modern disk and CPU? What about a producer-consumer model where one thread reads files and creates an in-memory queue of file contents; and a different thread handles the actual searching without pauses for IO? Edit: If you're truly CPU-bound, another variation of producer-consumer is to have a single thread read files into queues, and then multiple threads searching through files. Each thread would search through a single file at a time. This eliminates the shared memory issue that you allude to with overlap.

lainzhow 2y ago
I didn't read the source, but from the description it says it uses memory mapping. So my guess here is that IO isn't so much of an issue since prefetching can hide away the latency if you are able to memory map a large enough segment of the file. Iff the statement about prefetching is true though, I wonder how the prefetching wouldn't be bamboozled by the multiple threads accessing the file.
- gwbas1c 2y ago
  Forgot about memory mapping. In that case it probably makes more sense to have a shared queue of files, and each thread handles a single file at a time. It'll avoid the overlap issue.

MattPalmer1086 2y ago

Interesting. You may be interested in a more modern search algorithm to replace Boyer Moore. I recently presented HashChain, a very fast sublinear search algorithm at the Symposium of Experimental Algorithms. https://drops.dagstuhl.de/storage/00lipics/lipics-vol301-sea2024/LIPIcs.SEA.2024.24/LIPIcs.SEA.2024.24.pdf https://drops.dagstuhl.de/storage/00lipics/lipics-vol301-sea... It's the fastest sublinear search algorithm around in almost all cases. I also have a guaranteed worst-case linear version (which is still sublinear and much faster than Boyer Moore in the average case). Sample code is available here: https://github.com/nishihatapalmer/HashChain https://github.com/nishihatapalmer/HashChain If you're interested, let me know.

rurban 2y ago
A benchmark of all good string-search algos is here: https://rurban.github.io/smart/results/best20/ https://rurban.github.io/smart/results/best20/ The ones parent picked are not amongst the best at all. I added a ticket to add your HashChain algos to be tested also. Preliminary testing shows indeed excellent numbers for hc2-hc4. Comes close to musl
- MattPalmer1086 2y ago
  Amazing, thanks. The sample code is already written to integrate with smart (I have also contributed to the smart tool!). You may want to add the linear version of HashChain too (in the same GitHub repo).
- MattPalmer1086 2y ago
  Looks like musl is using pointer arithmetic? Can speed up most of the algorithms in smart by using that. It's faster than using array indexing generally. I didn't do that in the sample code for HashChain simply because it would be an unfair comparison with the others.
- MattPalmer1086 2y ago
  The musl timings are actually incorrect, because it resets the timer on each iteration of the main loop used to count matches. So you only record the time to make the last match, not the total time. I've raised an issue on the GitHub for smart.

rafram 2y ago

Was this entire blog post written by AI too? Honestly, this is an impressive feat if so, but the fake benchmarks are really not a good look.