4 ms·

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 R

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
- chrismorgan 12y ago
  And at present it is NFA-only, no DFA fast path. But among NFA implementations, the compile-time regular expression engine is unbeatable.
benbjohnson 12y ago
JSON is inherently slow to parse. Even with the code generation of megajson, you can only get 2x performance at best. The megajson package has microbenchmarks for all the individual parsing tasks so you can get an idea of where things are slow. Here's are the benchmarks from my MacBook Pro: https://gist.github.com/benbjohnson/6380fab7cac7533115e5 https://gist.github.com/benbjohnson/6380fab7cac7533115e5 JSON is slow because of (at least) two reasons: 1) Strings are unframed - You have to check every single byte to see if it's a double quote to end the string. Compare this to MessagePack or Protobufs where the encoding states the exact length of the string. Those are faster because you can simply memmove() it. 2) Numbers require base 10 conversion - Numbers in JSON are typically only a couple bytes long. So for every 1 - 10 bytes you have to do an atoi(). You may have to do that a couple hundred thousand times in a megabyte of JSON. Numbers are also unframed so they suffer from the same "check-every-byte" issue as strings. I feel like the encoding/json package actually does a great job in balancing parsing speed and convenience.
- jerf 12y ago
  3) JSON's object encoding is very fluffy and redundant. If one has an array of objects each of which all have the same set of keys (a very common use case), the keys must be spelled out each time, with double-quotes and other punctuation around them, for each usage. There's a result from elementary complexity analysis which many have probably forgotten, which is that the time complexity of an algorithm is lower-bounded by the space complexity, because if an algorithm has a space complexity of O(n^2), it must have at least O(n^2) time complexity because that's how long it takes to even look at O(n^2) space once. Similarly, by being so fluffy, JSON incurs fundamental speed penalties that can not be recovered simply by virtue of being so physically large. JSON is convenient and quite cross-platform. This carries it to a lot of places, quite justifiably. However, if speed is a concern, JSON is often a poor choice. It is literally impossible, no matter how clever you get, to write a JSON decoder that will be as fast as Protocol Buffers can be, because you can never overcome the fact that the JSON decoder has to look at more bytes. (No matter how cleverly you encode your JSON such that the result is a legal JSON file in the end, with key compression or whatever, other serialization methods can be just as clever, but then don't have JSON restrictions on how bytes are spent.)

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

chrismorgan 12y ago
And at present it is NFA-only, no DFA fast path. But among NFA implementations, the compile-time regular expression engine is unbeatable.

benbjohnson 12y ago

JSON is inherently slow to parse. Even with the code generation of megajson, you can only get 2x performance at best. The megajson package has microbenchmarks for all the individual parsing tasks so you can get an idea of where things are slow. Here's are the benchmarks from my MacBook Pro: https://gist.github.com/benbjohnson/6380fab7cac7533115e5 https://gist.github.com/benbjohnson/6380fab7cac7533115e5 JSON is slow because of (at least) two reasons: 1) Strings are unframed - You have to check every single byte to see if it's a double quote to end the string. Compare this to MessagePack or Protobufs where the encoding states the exact length of the string. Those are faster because you can simply memmove() it. 2) Numbers require base 10 conversion - Numbers in JSON are typically only a couple bytes long. So for every 1 - 10 bytes you have to do an atoi(). You may have to do that a couple hundred thousand times in a megabyte of JSON. Numbers are also unframed so they suffer from the same "check-every-byte" issue as strings. I feel like the encoding/json package actually does a great job in balancing parsing speed and convenience.

jerf 12y ago
3) JSON's object encoding is very fluffy and redundant. If one has an array of objects each of which all have the same set of keys (a very common use case), the keys must be spelled out each time, with double-quotes and other punctuation around them, for each usage. There's a result from elementary complexity analysis which many have probably forgotten, which is that the time complexity of an algorithm is lower-bounded by the space complexity, because if an algorithm has a space complexity of O(n^2), it must have at least O(n^2) time complexity because that's how long it takes to even look at O(n^2) space once. Similarly, by being so fluffy, JSON incurs fundamental speed penalties that can not be recovered simply by virtue of being so physically large. JSON is convenient and quite cross-platform. This carries it to a lot of places, quite justifiably. However, if speed is a concern, JSON is often a poor choice. It is literally impossible, no matter how clever you get, to write a JSON decoder that will be as fast as Protocol Buffers can be, because you can never overcome the fact that the JSON decoder has to look at more bytes. (No matter how cleverly you encode your JSON such that the result is a legal JSON file in the end, with key compression or whatever, other serialization methods can be just as clever, but then don't have JSON restrictions on how bytes are spent.)