5 ms·

Totally agreed: almost all users (me/GoAWK included) want performance and don't care nearly as much about simplicity under the hood. Simplicity of implementatio

Totally agreed: almost all users (me/GoAWK included) want performance and don't care nearly as much about simplicity under the hood. Simplicity of implementation is of value for educational purposes, but we could easily have a small, simple 3rd party package for that. Go's regexp package is kinda too complex for a simple educational demonstration and too simple to be fast. :-) I actually tried BurntSushi's https://github.com/BurntSushi/rure-go 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 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...

tedunangst 5y ago
Have you considered writing your own string matcher for the simple cases like fixed patterns? I got some pretty solid wins just by guarding some regex executions with simple strings.indexof calls.
- benhoyt 5y ago
  Yeah, that's a good idea, I did consider it, but haven't tried it yet. Do you hook and look at the regex string before it's compiled, or do you hook in at the parsed regex AST level? (eg: regexp/syntax in Go).
  - tedunangst 5y ago
    For something like awk, I think you'd look before compiling, then create your own matcher. With an abstract Matcher interface that regexp implements. 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.c 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.
  - alex_muscar 5y ago
    I think GNU grep does something similar. When it has a fixed patter it uses Boyer-Moore [1]. [1]: https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug...
  - burntsushi 5y ago
    Go's regexp package even exposes a routine for this: https://pkg.go.dev/regexp#Regexp.LiteralPrefix https://pkg.go.dev/regexp#Regexp.LiteralPrefix 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).
    - tedunangst 5y ago
      Oh, regarding rure go, the bugs note about using int is inaccurate. Go spec says max length of any object can be stored in int. You can't build a too big haystack.
      - burntsushi 5y ago
        Ah that's right! Nice catch, thanks.
lamontcg 5y ago
> almost all users (me/GoAWK included) want performance and don't care nearly as much about simplicity under the hood. 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.
- epolanski 5y ago
  Exactly, at some point code is such a mess that further optimization and features are harder to get merged. And the smaller the number of contributors the bigger the problem gets, till the main maintainer calls it quits and there's need for a completely new library.
- kaba0 5y ago
  Is it also true when even the essential complexity of the project is quite demanding? Like runtimes, especially with JIT compilers are not easy to begin with.
  - lamontcg 5y ago
    It is even more important then.

tedunangst 5y ago

Have you considered writing your own string matcher for the simple cases like fixed patterns? I got some pretty solid wins just by guarding some regex executions with simple strings.indexof calls.

benhoyt 5y ago
Yeah, that's a good idea, I did consider it, but haven't tried it yet. Do you hook and look at the regex string before it's compiled, or do you hook in at the parsed regex AST level? (eg: regexp/syntax in Go).
- tedunangst 5y ago
  For something like awk, I think you'd look before compiling, then create your own matcher. With an abstract Matcher interface that regexp implements. 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.c 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.
- alex_muscar 5y ago
  I think GNU grep does something similar. When it has a fixed patter it uses Boyer-Moore [1]. [1]: https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html https://lists.freebsd.org/pipermail/freebsd-current/2010-Aug...
- burntsushi 5y ago
  Go's regexp package even exposes a routine for this: https://pkg.go.dev/regexp#Regexp.LiteralPrefix https://pkg.go.dev/regexp#Regexp.LiteralPrefix 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).
  - tedunangst 5y ago
    Oh, regarding rure go, the bugs note about using int is inaccurate. Go spec says max length of any object can be stored in int. You can't build a too big haystack.
    - burntsushi 5y ago
      Ah that's right! Nice catch, thanks.

lamontcg 5y ago

> almost all users (me/GoAWK included) want performance and don't care nearly as much about simplicity under the hood. 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.

epolanski 5y ago
Exactly, at some point code is such a mess that further optimization and features are harder to get merged. And the smaller the number of contributors the bigger the problem gets, till the main maintainer calls it quits and there's need for a completely new library.
kaba0 5y ago
Is it also true when even the essential complexity of the project is quite demanding? Like runtimes, especially with JIT compilers are not easy to begin with.
- lamontcg 5y ago
  It is even more important then.