4 ms·

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 f

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.)
- kibwen 12y ago
  > the time complexity of an algorithm is lower-bounded by > the space complexity Just wanted to say that this is an awesome result that I hadn't considered before. Very cool.
  - jerf 12y ago
    It's the rare case of a theoretical result whose theoretical impact is fairly marginal but practical impact is enormous... when you set out to seriously optimize something, you will eventually hit a point where this starts to become a serious consideration. Serialization is a particularly vivid and easy-to-see example, but sooner or later you'll hit it in any serious optimization effort.

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.)

kibwen 12y ago
> the time complexity of an algorithm is lower-bounded by > the space complexity Just wanted to say that this is an awesome result that I hadn't considered before. Very cool.
- jerf 12y ago
  It's the rare case of a theoretical result whose theoretical impact is fairly marginal but practical impact is enormous... when you set out to seriously optimize something, you will eventually hit a point where this starts to become a serious consideration. Serialization is a particularly vivid and easy-to-see example, but sooner or later you'll hit it in any serious optimization effort.