Hah, this reminds me how over several years ago, I rewrote one of my homework from Go to Python, since Go version was so terribly slow because of regex. I really hoped it was better in 2021.
Go's regexp package does have a couple of advantages over Python, Perl, and so on: 1) it's guaranteed linear time in the length of the input, regardless of the regex, see https://swtch.com/~rsc/regexp/regexp1.html, and 2) it's a relatively simple implementation.
https://fosdem.org/2022/schedule/event/go_finite_automata/
This repo collects all the changes so you can try them out: https://github.com/grafana/regexp/tree/speedup#readme
I actually tried BurntSushi's https://github.com/BurntSushi/rure-go (bindings to Rust's regex engine) with GoAWK and it made regex handling 4-5x as fast for many regexes, despite the CGo overhead. However, rure-go (and CGo in general) is a bit painful to build, so I'm not going to use that. Maybe I'll create a branch for speed freaks who want it.
I've also thought of using https://gitlab.com/cznic/ccgo to convert Mawk's fast regex engine to Go source and see how that performs. Maybe on the next rainy day...
I got some pretty solid wins just by guarding some regex executions with simple strings.indexof calls.
It's C, but openbsd grep does something like this because libc regex is super slow. Look for fastcomp on https://github.com/openbsd/src/blob/master/usr.bin/grep/util... It's not super sophisticated, but enough to beat the full regex engine.
In the go code where I did this, it was a little different, with a static pattern. Something like "(\w+) apple" to find all apple adjectives or whatever, but the regexp wasted so much time matching words before not apples. A quick scan for "apple" to eliminate impossible matches made it faster. This depends more on knowing regex and corpus, so probably less relevant for awk.
It's been a while since I've looked at the source code, but it is almost certainly already doing basic prefix literal optimizations.
The more advanced literal optimizations come into play when every match must start with one of a few possible characters or strings. Then you get into things like Aho-Corasick or fancy SIMD algorithms (Teddy).
[1]: https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug...
that works up until you're at scale and the complexity of the implementation causes hard to understand edge conditions and just bugs from the complexity being beyond what the developers are able to handle.
It's only in a few areas, like programming languages and operating systems, that we're obsessed with simplicity, and it makes little sense to me.
I don't see simplicity as a "virtue", as such: it's all about the ability to reason about a system. The more complex it is, the harder this becomes. This makes it harder for implementers to work on it, and harder for users to figure out what is going wrong.
On the other hand, complexity often offers useful enhancements such as features or performance. There is some amount of tension here, which is hardly unique to software: you see this in, say, tax systems, regulation/law, design of cars and all sort of things, etc.
It's a tradeoff, in the end. I mean sure, users don't really need to know how things work under the hood, but the people building and maintaining the language do; Go's philosophies on maintainability extend to the language's internals as well.
This is one reason why generics took over ten years to land; they needed to find the middle ground between functionality and sanity within the compiler. Java's generics implementation takes up a huge chunk of the spec and tooling. I don't even want to know about Scala's. It added so much more complexity to the language that I'm not surprised Java stagnated for as long as it did.
Does it? It is a pretty straightforward generic implementation, imo.
Go is not about providing the fastest implementations out of the box, it's about having a broad toolset in the standard library to solve the problems Go was built for.
Faster (and often more complex) implementations are a maintenance burden for Go contributors. It's far better for a high performance regex library to be a third party package for those that need it.
For those where regex is a limiting factor in performance they'll soon find out why. But for most people fast regex is nothing compared to the overhead of a simple HTTP request.
What’s the multiplicative factor? Does it dominate for “typical” regexes?
I used to think that backtracking was superior to the Thompson NFA in practice on typical regexes, but modern implementations of the Thompson NFA have shown that I was wrong in that and the Thompson NFA can match backtracking's performance. Still, the situation isn't nearly as simple as Russ's article makes it out to be by only focusing on /a?a?a?aaa/, a regex which nobody would write. (This is not to deny that people do write pathological regexes from time to time. But what's the size of the userbase that writes pathological regexes compared to the size of the userbase that uses backreferences?)
Now a hybrid NFA/DFA (or a "lazy DFA") that does subset construction at search time using a Thompson NFA can definitely beat out a backtracker. A lazy DFA will generally match the speed of a fully compiled DFA, and is about an order of magnitude faster than a Thompson NFA simulation:
[andrew@frink regex-automata]$ regex-cli find nfa thompson pikevm "@$medium" '(?m)^\w{30}$'
build pike vm time: 6.584596ms
create cache time: 278.231µs
search time: 7.798138892s
counts: [3]
[andrew@frink regex-automata]$ regex-cli find hybrid dfa "@$medium" '(?m)^\w{30}$'
parse time: 24.256µs
translate time: 20.202µs
compile nfa time: 5.966991ms
nfa memory: 486196
build hybrid dfa time: 3.137µs
hybrid dfa memory: 486196
create cache time: 21.793µs
search time: 406.746917ms
cache clear count: 0
counts: [3]
[andrew@frink regex-automata]$ regex-cli find dfa dense "@$medium" '(?m)^\w{30}$'
parse time: 22.824µs
translate time: 15.513µs
compile nfa time: 6.000195ms
nfa memory: 486196
compile dense dfa time: 106.35009ms
dense dfa memory: 4501024
dense alphabet length: 117
dense stride: 128
search time: 448.568888ms
counts: [3]
$ ls -lh $medium
-rw-rw-r-- 1 andrew users 280M Jul 14 2021 /home/andrew/data/benchsuite/subtitles/2018/OpenSubtitles2018.raw.sample.medium.en
If such a thing exists, I haven't seen it, but that's not to say it doesn't exist. In general, though, programming languages and libraries have poor-to-nonexistent generalized support for bounding the amount of resources to spend on a given internal computation. Because that's obviously a rather niche use that's hard to justify a lot of effort, especially since "bound the amount of resources for a given program", a well-implemented bit of functionality, tends to hit a lot of the use cases.
Rust -> Ruby -> Java -> Golang
https://github.com/mariomka/regex-benchmark
Though it appears the numbers are two years old or so, and only for 3 specific regexes.
The top times for the mentioned languages are:
Rust: 0.78s
Ruby: 12.33s
Java: 5.34s
Go: 3.80s
Python: 1.34s
Python #2 1.34s PCRE2
Go #5 3.80s PCRE
Java #3 5.34s
Java #6 5.39s
Java #1 8.49s
Python #1 9.25s "standard library"
Go #4 15.60s PCRE
Go #3 26.86s "standard library"
Go #1 27.01s "standard library"https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
regex=PCRE2.pcre2_compile_8(pattern, c_size_t(len(pattern)), c_uint32(0),
byref(c_int()), byref(c_size_t()), None)
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
C gcc #6 0.56s
Java #3 0.79sLook at the runtimes being mentioned here. We're talking on the order of seconds. The benchmark itself calls for 15 pretty simple regexes to be compiled. Regex compilation of 1ms or longer would be considered slow I think. So that's 15ms. That's nearly nothing compared to the full runtime of the benchmark. Even if you assumed each regex took 10ms on average to compile, you're still only looking at 150ms total.
I say this as the author of Rust's regex engine and as someone who has spent a non-trivial time looking at and thinking about this particular benchmark.
The NFA simulator is heavily optimized for readability, which means lots of recursion, and fewer special cases outside of small regexps. The compiler also doesn't perform certain optimizations like vectorization and emitting jump tables, which might be useful here.
There isn't a metaprogramming facility to generate equivalent Go code like in re2go: https://re2c.org/manual/manual_go.html. The best we can do is pre-declare the regexps globally as to initialize them once, but we still have to run the interpreter.
Moreover, thus far, a DFA matcher is out of a picture, as discussed here: https://github.com/golang/go/issues/11646.
Mathematically 1.2 is greater than 1.18. Yet in versions it is lesser.
I find this annoying and counter intuitive.
That way your brain can't think of them as numbers any more =)
Versions aren't numbers.
For Virgil, because I am a fan of the roman poet, I am using roman numerals for the major versions and append a monotonically-increasing-regardless-of-major-version "00XXX" build number to that. This ensures they always sort lexicographically.
...until I get to version IX, i.e. 9, which would sort incorrectly. So I'll just skip 9, 19, 29...90...heh. :)
Using this precise rule, the starting point that gets you furthest is 250, which grants you 153 elements before stopping at 1038 (MXXXVIII).
It’s possible to devise a longer sequence by skipping some numbers (e.g. after 1000 you’d jump to 1100), but I’m too lazy to calculate how you’d do all that.
All this also assumes subtraction rules, which were a late addition to Roman numerals; without subtraction rules, four is written IIII instead of IV, and nine VIIII instead of IX, and so all of 1–49 would be lexicographically sorted.
from docutils.utils.roman import toRoman
def sequence(start):
last = ''
out = []
for i in range(start, 5000):
this = toRoman(i)
if this > last:
last = this
out.append(i)
return out
# Brute force way because I’m lazy; takes around ten seconds on my machine.
start, s = max(((start, sequence(start)) for start in range(1, 5000)), key=lambda x: len(x[1]))
print(f'{start} gives you {len(s)} items, {s}')This is not super surprising, and like you said, in a typical AWK script you would only need to compile once.
In short:
$ go test -bench .
...
BenchmarkRegexpCompile-8 513030 2307 ns/op
BenchmarkRegexpEval1-8 2795020 425.5 ns/op
BenchmarkRegexpEval2-8 3218155 370.2 ns/op
...
Edit: formatting