7 ms·

So on most real world applications, you shave perhaps a second or two off compilation and linking times. That's great, but... why does Go still have such an ab

So on most real world applications, you shave perhaps a second or two off compilation and linking times. That's great, but... why does Go still have such an abysmal regexp package that is an order of magnitude slower than C and C++?[1] Why does encoding/json still rely on reflection, making it slow compared to other approaches?[2] In other words, I guess I feel like there are areas with more bang for the buck. The changes in 1.3 are great (100% precise garbage collection!), but I'm hoping improvements to regexp and encoding/json are somewhere on the roadmap as well. [1] http://benchmarksgame.alioth.debian.org/u64q/performance.php?test=regexdna&sort=elapsed http://benchmarksgame.alioth.debian.org/u64q/performance.php... [2] https://journal.paul.querna.org/articles/2014/03/31/ffjson-faster-json-in-go/ https://journal.paul.querna.org/articles/2014/03/31/ffjson-f...

thrownaway2424 12y ago
No idea about the regexp performance (it's been adequate for my uses). For encoding/json it's probably slow because nobody at Google gives two shits about JSON; they use protocol buffers for everything. Someone from outside Google would have to contribute encoding/json performance improvements if they need them.
- enneff 12y ago
  That's not true. We do care about JSON encoding/decoding performance, and encoding/json is pretty decent. It's just not as blazing fast as some other implementations. Our focus has been on providing a convenient API that's suitable for most uses, and that's what we have achieved IMO. There are alternatives for people who really need the extra speed, as burntsushi mentioned.
zik 12y ago
It's open source, so if these things are a priority for you then you should definitely consider improving them yourself.
kyrra 12y ago
Go uses a different regex algorithm that doesn't fall over in corner cases. See: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html And Russ's comment here: https://groups.google.com/forum/m/#!topic/golang-nuts/6d1maef4jQ8 https://groups.google.com/forum/m/#!topic/golang-nuts/6d1mae... EDIT: I shouldn't answer question I don't know the full answer to.
- comex 12y ago
  The comment does not accurately reflect the state of the benchmarks today. (I do not know whether it accurately reflects the state of the benchmarks at the time of posting.) While some of the implementations are backtracking, the #2 slot is currently held by a C++ implementation that uses RE2: https://code.google.com/p/re2/ https://code.google.com/p/re2/ which also provides the linear guarantee. Edit: Apparently I forgot that RE2 was also written by Russ Cox, so he should know well that it provides better performance with the same guarantee.
Laremere 12y ago
I think it's a mater of the priorities of the language developers. <I've removed my thoughts on regex here because others have posted with more knowledge on the subject> As for runtime reflection, it's a very handy tool which allows for quick development iteration. The page you link generates more efficient Go code, however it comes at the price of being more brittle. I've used standard library json package for things like reading a config file, where the time difference isn't noticeable. One size doesn't fit all, and if you're application really needs to parse lots of json quickly, then a more rigid approach may be in order.
burntsushi 12y ago
I grant that your questions are probably rhetorical, but I'll take a shot at them anyway. While I was writing Rust's regex crate, I became very familiar with Russ Cox's work on implementing a regex engine with worst case O(mn) time complexity (m ~ regex and n ~ search text). As far as I know, he has two implementations of these ideas: RE2 (C++) and Go's regexp package. RE2 is extremely sophisticated. It includes a full NFA simulation (known as the "Pike VM") that can find submatches, and it also includes a DFA that avoids repeating work (but cannot find submatches). The DFA is very very fast (and I believe is multithreaded). The NFA simulation isn't as fast and is only used when necessary. Go's regexp package only includes a full NFA simulation. There is no speedy DFA. My guess is that this is the primary reason why it is slow. (I will, however, note that Go 1.3 will include a reasonably large optimization which introduces a "one-pass" NFA simulation. It's used when it can be proven that the regex will never need to backtrack. Rob Pike posted some benchmarks on golang-dev a while back, and they showed a perf improvement in the regexp package. So they at least seem to be working on things that you care about.) Speaking from a higher level, I'd say that the raw performance of regexes is probably not a huge priority. Needing wickedly fast regexes seems like a special case to me, in which case, you might just use an existing library to do it via cgo. (And indeed, the benchmark's game includes some Go benchmarks that use the PCRE C library, which has more reasonable performance.) For more details on how it all works, Russ has written an amazing series of articles on the topic: http://swtch.com/~rsc/regexp/ http://swtch.com/~rsc/regexp/ > Why does encoding/json still rely on reflection, making it slow compared to other approaches? Using reflection makes encoding/decoding JSON extraordinarily convenient. I do the same with TOML[1], although admittedly, performance is less of an issue there. My suspicion is that the added complexity for when you need raw speed isn't common enough to be in the standard library. megajson[2] tries to fill this hole, but it's a code generation tool, so you may find that less than ideal. [1] - https://github.com/BurntSushi/toml https://github.com/BurntSushi/toml [2] - https://github.com/benbjohnson/megajson https://github.com/benbjohnson/megajson
- bjz_ 12y ago
  For the benefit of others, here is burntsushi's regex crate for Rust (compile time regexes included): http://static.rust-lang.org/doc/master/regex/index.html http://static.rust-lang.org/doc/master/regex/index.html
bmatsuo 12y ago
Regular expressions are used less frequently in Go than in many popular languages (esp. dynamic ones). Often the "strings" package suffices. I almost never import "regexp". So yea. As people have said, I don't think it's a high priority.
- enneff 12y ago
  Rob wrote about this: http://commandcenter.blogspot.com.au/2011/08/regular-expressions-in-lexing-and.html http://commandcenter.blogspot.com.au/2011/08/regular-express...
- coldtea 12y ago
  >Often the "strings" package suffices. Suffices for whom and for what work? Maybe suffices for you. This is not a dynamic vs static language issue -- C and C++ users use regexes all the time. It's a matter of business needs (e.g what you need your program to do).
  - dchest 12y ago
    True, but there's also another factor: in Go it's easy to write string manipulation functions that are fast, while in most dynamic languages some regular expressions would run faster than your hand-written routine.
    - coldtea 12y ago
      Perhaps, but I'm not 100% about that without some profiling. For one, Go tends to offer string stuff implemented in Go, whereas dynamic languages usually delegate string operations to plain old C, which can be faster (especially when Unicode is added into the picture).
enneff 12y ago
> So on most real world applications, you shave perhaps a second or two off compilation and linking times. It's important to note that these linker changes are just a single step as part of a long-term plan to translate the Go compilers from C to Go. Once the compiler is written in Go it will be much easier to improve both compilation speed and the performance of the generated code. The plan: https://docs.google.com/a/google.com/document/d/1P3BLR31VA8cvLJLfMibSuTdwTuF7WWLux71CYD0eeD8/preview?sle=true https://docs.google.com/a/google.com/document/d/1P3BLR31VA8c...
- mratzloff 12y ago
  That's an important point that I didn't take into consideration. Thanks!
ithkuil 12y ago
> So on most real world applications, you shave perhaps a second or two off compilation and linking times. Which might be a significant part of the overall build time, if it takes 5-8 seconds to build.
- jerf 12y ago
  In my experience, it's not hard to have the same basic compile-run test-fix cycle with Go that it is with interpreted languages. Shaving a second off that may not save me a lot of literal clock time, but it makes it that much more pleasant to use, and therefore, that much less likely that I'll take unfortunate shortcuts. I haven't gotten up to a truly large Go code base, the whole shebang right now is only about ~25,000 lines, but the full save-test cycle is still comparable to what I get with a short Python script. (Though as I like to point out occasionally, if you sample a lot of languages in the world, real-world C and C++ programs have exceptionally long compile times due to ancient design decisions. Most other compiled languages are actually quite fast to compile. Go is striving to be fast even so, but when benchmarked against something other than C or C++ it seems less spectacular.)
  - pcwalton 12y ago
    > (Though as I like to point out occasionally, if you sample a lot of languages in the world, real-world C and C++ programs have exceptionally long compile times due to ancient design decisions. Most other compiled languages are actually quite fast to compile. Go is striving to be fast even so, but when benchmarked against something other than C or C++ it seems less spectacular.) Nowadays, especially with unity builds, a lot of the reason that C and C++ are slow to compile (especially C) is actually that optimizations and codegen take a while. Most languages use JITs, so their compile steps are much faster. With the 6g/8g compilers, Go doesn't really do the same kind of optimization that e.g. GCC and LLVM do (e.g. SSA conversion, GVN, SCCP, LICM, aggressive algebraic simplifications, etc), so much of its build speed comes from that. In my experience, there's no free lunch: fast compiles come at the expense of runtime performance, and runtime performance comes at the expense of fast compilation.
  - ithkuil 12y ago
gkya 12y ago
> [...] I guess I feel like there are areas with more bang for the buck [other than the linker]. Well, for a ~5-years-old language, the linker and the compiler is most presumably more important than the standard-library regexp-engine/json-package.
melling 12y ago
It's a 30% reduction in link times. That translates into a couple seconds for many projects. However, Go was built so developers could build those million line apps.

thrownaway2424 12y ago

No idea about the regexp performance (it's been adequate for my uses). For encoding/json it's probably slow because nobody at Google gives two shits about JSON; they use protocol buffers for everything. Someone from outside Google would have to contribute encoding/json performance improvements if they need them.

enneff 12y ago
That's not true. We do care about JSON encoding/decoding performance, and encoding/json is pretty decent. It's just not as blazing fast as some other implementations. Our focus has been on providing a convenient API that's suitable for most uses, and that's what we have achieved IMO. There are alternatives for people who really need the extra speed, as burntsushi mentioned.

zik 12y ago

It's open source, so if these things are a priority for you then you should definitely consider improving them yourself.

kyrra 12y ago

Go uses a different regex algorithm that doesn't fall over in corner cases. See: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html And Russ's comment here: https://groups.google.com/forum/m/#!topic/golang-nuts/6d1maef4jQ8 https://groups.google.com/forum/m/#!topic/golang-nuts/6d1mae... EDIT: I shouldn't answer question I don't know the full answer to.

comex 12y ago
The comment does not accurately reflect the state of the benchmarks today. (I do not know whether it accurately reflects the state of the benchmarks at the time of posting.) While some of the implementations are backtracking, the #2 slot is currently held by a C++ implementation that uses RE2: https://code.google.com/p/re2/ https://code.google.com/p/re2/ which also provides the linear guarantee. Edit: Apparently I forgot that RE2 was also written by Russ Cox, so he should know well that it provides better performance with the same guarantee.

Laremere 12y ago

I think it's a mater of the priorities of the language developers. <I've removed my thoughts on regex here because others have posted with more knowledge on the subject> As for runtime reflection, it's a very handy tool which allows for quick development iteration. The page you link generates more efficient Go code, however it comes at the price of being more brittle. I've used standard library json package for things like reading a config file, where the time difference isn't noticeable. One size doesn't fit all, and if you're application really needs to parse lots of json quickly, then a more rigid approach may be in order.

burntsushi 12y ago

I grant that your questions are probably rhetorical, but I'll take a shot at them anyway. While I was writing Rust's regex crate, I became very familiar with Russ Cox's work on implementing a regex engine with worst case O(mn) time complexity (m ~ regex and n ~ search text). As far as I know, he has two implementations of these ideas: RE2 (C++) and Go's regexp package. RE2 is extremely sophisticated. It includes a full NFA simulation (known as the "Pike VM") that can find submatches, and it also includes a DFA that avoids repeating work (but cannot find submatches). The DFA is very very fast (and I believe is multithreaded). The NFA simulation isn't as fast and is only used when necessary. Go's regexp package only includes a full NFA simulation. There is no speedy DFA. My guess is that this is the primary reason why it is slow. (I will, however, note that Go 1.3 will include a reasonably large optimization which introduces a "one-pass" NFA simulation. It's used when it can be proven that the regex will never need to backtrack. Rob Pike posted some benchmarks on golang-dev a while back, and they showed a perf improvement in the regexp package. So they at least seem to be working on things that you care about.) Speaking from a higher level, I'd say that the raw performance of regexes is probably not a huge priority. Needing wickedly fast regexes seems like a special case to me, in which case, you might just use an existing library to do it via cgo. (And indeed, the benchmark's game includes some Go benchmarks that use the PCRE C library, which has more reasonable performance.) For more details on how it all works, Russ has written an amazing series of articles on the topic: http://swtch.com/~rsc/regexp/ http://swtch.com/~rsc/regexp/ > Why does encoding/json still rely on reflection, making it slow compared to other approaches? Using reflection makes encoding/decoding JSON extraordinarily convenient. I do the same with TOML[1], although admittedly, performance is less of an issue there. My suspicion is that the added complexity for when you need raw speed isn't common enough to be in the standard library. megajson[2] tries to fill this hole, but it's a code generation tool, so you may find that less than ideal. [1] - https://github.com/BurntSushi/toml https://github.com/BurntSushi/toml [2] - https://github.com/benbjohnson/megajson https://github.com/benbjohnson/megajson

bjz_ 12y ago
For the benefit of others, here is burntsushi's regex crate for Rust (compile time regexes included): http://static.rust-lang.org/doc/master/regex/index.html http://static.rust-lang.org/doc/master/regex/index.html

bmatsuo 12y ago

Regular expressions are used less frequently in Go than in many popular languages (esp. dynamic ones). Often the "strings" package suffices. I almost never import "regexp". So yea. As people have said, I don't think it's a high priority.

enneff 12y ago
Rob wrote about this: http://commandcenter.blogspot.com.au/2011/08/regular-expressions-in-lexing-and.html http://commandcenter.blogspot.com.au/2011/08/regular-express...
coldtea 12y ago
>Often the "strings" package suffices. Suffices for whom and for what work? Maybe suffices for you. This is not a dynamic vs static language issue -- C and C++ users use regexes all the time. It's a matter of business needs (e.g what you need your program to do).
- dchest 12y ago
  True, but there's also another factor: in Go it's easy to write string manipulation functions that are fast, while in most dynamic languages some regular expressions would run faster than your hand-written routine.
  - coldtea 12y ago
    Perhaps, but I'm not 100% about that without some profiling. For one, Go tends to offer string stuff implemented in Go, whereas dynamic languages usually delegate string operations to plain old C, which can be faster (especially when Unicode is added into the picture).

enneff 12y ago

> So on most real world applications, you shave perhaps a second or two off compilation and linking times. It's important to note that these linker changes are just a single step as part of a long-term plan to translate the Go compilers from C to Go. Once the compiler is written in Go it will be much easier to improve both compilation speed and the performance of the generated code. The plan: https://docs.google.com/a/google.com/document/d/1P3BLR31VA8cvLJLfMibSuTdwTuF7WWLux71CYD0eeD8/preview?sle=true https://docs.google.com/a/google.com/document/d/1P3BLR31VA8c...

mratzloff 12y ago
That's an important point that I didn't take into consideration. Thanks!

ithkuil 12y ago

> So on most real world applications, you shave perhaps a second or two off compilation and linking times. Which might be a significant part of the overall build time, if it takes 5-8 seconds to build.

jerf 12y ago
In my experience, it's not hard to have the same basic compile-run test-fix cycle with Go that it is with interpreted languages. Shaving a second off that may not save me a lot of literal clock time, but it makes it that much more pleasant to use, and therefore, that much less likely that I'll take unfortunate shortcuts. I haven't gotten up to a truly large Go code base, the whole shebang right now is only about ~25,000 lines, but the full save-test cycle is still comparable to what I get with a short Python script. (Though as I like to point out occasionally, if you sample a lot of languages in the world, real-world C and C++ programs have exceptionally long compile times due to ancient design decisions. Most other compiled languages are actually quite fast to compile. Go is striving to be fast even so, but when benchmarked against something other than C or C++ it seems less spectacular.)
- pcwalton 12y ago
  > (Though as I like to point out occasionally, if you sample a lot of languages in the world, real-world C and C++ programs have exceptionally long compile times due to ancient design decisions. Most other compiled languages are actually quite fast to compile. Go is striving to be fast even so, but when benchmarked against something other than C or C++ it seems less spectacular.) Nowadays, especially with unity builds, a lot of the reason that C and C++ are slow to compile (especially C) is actually that optimizations and codegen take a while. Most languages use JITs, so their compile steps are much faster. With the 6g/8g compilers, Go doesn't really do the same kind of optimization that e.g. GCC and LLVM do (e.g. SSA conversion, GVN, SCCP, LICM, aggressive algebraic simplifications, etc), so much of its build speed comes from that. In my experience, there's no free lunch: fast compiles come at the expense of runtime performance, and runtime performance comes at the expense of fast compilation.
- ithkuil 12y ago

gkya 12y ago

> [...] I guess I feel like there are areas with more bang for the buck [other than the linker]. Well, for a ~5-years-old language, the linker and the compiler is most presumably more important than the standard-library regexp-engine/json-package.

melling 12y ago

It's a 30% reduction in link times. That translates into a couple seconds for many projects. However, Go was built so developers could build those million line apps.