Update benchmark with ugrep 5.0

[genivia-inc]

Nice project!

I came across it because a ugrep user found a Reddit post about the project. Thanks for including ugrep in the benchmarks. It is always interesting how ugrep can be used in comparison. If there are some bottlenecks to speed, then I put it on the TODO list to resolve (see my note below).

The ugrep version used in these benchmark isn't up to date. More optimal search methods and optimizations were implemented in ugrep 3.12 and continued with 4.0. You may want to run the benchmarks with the latest ugrep e.g. v4.0.5. The old version 3.11 had an issue picking the wrong search algorithm in some cases, leading to a fall back to the default method that is slower.

Note that there are also plans for enhancing ugrep's search speed further with some tricks other grep use, as well as adding a new method to deal with pattern cases that ugrep doesn't yet handle well (long initial wildcard characters like .*foo that's not optimized at all but is easy to do by looking for foo), but these plans were (and some still are) delayed to give priority to new and improved features while ensuring reliability. I won't give a list of things that were added over time (since this is not about ugrep, but about hypergrep). Simply getting high performance with lots of new features is a tricky combination to do at the same time.

People always ask about new features or to improve them, they care a bit less about speed. Most often if they really want speed, then the its usually to search "cold" file systems. Then qgrep might be a good choice. Or perhaps ugrep-indexer.

I am curious, is hypergrep based on hyperscan? EDIT: sorry, dumb question, I see the answer in the README up front now. I wanted to ask, because hypergrep has a "simple grep" example that works OK, but not stellar.

[p-ranav]

Hello!

Yes, I'd be happy to update my benchmarks using the latest ugrep v4.0.5. I'm excited for your plans to further speed up ugrep! I agree, it's tricky balancing features with performance. New features often add performance penalties.

And yes, hypergrep uses Intel HyperScan as its regex engine. I suspect their simple example doesn't particularly optimize for large file search or indeed git repositories.

[genivia-inc]

Yes. Simple grep is just a demo application. Large files are searched very quickly. But it lacks a lot of features to make it worthwhile to compare. There is no line counting overhead whatsoever, so it is definitely fast.

I don't know if you're interested in any of the following details, I just wanted to convey ongoing efforts and short-term plans.

Motivation: I am very interested and curious in figuring out new ways to speed up pattern matching algorithmically and try it out in practice. Ugrep was born because of this about four years ago (unoptimized) to try something new I came up with, which I call PM for "predict match". I got ugrep going based on a demo grep I wrote for RE/flex. I want to try hypergrep instead of simple grep to see where we stand now and what needs to be tweaked in ugrep, besides comparing it to some other optimizations that are/were planned, but haven't been released yet.

Background: I've extensively used simple grep to evaluate and compare the speed of matching/search methods. Some early R&D work I did on a new regex search method focussed primarily on classes of patterns that involve short and long strings in growing numbers (e.g. set of words of various sizes). The bitap method and derivatives are really poor at this when its window is short since it is limited to the shortest word in the set. I spent time to find better ways to see if it is possible to compete with hyperscan and other grep tools, and eventually found that PM-4 is nice and superior when matching words up to sets of a 2k or so and does not need SIMD to run fast. It's using a Bloom filter of sorts for short 1 char to 4 char word patterns simultaneously with bit banging. This is combined with bitap, depending on a formula that looks at the entropy of a pattern to match to decide what method should be used. When this combination is used, it is faster than hyperscan (i.e. simple grep) by predicting at which positions a match may occur.

What's next: It might be that other algorithmic combinations implemented in SIMD (AVX and AArch64) are better, or not. I've tried bitap-based methods in pure AVX2 with the 256 byte table in vectors to have zero memory loads except for input, but it ran about the same time as the scalar version. The latest ugrep v4 uses a very different way to match patterns using AVX and AArch64 instructions that are picked by the decision logic to execute when (roughly) deemed best for matching.

Anyway, I will try hyperscan in about two/three weeks (I am on a break) and see what happens.

[genivia-inc]

I just wanted to drop a short note that after a bit of tweaking and adding two common grep-like optimizations, the upcoming ugrep v4.1 release is pretty fast on x64 and arm64 and almost always faster than other fast grep tools, see a preview report posted here: Genivia/ugrep#289

The difficulty is sometimes picking the number of threads and the search method to use that's best.

Finally, it might be again important to point out for your benchmarks that the \w+foo pattern is slow in ugrep as I've already indicated, but those optimizations have to wait until I'm back in office.

PS. I hope you have a great week and happy coding!

[genivia-inc]

OK. As promised, we dropped a new ugrep v4.3 with its performance report showing that ugrep is nearly always faster than other grep on x64 and arm64 systems. I have not been able to compare against hypergrep because it doesn't compile #45.

Another update v4.3.2 will be available soon to speed up recursive search further with improved thread scheduling.

Please note that there is one case of slow regex patterns \w+foo that suffer backtracking will be attacked next for a future release update (it works alright with option -P). To use them specifically in a benchmark makes very little sense at the moment, although \w*foo can be used instead which doesn't have this pathological backtracking issue but also isn't as fast as can be. Regex search and matching is done with my regex DFA project RE/flex, which is pretty fast for regex matching, but search is a different beast that "eats" heuristics, approximate matching with hashing/filters//bitap, SIMD, etc.

[genivia-inc]

FYI. ugrep 5.0 was released some time ago, an important milestone.

This release fixes the performance problems with "leading wildcard" patterns such as \w+foo and many other patterns like this that caused excessive backtracking in previous ugrep releases. We did more benchmarking to test and compare performance. See updated performance report