22 ms·
Go performance from version 1.2 to 1.18
- davidkuennen 5y agoI've been using go services for my backends for years and I've totally fallen in love. I'm always amazed whenever I write something for like an hour, then compile it and it just works. It usually never does.
- truncate 5y ago>> I’m looking forward to someone improving the performance of Go’s regexp package, which is quite slow. 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.
- throwaway894345 5y agoYeah, if you can call straight into a C module (e.g., regex or csv or etc) and not do anything of consequence in Python, that’s the sweet spot from a performance perspective.
- benhoyt 5y agoInteresting, though not too surprising. Do you remember what the regexes were that your assignment used? 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 https://swtch.com/~rsc/regexp/regexp1.html, and 2) it's a relatively simple implementation.
- pcwalton 5y agoSimplicity of implementation isn't what users need, though; they need performance. For example, you can make GCC into a much simpler C compiler by compiling at -O0, but in practice nobody does that.
- benhoyt 5y agoTotally 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 agoHave 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 agoYeah, 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 agoFor 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.
- frutiger 5y ago> 1) it's guaranteed linear time in the length of the input What’s the multiplicative factor? Does it dominate for “typical” regexes?
- pcwalton 5y agoFor most regexes, backtracking and Thompson NFA have the same asymptotic complexity, which is why most languages adopted backtracking. The implementors of such languages knew what they were doing, especially when you consider that by adopting the Thompson NFA means you give up backreferences. The differences only arise with pathological 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?)
- tedunangst 5y agoPeople will gleefully write that regex if it causes a denial of your service. People would similarly blow up ftp servers with "ls starstarstarstar" globs.
- burntsushi 5y agoFWIW, I would say that it's difficult for a Thompson NFA on its own to beat backtracking in non-pathological cases. So I actually think your prior is still mostly correct. 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 (This is using an yet-unreleased tool as part of ongoing regex development.)
- mattgreenrocks 5y agoGiven that Go's original raison d'etre was Internet-facing services, the choice for guaranteed linear time execution makes sense as a default.
- jeffbee 5y agoThat ... isn't really true at all. Go's original raison was logs processing.
- alecthomas 5y agoI'd be interested in reading more about that. Do you have a reference?
- icholy 5y agoI think they're referring to Rob Pike's Sawzall language. However, I wouldn't call Go a descendant of it.
- sanxiyn 5y agoAs Knuth opined in an often quoted passage, it is criminally negligent to avoid 10% performance improvement to keep implementation simplicity.
- rastignack 5y agoWay to never deliver. Absolute numbers like this are pointless.
- bboreham 5y agoI have done some optimisations in Go regex recently; I have a talk coming up on Saturday: https://fosdem.org/2022/schedule/event/go_finite_automata/ 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 https://github.com/grafana/regexp/tree/speedup#readme
- benhoyt 5y agoThat's excellent! Those all look like pretty nice small code changes that all add up. I especially like the very small "avoid copy" change (https://go-review.googlesource.com/c/go/+/355789 https://go-review.googlesource.com/c/go/+/355789) that adds up to a 30% speedup on many benchmarks. I hope they get included in Go 1.19. Good work!
- truncate 5y agoIt was 7 years ago, so I don't exactly remember what regex I used. I remember it was information retrieval course, and was supposed to write a crawler and index the webpage. So I think part of it was definitely to find all the links within webpage. I was working on extra credit so there might be some funky stuff.
- catlifeonmars 5y agoOne of our ACLs at work relies heavily on Go regexp. The performance of evaluation is actually not too bad. What is quite terrible is the performance of *compiling* regexps.
- benhoyt 5y agoI find this a bit surprising -- do you have numbers? Though even if compiling them is relatively slow it doesn't matter too much, because usually you're compiling once and evaluating many many times (e.g., in the case of a typical AWK script, you compile once and evaluate for each line in the input).
- catlifeonmars 5y agohttps://gist.github.com/jncornett/4a908250d701aec52a11d61a8953c4bb https://gist.github.com/jncornett/4a908250d701aec52a11d61a89... 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
- xpressvideoz 5y agoAccording to my totally unscientific benchmarks, if the performance of Rust's regular expression module were 1x, Go's was 8x and Ruby's was 32x, and Java's was 42x. Using Google's Java regex module improved the speed quite a bit but still was at ~18x. I was very impressed to see Rust doing so well. And it was sad to see Java so underperforming in such a typical workload. I know we're measuring libraries not languages, but I think regexes are so prevalent that not optimizing for it would hinder the language's real life performance.
- pcwalton 5y agoBy performance you mean elapsed time, right? So by 8x you mean 8x slower?
- xpressvideoz 5y agoYeah that's right. I compiled a pattern and matched it against a huge wall of text, measuring elapsed time.
- tapirl 5y agoconvenient to show your benchmarks?
- xpressvideoz 5y agoUnfortunately, the test code belongs to the company I work for so I cannot take it out. It was done to determine what language we should use for an internal tool. I hope to conduct another benchmark one day, publicly this time.
- dekelpilli 5y agoNot OP, but Benchmarks Game has a performance test based on regex: https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/regexredux.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... The top times for the mentioned languages are: Rust: 0.78s Ruby: 12.33s Java: 5.34s Go: 3.80s Python: 1.34s
- snarkerson 5y agoVersion Numbering bothers me. Mathematically 1.2 is greater than 1.18. Yet in versions it is lesser. I find this annoying and counter intuitive.
- sinsterizme 5y agoYeah I always get tripped up. I feel like we should write it as 1.02, that way it can get up to 1.99 without this issue :)
- titzer 5y agoMe too. 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. :)
- chrismorgan 5y agoIf your algorithm is “choose the next number for which its Roman numeral sorts lexicographically higher than the current number”, then if you start at 1 you will only get 35 elements, since 38 (XXXVIII) is the lexicographically-highest Roman numeral. 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}')
- 5y ago
- darkgray 5y agoMe too. I have a project suffering pretty badly from the performance hit taken when a regexp doesn't start with a fixed string. Matching against `[ab]cd` is up to 9x slower than against `ab[cd]`.
- smasher164 5y agoThere's a lot of room for improvement on the compiler and library end. RE2 and Hyperscan demonstrate the ceiling here. 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 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 https://github.com/golang/go/issues/11646.
- titzer 5y ago> A recent improvement was in version 1.17, which passes function arguments and results in registers instead of on the stack. This was a significant improvement for GoAWK’s old tree-walking interpreter, where I saw a 38% increase in speed on one microbenchmark, and a 17% average speedup across all microbenchmarks I find that surprising that Go did not use registers for its (internal) calling convention until 1.17. And I also find it surprising that they only expected a 5% boost from it.
- tptacek 5y agoSince its initial release, Go has used a stack-based calling convention based on the Plan 9 ABI, in which arguments and result values are passed via memory on the stack. This has significant simplicity benefits: the rules of the calling convention are simple and build on existing struct layout rules; all platforms can use essentially the same conventions, leading to shared, portable compiler and runtime code; and call frames have an obvious first-class representation, which simplifies the implementation of the go and defer statements and reflection calls. Furthermore, the current Go ABI has no callee-save registers, meaning that no register contents live across a function call (any live state in a function must be flushed to the stack before a call). This simplifies stack tracing for garbage collection and stack growth and stack unwinding during panic recovery. https://go.googlesource.com/proposal/+/refs/changes/78/248178/1/design/40724-register-calling.md https://go.googlesource.com/proposal/+/refs/changes/78/24817...
- titzer 5y agoI didn't consider the effects of goroutines, but it's pretty common that JITs that have to emit precise stackmaps simply don't use callee-saved registers, so it doesn't seem any harder to make goroutine stacks first-class. But the detail is in the details, always.
- sanxiyn 5y agoThis is basically argument from implementation simplicity. I am of the opinion that implementation simplicity is overrated, and should be essentially ignored, especially for projects as widely used as Go.
- tgtweak 5y agoThe thing people don't seem to appreciate/understand with go is the effects of using it in serverless and cloud native environments. Every high throughput service I've had moved to GO has used a tiny amount of Memory and CPU compared to the implementation it replaced, typically nodejs, python, Scala and .net. In a cloud world where it's usually boiled down to pay-per MB of in-process memory and per cycle... That can be 4-5 figures a month in reduced cloud cost for the same traffic. Tiny output binaries are also very quick to transfer and spin up in serverless as well - often reducing costs further. The benefits over time of essentially knowing things will get faster with each new version is really encouraging as well. Imagine your cloud bill went down over time as a result of simply rebuilding your service on newer golang core and redeploying.
- ctopher7 5y agohow about using rust in cloud native env? I write in go for a living (my company uses it company wide) but I use rust for my personal project never had the chance to compare both performance
- dimgl 5y ago+1 for this. There is some upfront cost though around learning Golang. Writing idiomatic Golang code takes a bit of getting used to.
- baby 5y agoHonestly Golang is not hard to learn, compared to other typed languages like Rust.
- seanw444 5y agoTook me maybe two days to feel comfortable rewriting one of my bigger projects from Python to Go. Absolutely wonderful language.
- dagmx 5y agoI think it depends on personal mental models. I found rust easier to get to grips with because it was more straightforward for the way I thought, whereas with Go I struggled with a lot of things that felt funky to me. I fully agree that Go is a simpler language up front though at the syntax level.
- byteshock 5y agoWould using a library like Hyperscan improve Go's regex performance? Reference: https://www.hyperscan.io/ https://www.hyperscan.io/
- ThePhysicist 5y agoIn my understanding Hyperscan is interesting if you want to check thousands or millions of Regexes against a single string. Normal regular expression libraries would force you to create a state machine for each regex and run them all one by one against a string/byte sequence, whereas Hyperscan builds a single state machine from all the regexes, which it then runs against the string/byte sequence. As most states/regexes will usually be inactive that can dramatically speed up the matching process. Hyperscan is often used in situations where you have many patterns that you want to test against the same string/byte sequence, e.g. in malware signature detection. I thought about writing a Hyperscan-alike Regex library in Golang, just not sure how well that would perform with the dynamic memory allocation. I think if you could ensure to do allocations only once during initialization it should be pretty fast. I once built parser generators in Golang and I remember it was a bit painful optimizing them due to dynamic memory allocation, I think for such low-level stuff C or C++ is still better (though I was not very well versed in Golang at the time, so maybe that was on me).
- elcapitan 5y ago
- ammmir 5y agoI love Go. It's the new Java, but fewer batteries included, and very easy to learn. I spent a day going over https://gobyexample.com/ https://gobyexample.com/ and became productive the next day. I tried to do the same with Rust, but I failed. Nobody was able to succinctly explain all the things you have to learn to become productive with Rust, let alone understand anyone else's code, since there are too many different ways of doing the same shit. I fear generics will make Go go in a worse direction, but I'm not losing sleep over it. I would even go as far as to say Go is the fastest way to land a $100K/yr job with zero knowledge about programming and still be able to live with yourself (unlike with the JavaScript/npm oligopoly). Solid Go'ers eschew huge dependencies and prefer classic Unix KISS philosophies. It's a breath of fresh air. And like the performance figures show, your apps magically get slightly faster over the years! Life is short, use Go.
- chakkepolja 5y agoGo is probably most productive language I'd use for CLI tools and quick server stuff. There are libraries for most things you need, often better documented than python counterparts. Single binary and good tooling. Now, one may hate something about the language but at the end we bite the bullet and get things done. That said, Go doesn't have a great ecosystem for website backend dev. You can do it, but often less convenient.
- asadlionpk 5y agoWhen you say website backend dev. What can be improved?
- maattdd 5y agoTypesafe SQL, typesafe template (or just useful template, not the ones in the stdlib which sucks tremendously), model metaprogramming, etc...
- alecthomas 5y agoFWIW for SQL, sqlc[1] is probably the nicest SQL layer I've used in any language. [1] https://github.com/kyleconroy/sqlc https://github.com/kyleconroy/sqlc
- deleted 5y ago[deleted]