regexp: investigate further performance improvements #26623
Comments
ianlancetaylor
changed the title
|
Calling out to C carries a cost. We don't want to do it for a basic package like regexp. We're much more interested in speeding up Go's regexp package. If people want to work on that, that would be great. Note that one reason that Go's regexp package may be slower is that it works on UTF-8 characters, not ASCII bytes. I don't know what Python does. Also note that Go is committed to using regexps that scale well (see https://swtch.com/~rsc/regexp/). I don't know what Python does. I'm not sure it's useful to leave a general issue like this open. It doesn't suggest any specific action to take. Are you interested in examining the regexp code to understand why Python does better on this benchmark? |
andybons
added
the
WaitingForInfo
|
The benchmark code includes compiling the regex. In a common use of regexp, one would compile the regex once and run it many times, so the benchmark numbers aren't very helpful. Also note that the benchmark numbers are almost a year old at this point, and Go does two releases per year. |
|
I might be mistaken, but doesn't PCRE have a JIT compiler? That might explain it, at-least for a couple of the top ones (I know PHP uses PCRE). |
mariomka/regex-benchmark#2 I found an example on the same repository which apparently excludes compilation, but it doesn't look too scientific (only ten executions). It shows more or less the same results (which is odd as I'd thought that compilation would have more of an impact on the times). |
|
The compilation does have a large impact on the speed: I presume it doesn't show up in the original numbers because the input data is very large, though. I agree with @ianlancetaylor that a generic issue like this isn't very helpful. If specific parts of the regexp package could be improved, or certain edge cases are orders of magnitude slower than they should be, we should use separate issues to tackle those. For example, we already have some like #24411 and #21463. |
|
While it's true that this issue is less than actionable as-is, it is also true that the results of the benchmark reported here are not too dissimilar from the ones on https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/regexredux.html (where they use 1.10). I agree it's unfortunate that all those benchmarks include pattern compilation (although it seems it's not so significant). |
|
My comments on #26943:
|
|
Change https://golang.org/cl/130417 mentions this issue: |
MatchRunePos is a significant element of regexp performance, so some attention to optimization is appropriate. Before this CL, a non-matching rune would do both a linear search in the first four entries, and a binary search over all the entries. Change the code to optimize for the common case of two runes, to only do a linear search when there are up to four entries, and to only do a binary search when there are more than four entries. Updates #26623 name old time/op new time/op delta Find-12 260ns ± 1% 275ns ± 7% +5.84% (p=0.000 n=8+10) FindAllNoMatches-12 144ns ± 9% 143ns ±12% ~ (p=0.187 n=10+10) FindString-12 256ns ± 4% 254ns ± 1% ~ (p=0.357 n=9+8) FindSubmatch-12 587ns ±12% 593ns ±11% ~ (p=0.516 n=10+10) FindStringSubmatch-12 534ns ±12% 525ns ±14% ~ (p=0.565 n=10+10) Literal-12 104ns ±14% 106ns ±11% ~ (p=0.145 n=10+10) NotLiteral-12 1.51µs ± 8% 1.47µs ± 2% ~ (p=0.508 n=10+9) MatchClass-12 2.47µs ± 1% 2.26µs ± 6% -8.55% (p=0.000 n=8+10) MatchClass_InRange-12 2.18µs ± 5% 2.25µs ±11% +2.85% (p=0.009 n=9+10) ReplaceAll-12 2.35µs ± 6% 2.08µs ±23% -11.59% (p=0.010 n=9+10) AnchoredLiteralShortNonMatch-12 93.2ns ± 9% 93.2ns ±11% ~ (p=0.716 n=10+10) AnchoredLiteralLongNonMatch-12 118ns ±10% 117ns ± 9% ~ (p=0.802 n=10+10) AnchoredShortMatch-12 142ns ± 1% 141ns ± 1% -0.53% (p=0.007 n=8+8) AnchoredLongMatch-12 303ns ± 9% 304ns ± 6% ~ (p=0.724 n=10+10) OnePassShortA-12 620ns ± 1% 618ns ± 9% ~ (p=0.162 n=8+10) NotOnePassShortA-12 599ns ± 8% 568ns ± 1% -5.21% (p=0.000 n=10+8) OnePassShortB-12 525ns ± 7% 489ns ± 1% -6.93% (p=0.000 n=10+8) NotOnePassShortB-12 449ns ± 9% 431ns ±11% -4.05% (p=0.033 n=10+10) OnePassLongPrefix-12 119ns ± 6% 114ns ± 0% -3.88% (p=0.006 n=10+9) OnePassLongNotPrefix-12 420ns ± 9% 410ns ± 7% ~ (p=0.645 n=10+9) MatchParallelShared-12 376ns ± 0% 375ns ± 0% -0.45% (p=0.003 n=8+10) MatchParallelCopied-12 39.4ns ± 1% 39.1ns ± 0% -0.55% (p=0.004 n=10+9) QuoteMetaAll-12 139ns ± 7% 142ns ± 7% ~ (p=0.445 n=10+10) QuoteMetaNone-12 56.7ns ± 0% 61.3ns ± 7% +8.03% (p=0.001 n=8+10) Match/Easy0/32-12 83.4ns ± 7% 83.1ns ± 8% ~ (p=0.541 n=10+10) Match/Easy0/1K-12 417ns ± 8% 394ns ± 6% ~ (p=0.059 n=10+9) Match/Easy0/32K-12 7.05µs ± 8% 7.30µs ± 9% ~ (p=0.190 n=10+10) Match/Easy0/1M-12 291µs ±17% 284µs ±10% ~ (p=0.481 n=10+10) Match/Easy0/32M-12 9.89ms ± 4% 10.27ms ± 8% ~ (p=0.315 n=10+10) Match/Easy0i/32-12 1.13µs ± 1% 1.14µs ± 1% +1.51% (p=0.000 n=8+8) Match/Easy0i/1K-12 35.7µs ±11% 36.8µs ±10% ~ (p=0.143 n=10+10) Match/Easy0i/32K-12 1.70ms ± 7% 1.72ms ± 7% ~ (p=0.776 n=9+6) name old alloc/op new alloc/op delta Find-12 0.00B 0.00B ~ (all equal) FindAllNoMatches-12 0.00B 0.00B ~ (all equal) FindString-12 0.00B 0.00B ~ (all equal) FindSubmatch-12 48.0B ± 0% 48.0B ± 0% ~ (all equal) FindStringSubmatch-12 32.0B ± 0% 32.0B ± 0% ~ (all equal) name old allocs/op new allocs/op delta Find-12 0.00 0.00 ~ (all equal) FindAllNoMatches-12 0.00 0.00 ~ (all equal) FindString-12 0.00 0.00 ~ (all equal) FindSubmatch-12 1.00 ± 0% 1.00 ± 0% ~ (all equal) FindStringSubmatch-12 1.00 ± 0% 1.00 ± 0% ~ (all equal) name old speed new speed delta QuoteMetaAll-12 101MB/s ± 8% 99MB/s ± 7% ~ (p=0.529 n=10+10) QuoteMetaNone-12 458MB/s ± 0% 425MB/s ± 8% -7.22% (p=0.003 n=8+10) Match/Easy0/32-12 385MB/s ± 7% 386MB/s ± 7% ~ (p=0.579 n=10+10) Match/Easy0/1K-12 2.46GB/s ± 8% 2.60GB/s ± 6% ~ (p=0.065 n=10+9) Match/Easy0/32K-12 4.66GB/s ± 7% 4.50GB/s ±10% ~ (p=0.190 n=10+10) Match/Easy0/1M-12 3.63GB/s ±15% 3.70GB/s ± 9% ~ (p=0.481 n=10+10) Match/Easy0/32M-12 3.40GB/s ± 4% 3.28GB/s ± 8% ~ (p=0.315 n=10+10) Match/Easy0i/32-12 28.4MB/s ± 1% 28.0MB/s ± 1% -1.50% (p=0.000 n=8+8) Match/Easy0i/1K-12 28.8MB/s ±10% 27.9MB/s ±11% ~ (p=0.143 n=10+10) Match/Easy0i/32K-12 19.0MB/s ±14% 19.1MB/s ± 8% ~ (p=1.000 n=10+6) Change-Id: I238a451b36ad84b0f5534ff0af5c077a0d52d73a Reviewed-on: https://go-review.googlesource.com/130417 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
Timed out in state WaitingForInfo. Closing. (I am just a bot, though. Please speak up if this is a mistake or you have the requested information.) |
|
Reopening to prevent @junyer having to relocate his ideas yet again. :) |
mvdan
removed
the
WaitingForInfo
|
I think @gopherbot needs to be taught some manners. |
|
That benchmark site has not been updated in a year. I just ran the input with the tip compiler (go version devel +aa20ae4853 Mon Nov 12 23:07:25 2018 +0530 linux/amd64), along with converting the benchmark to an idiomatic one. Code - package main
import (
"bytes"
"log"
"os"
"regexp"
"testing"
)
var matches []string
var count int
func measure(data string, pattern string, b *testing.B) {
r, err := regexp.Compile(pattern)
if err != nil {
log.Fatal(err)
}
for i := 0; i < b.N; i++ {
matches = r.FindAllString(data, -1)
count = len(matches)
}
}
func BenchmarkAll(b *testing.B) {
filerc, err := os.Open(os.Getenv("FILE_NAME"))
if err != nil {
log.Fatal(err)
}
defer filerc.Close()
buf := new(bytes.Buffer)
buf.ReadFrom(filerc)
data := buf.String()
// Email
b.Run("Email", func(b *testing.B) {
measure(data, `[\w\.+-]+@[\w\.-]+\.[\w\.-]+`, b)
})
// URI
b.Run("URI", func(b *testing.B) {
measure(data, `[\w]+://[^/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?`, b)
})
// IP
b.Run("IP", func(b *testing.B) {
measure(data, `(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])`, b)
})
}With that, if I compare with 1.10, there is a substantial improvement now And also the total is now 1415ms which brings us above Python3. If we are to go by the original issue title, I'd say it is pretty much resolved. Only @junyer's comments here have some concrete suggestions to improve. I don't know whether they are still applicable in the current tip as of now. I will let someone investigate that and re-purpose the issue to that effect. |
agnivade
changed the title
agnivade
added
the
NeedsInvestigation
|
As per https://perf.golang.org/search?q=upload:20181127.2, moving the Note that this is the regular expression used for the |
|
As per https://perf.golang.org/search?q=upload:20181127.3, letting |
|
Both of those are quite trivial changes. I also suggested reducing the overhead of |
|
This may be a bit of a wild idea (that would likely need to be tracked in a separate issue, but as I'm not even sure how feasible it is and as it's related to this pretty open-ended issue I'm dumping it here) but it came to mind while reading this old article from @dgryski: would it make sense, for regexp source expressions known at compile time, having the go compiler compile the regexp and then emit native machine code implementing To avoid having to generate native code directly just for the regexp it would probably be ok to generate go code and let the rest of the go compiler handle that. |
There is precedent for this, namely CTRE for C++, and what used to be rust's compile-time regex macro. The optimization doesn't seem too farfetched to me, since it's similar to how intrinsics and SSA rules can redirect usage of the standard library to different implementations. As a side note, it would be an interesting project for someone to put together a |
|
CTRE is a veritable nightmare of C++ template metaprogramming. Let us never speak of it again. The state of the art for code generation is probably Trofimovich's TDFA work for RE2C. See http://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf. |
|
This pcre based regex gave better performance compared to regexp - still PHP preg_match out performed in my test of (apache access log parsing). |
golang regex is so slow: golang/go#26623 --------------------------------- keys_size | FlashText (s) | Regex (s) 10 | 0.00053121 | 0.007381449 1010 | 0.000902698 | 1.021105121 2010 | 0.001164453 | 2.155324188 3010 | 0.001272009 | 3.189556999 4010 | 0.001415052 | 4.489287341 5010 | 0.00151844 | 5.662644436 6010 | 0.001601235 | 6.820220812 7010 | 0.001711219 | 7.845579981 8010 | 0.001785076 | 9.740038207 ...
golang regex is so slow: golang/go#26623 --------------------------------- keys_size | FlashText (s) | Regex (s) 10 | 0.00053121 | 0.007381449 1010 | 0.000902698 | 1.021105121 2010 | 0.001164453 | 2.155324188 3010 | 0.001272009 | 3.189556999 4010 | 0.001415052 | 4.489287341 5010 | 0.00151844 | 5.662644436 6010 | 0.001601235 | 6.820220812 7010 | 0.001711219 | 7.845579981 8010 | 0.001785076 | 9.740038207 ...
That makes me think of a couple of less extreme optimisations:
|
|
FWIW there's a good number of unreviewed CLs by @bboreham improving regexp performance that have been sitting for a cycle or so: Of the list, CL 355789 is exceptionally small (take the address of a big struct instead of copying it; 4 line change) compared to its 30-40% perf benefit. |
|
And, the benchstat with those 5 applied: TimeAllocSpeed |
|
CL 355789 (the "exceptionally small" yet powerful CL mentioned previously) has been merged for Go 1.19! 🎉 (The CL didn't mention this issue, so the commit didn't trigger a thread update, hence me mentioning since so many are following this thread. The other 4 CLs are still pending review.) |
ghost
mentioned this issue
|
are there other significant performance increases in the works, or is the current 1.19 release considered "good enough" compared to other languages that speed is no longer an issue? |
|
Of the CLs I listed in #26623 (comment), only one has been reviewed and merged; the rest remain unreviewed. There are certainly a few boosts in there. (I can't answer a question about what defines "good enough".) |
|
#11646 isn't "in the works" anymore, evidently, which is unfortunate, but unsurprising due to its complexity. |
|
Just out of curiosity updated the versions and ran it today:
|
Languages Regex Benchmark:
In the above benchmark, Go's regex is even slower than Python. It is not ideal because as Python is a scripting language, and Go is a static language, Go should be faster than Python.
I noticed that there's an issue here: #19629, and someone said that because Python uses C for regex, and C is faster than Go. But Python is a cross-platform language and it can enjoy the C regex implementations for all platforms. Why can't Go do the same thing? This may be a stupid question but I just don't understand why Go has to use cgo to call C code, but Python doesn't have this limitation? Thanks.
The text was updated successfully, but these errors were encountered: