20 ms·
Building a high performance JSON parser
- denysvitali 3y agoAlso interesting: https://youtu.be/a7VBbbcmxyQ https://youtu.be/a7VBbbcmxyQ
- eatonphil 3y agoThe walkthrough is very nice, how to do this if you're going to do it. If you're going for pure performance in a production environment you might take a look at Daniel Lemire's work: https://github.com/simdjson/simdjson https://github.com/simdjson/simdjson. Or the MinIO port of it to Go: https://github.com/minio/simdjson-go https://github.com/minio/simdjson-go.
- vjerancrnjak 3y agoIf your JSON always looks the same you can also do better than general JSON parsers.
- lylejantzi3rd 3y agoAndreas Fredriksson demonstrates exactly that in this video: https://vimeo.com/644068002 https://vimeo.com/644068002
- diarrhea 3y agoI wonder: can fast, special-case JSON parsers be dynamically autogenerated from JSON Schemas? Perhaps some macro-ridden Rust monstrosity that spits out specialised parsers at compile time, dynamically…
- minhazm 3y agoFor json schema specifically there are some tools like go-jsonschema[1] but I've never used them personally. But you can use something like ffjson[2] in go to generate a static serialize/deserialize function based on a struct definition. [1] https://github.com/omissis/go-jsonschema https://github.com/omissis/go-jsonschema [2] https://github.com/pquerna/ffjson https://github.com/pquerna/ffjson
- atombender 3y agoHey, go-jsonschema is my project. (Someone else just took over maintaining it, though.) It still relies on the standard Go parser; all it does it generate structs with the right types and tags.
- galangalalgol 3y agoDoesn't the serde crate's json support do precisely this? It generates structs that have optional in all the right places and with all the right types anyway. Seems like the llvm optimiser can probably do something useful with that even if the serde feature isn't using apriori knowledge out of the schema.
- dleeftink 3y agoSomewhat tangentially related, Fabian Iwand posted this regex prefix tree visualiser/generator last week [0], which may offer some inspiration for prototyping auto generated schemas.
- atombender 3y agoYou forgot to include the link?
- 3y ago
- loeg 3y agoYou might also move to something other than JSON if parsing it is a significant part of your workload.
- haswell 3y agoMost of the times I’ve had to deal with JSON performance issues, it involved a 3rd party API and JSON was the only option. If you’re building something net-new and know you’ll have these problems out the gate, something other than JSON might be feasible, but the moment some other system not in the closed loop needs to work with the data, you’re back to JSON and any associated perf issues.
- fooster 3y agoLast time I compared the performance of various json parsers the simd one turned out to be disappointingly slow.
- Thaxll 3y agoThe fastest json lib in Go is the one done by the company behind Tiktok.
- ken47 3y agoFastest at what?
- cannonpalms 3y ago> For all sizes of json and all scenarios of usage, Sonic performs best. The repository has benchmarks
- mananaysiempre 3y agoI’m not seeing simdjson in them though? I must be missing something because the Go port of it is explicitly mentioned in the motivation[1] (not the real thing, though). [1] https://github.com/bytedance/sonic/blob/main/docs/INTRODUCTION.md https://github.com/bytedance/sonic/blob/main/docs/INTRODUCTI...
- rockinghigh 3y agohttps://github.com/bytedance/sonic https://github.com/bytedance/sonic
- pizzafeelsright 3y agoExcellent treat vector.
- pizzafeelsright 3y agoExcellent treat vector.
- lionkor 3y agosimdjson has not been the fastest for a long long time
- jzwinck 3y agoWhat is faster? According to https://github.com/kostya/benchmarks#json https://github.com/kostya/benchmarks#json nothing is.
- rexfuzzle 3y agoGreat to see a shout out to Phil Pearl! Also worth looking at https://github.com/bytedance/sonic https://github.com/bytedance/sonic
- Galanwe 3y ago[flagged]
- bsdnoob 3y agoDid you even open the article? Following is literally in first paragraph > This package offers the same high level json.Decoder API but higher throughput and reduced allocations
- jcelerier 3y agoHow does that contradict what the parent poster says? I think it's very weird to call something "high performance" when it looks like it's maybe 15-20% of the performance of a simdjson in c++. This is not "going from normal performance to high performance", this going from "very subpar" to "subpar"
- willsmith72 3y agoOk but how many teams are building web APIs in C++?
- TheCleric 3y agoI worked with a guy who did this. It was fast, but boy howdy was it not simple.
- lolinder 3y agoPar is different for different stacks. It's reasonable for someone to treat their standard library's JSON parser as "par", given that that's the parser that most of their peers will be using, even if there are faster options that are commonly used in other stacks.
- Thaxll 3y agoBecause even in C++ people don't use json simd most project use rapidjson which Go is on part with.
- 3y ago
- kevingadd 3y agoI'm surprised there's no way to say 'I really mean it, inline this function' for the stuff that didn't inline because it was too big. The baseline whitespace count/search operation seems like it would be MUCH faster if you vectorized it with SIMD, but I can understand that being out of scope for the author.
- mgaunard 3y agoOf course you can force-inline.
- cbarrick 3y agoObviously you can manually inline functions. That's what happened in the article. The comment is about having a directive or annotation to make the compiler inline the function for you, which Go does not have. IMO, the pre-inline code was cleaner to me. It's a shame that the compiler could not optimize it. There was once a proposal for this, but it's really against Go's design as a language. https://github.com/golang/go/issues/21536 https://github.com/golang/go/issues/21536
- peterohler 3y agoYou might want to take a look at https://github.com/ohler55/ojg https://github.com/ohler55/ojg. It takes a different approach with a single pass parser. There are some performance benchmarks included on the README.md landing page.
- arun-mani-j 3y agoI remember reading a SO question which asks for a C library to parse JSON. A comment was like - C developers won't use a library for JSON, they will write one themselves. I don't know how "true" that comment is but I thought I should try to write a parser myself to get a feel :D So I wrote one, in Python - https://arunmani.in/articles/silly-json-parser/ https://arunmani.in/articles/silly-json-parser/ It was a delightful experience though, writing and testing to break your own code with different variety of inputs. :)
- xoac 3y agoGood for you but what does this have to do with the article?
- janmo 3y agoI wrote a small JSON parser in C myself which I called jsoncut. It just cuts out a certain part of a json file. I deal with large JSON files, but want only to extract and parse certain parts of it. All libraries I tried parse everything, use a lot of RAM and are slow. Link here, if interested to have a look: https://github.com/rgex/jsoncut https://github.com/rgex/jsoncut
- vlovich123 3y agoThe words you’re looking for are SAX-like JSON parser or streaming json parser. I don’t know if there’s any command line tools like the one you wrote that use it though to provide a jq-like interface.
- janmo 3y agoI tried JQ and other command line tools, all were extremely slow and seemed to always parse the entire file. My parser just reads the file byte by byte until it finds the target, then outputs the content. When that's done it stops reading the file, meaning that it can be extremely fast when the targeted information is at the beginning of the JSON file.
- 3y ago
- visarga 3y agonowadays I am more interested in a "forgiving" JSON/YAML parser, that would recover from LLM errors, is there such a thing?
- kevingadd 3y agoIf the LLM did such a bad job that the syntax is wrong, do you really trust the data inside? Forgiving parsers/lexers are common in language compilers for languages like rust or C# or typescript, you may want to investigate typescript in particular since it's applicable to JSON syntax. Maybe you could repurpose their parser.
- RichieAHB 3y agoI feel like trying to infer valid JSON from invalid JSON is a recipe for garbage. You’d probably be better off doing a second pass with the “JSON” through the LLM but, as the sibling commenter said, at this point even the good JSON may be garbage …
- _dain_ 3y agohalloween was last week
- explaininjs 3y agoPerhaps not quite what you're asking for, but along the same lines there's this "Incomplete JSON" parser, which takes a string of JSON as it's coming out of an LLM and parses it into as much data as it can get. Useful for building streaming UI's, for instance it is used on https://rexipie.com https://rexipie.com quite extensively. https://gist.github.com/JacksonKearl/6778c02bf85495d1e39291c0f7b9ea9c https://gist.github.com/JacksonKearl/6778c02bf85495d1e39291c... Some example test cases: { input: '[{"a": 0, "b":', output: [{ a: 0 }] }, { input: '[{"a": 0, "b": 1', output: [{ a: 0, b: 1 }] }, { input: "[{},", output: [{}] }, { input: "[{},1", output: [{}, 1] }, { input: '[{},"', output: [{}, ""] }, { input: '[{},"abc', output: [{}, "abc"] }, Work could be done to optimize it, for instance add streaming support. But the cycles consumed either way is minimal for LLM-output-length=constrained JSON. Fun fact: as best I can tell, GPT-4 is entirely unable to synthesize code to accomplish this task. Perhaps that will change as this implementation is made public, I do not know.
- mannyv 3y agoThese are always interesting to read because you get to see runtime quirks. I'm surprised there was so much function call overhead, for example. And it's interesting you can bypass range checkong. The most important thing, though, is the process: measure then optimize.
- deleted 3y ago[deleted]
- isuckatcoding 3y agoThis is fantastically useful. Funny enough I stumbled upon your article just yesterday through google search.
- mgaunard 3y ago"It’s unrealistic to expect to have the entire input in memory" -- wrong for most applications
- isuckatcoding 3y agoYes but for applications where you need to do ETL style transformations on large datasets, streaming is an immensely useful strategy. Sure you could argue go isn’t the right tool for the job but I don’t see why it can’t be done with the right optimizations like this effort.
- dh2022 3y agoIf performance is important why would you keep large datasets in JSON format?
- querulous 3y agosometimes it's not your data
- isuckatcoding 3y agoUsually because the downstream service or store needs it
- Maxion 3y agoBecause you work at or for some bureaucratic MegaCorp, that does weird things with no real logic behind it other than clueless Dilbert managers making decisions based on LinkedIn blogs. Alternatively desperate IT consultants trying to get something to work with too low of a budget and/or no access to do things the right way. Be glad you have JSON to parse, and not EDI, some custom deliminated data format (with no or old documentation) - or shudders you work in the airline industry with SABRE.
- capableweb 3y agohttps://yourdatafitsinram.net/ https://yourdatafitsinram.net/
- jensneuse 3y agoI've taken a very similar approach and built a GraphQL tokenizer and parser (amongst many other things) that's also zero memory allocations and quite fast. In case you'd like to check out the code: https://github.com/wundergraph/graphql-go-tools https://github.com/wundergraph/graphql-go-tools
- markl42 3y agoHow big of an issue is this for GQL servers where all queries are known ahead of time (allowlist) - i.e. you can cache/memorize the ast parsing and this is only a perf issue for a few minutes after the container starts up Or does this bite us in other ways too?
- jensneuse 3y agoI build GraphQL API gateways / Routers for 5+ years now. It would be nice if trusted Documents or persisted operations were the default, but the reality is that a lot of people want to open up their GraphQL to the public. For that reason we've build a fast parser, validator, normalizer and many other things to support these use cases.
- romshark 3y agoYou might also want to check out this abomination of mine: https://github.com/graph-guard/gqlscan https://github.com/graph-guard/gqlscan I've held a talk about this, unfortunately wasn't recorded. I've tried to squeeze as much out of Go as I could and I've went crazy doing that :D
- jensneuse 3y agoIt's a bit verbose.
- nwpierce 3y agoWriting a json parser is definitely an educational experience. I wrote one this summer for my own purposes that is decently fast: https://github.com/nwpierce/jsb https://github.com/nwpierce/jsb
- lamontcg 3y agoWish I wasn't 4 or 5 uncompleted projects deep right now and had the time to rewrite a monkey parser using all these tricks.
- jchw 3y agoLooks pretty good! Even though I've written far too many JSON parsers already in my career, it's really nice to have a reference for how to think about making a reasonable, fast JSON parser, going through each step individually. That said, I will say one thing: you don't really need to have an explicit tokenizer for JSON. You can get rid of the concept of tokens and integrate parsing and tokenization entirely. This is what I usually do since it makes everything simpler. This is a lot harder to do with something like the rest of ECMAscript since in something like ECMAscript you wind up needing look-ahead (sometimes arbitrarily large look-ahead... consider arrow functions: it's mostly a subset of the grammar of a parenthesized expression. Comma is an operator, and for default values, equal is an operator. It isn't until the => does or does not appear that you know for sure!)
- coldtea 3y agoWhat line of work are you in that you've "written far too many JSON parsers already" in your career?!!!
- craigching 3y agoProbably anywhere that requires parsing large JSON documents. Off the shelf JSON parsers are notoriously slow on large JSON documents.
- ahoka 3y agoNot necessarily, for example Newtonsoft is fine with multiple hundreds of megabyes if you use it correctly. But of course depends on how large we are talking about.
- beached_whale 3y agoThere are several that are into the GB/s of performance with various interfaces. Most are just trash for large documents and sit in the allocators far too long, but that's not required either
- zlg_codes 3y ago
- evmar 3y agoIn n2[1] I needed a fast tokenizer and had the same "garbage factory" problem, which is basically that there's a set of constant tokens (like json.Delim in this post) and then strings which cause allocations. I came up with what I think is a kind of neat solution, which is that the tokenizer is generic over some T and takes a function from byteslice to T and uses T in place of the strings. This way, when the caller has some more efficient representation available (like one that allocates less) it can provide one, but I can still unit test the tokenizer with the identity function for convenience. In a sense this is like fusing the tokenizer with the parser at build time, but the generic allows layering the tokenizer such that it doesn't know about the parser's representation. [1] https://github.com/evmar/n2 https://github.com/evmar/n2
- suzzer99 3y agoCan someone explain to me why JSON can't have comments or trailing commas? I really hope the performance gains are worth it, because I've lost 100s of man-hours to those things, and had to resort to stuff like this in package.json: "IMPORTANT: do not run the scripts below this line, they are for CICD only": true,
- coldtea 3y agoIt can't have comments because it didn't originally had comments, so now it's too late. And it originally didn't have comments, because Douglas Cockford thought they could be abused for parsing instructions. As for not having trailing commas, it's probably a less intentional bad design choice. That said, if you want commas and comments, and control the parsers that will be used for your JSON, then use JSONC (JSON with comments). VSCode for example does that for its JSON configuration.
- explaininjs 3y agoJSONC also supports trailing commas. It is, in effect, "JSON with no downsides". TOML/Yaml always drive me batty with all their obscure special syntax. Whereas it's almost impossible to look at a formatted blob of JSON and not have a very solid understanding of what it represents. The one thing I might add is multiline strings with `'s, but even that is probably more trouble than it's worth, as you immediately start going down the path of "well let's also have syntax to strip the indentation from those strings, maybe we should add new syntax to support raw strings, ..."
- tubthumper8 3y agoDoes JSONC have a specification or formal definition? People have suggested[1] using JSON5[2] instead for that reason [1] https://github.com/microsoft/vscode/issues/100688 https://github.com/microsoft/vscode/issues/100688 [2] https://spec.json5.org/ https://spec.json5.org/
- mananaysiempre 3y agoUnfortunately, JSON5 says keys can be ES5 IdentifierName[1]s, which means you must carry around Unicode tables. This makes it a non-option for small devices, for example. (I mean, not really, you technically could fit the necessary data and code in low single-digit kilobytes, but it feels stupid that you have to. Or you could just not do that but then it’s no longer JSON5 and what was the point of having a spec again?) [1] https://es5.github.io/x7.html#x7.6 https://es5.github.io/x7.html#x7.6
- forrestthewoods 3y ago> Any (useful) JSON decoder code cannot go faster that this. That line feels like a troll. Cunningham’s Law in action. You can definitely go faster than 2 Gb/sec. In a word, SIMD.
- shoo 3y agowe could re-frame by distinguishing problem statements from implementations Problem A: read a stream of bytes, parse it as JSON Problem B: read a stream of bytes, count how many bytes match a JSON whitespace character Problem B should require fewer resources* to solve than problem A. So in that sense problem B is a relaxation of problem A, and a highly efficient implementation of problem B should be able to process bytes much more efficiently than an "optimal" implementation of problem A. So in this sense, we can probably all agree with the author that counting whitespace bytes is an easier problem than the full parsing problem. We're agreed that the author's implementation (half a page of go code that fits on a talk slide) to solve problem B isn't the most efficient way to solve problem B. I remember reading somewhere the advice that to set a really solid target for benchmarking, you should avoid measuring the performance of implementations and instead try to estimate a theoretical upper bound on performance, based on say a simplified model of how the hardware works and a simplification of the problem -- that hopefully still captures the essence of what the bottleneck is. Then you can compare any implementation to that (unreachable) theoretical upper bound, to get more of an idea of how much performance is still left on the table. * for reasonably boring choices of target platform, e.g. amd64 + ram, not some hypothetical hardware platform with surprisingly fast dedicated support for JSON parsing and bad support for anything else.
- forrestthewoods 3y agoEverything you said is totally reasonable. I'm a big fan of napkin math and theoretical upper bounds on performance. simdjson (https://github.com/simdjson/simdjson https://github.com/simdjson/simdjson) claims to fully parse JSON on the order of 3 GB/sec. Which is faster than OP's Go whitespace parsing! These tests are running on different hardware so it's not apples-to-apples. The phrase "cannot go faster than this" is just begging for a "well ackshully". Which I hate to do. But the fact that there is an existence proof of Problem A running faster in C++ SIMD than OP's Probably B scalar Go is quite interesting and worth calling out imho. But I admit it doesn't change the rest of the post.
- ncruces 3y agoIt's possible to improve over the standard library with better API design, but it's not really possible to do a fully streaming parser that doesn't half fill structures before finding an error and bailing out in the middle, which is another explicit design constraint for the standard library.
- hintymad 3y agoHow is this compared to Daniel Lemire's simdjson? https://github.com/simdjson/simdjson https://github.com/simdjson/simdjson
- 1vuio0pswjnm7 3y ago"But there is a better trick that we can use that is more space efficient than this table, and is sometimes called a computed goto." From 1989: https://raw.githubusercontent.com/spitbol/x32/master/docs/spitbol-manual-v3.7.pdf https://raw.githubusercontent.com/spitbol/x32/master/docs/sp... "Indirection in the Goto field is a more powerful version of the computed Goto which appears in some languages. It allows a program to quickly perform a multi-way control branch based on an item of data."
- wood_spirit 3y agoMy own lessons from writing fast json parsers has a lot of language-type things but here are some generalisations: Avoid heap allocations in tokenising. Have a tokeniser that is a function that returns a stack-allocated struct or an int64 token that is a packed field describing the start, length and type offsets etc of the token. Avoid heap allocations in parsing: support a getString(key String) type interface for clients that what to chop up a buffer. For deserialising to object where you know the fields at compile time, generally generate a switch case of key length before comparing string values. My experience in data pipelines that process lots of json is that choice of json library can be a 3-10x performance difference and that all the main parsers want to allocate objects. If the classes you are serialising or deserialising is known at compile time then Jackson Java does a good job but you can get a 2x boost with careful coding and profiling. Whereas if you are paying aribrary json then all the mainstream parsers want to do lots of allocations that a more intrusive parser that you write yourself can avoid, and that you can make massive performance wins if you are processing thousands or millions of objects per second.
- wslh 3y agoI remember this JSON benchmark page from RapidJSON [1]. [1] https://rapidjson.org/md_doc_performance.html https://rapidjson.org/md_doc_performance.html
- crabbone 3y agoMaybe I overlooked something, but the author keeps repeating that they wrote a "streaming" parser, but never explained what that actually means. In particular, they never explained how did they deal with repeating keys in "hash tables". What does their parser do? Calls the "sink" code twice with the repeated key? Waits until the entire "hash table" is red and then calls the "sink" code? In my mind, JSON is inherently inadequate for streaming because of hierarchical structure, no length know upfront and most importantly, repeating keys. You could probably make a subset of JSON more streaming-friendly, but at this point, why bother? I mean, if the solution is to modify JSON, then a better solution would be something that's not JSON at all.
- cratermoon 3y agoMy favorite bit about this is his reference to John Ousterhout, Define errors out of existence. youtu.be/bmSAYlu0NcY?si=WjC1ouEN1ad2OWjp&t=1312 Note the distinct lack of: if err != nil {
- romshark 3y agoI've recently held a talk (https://youtu.be/a7VBbbcmxyQ?si=0fGVxfc4qmKMVCXk https://youtu.be/a7VBbbcmxyQ?si=0fGVxfc4qmKMVCXk) about github.com/romshark/jscan that I've been working on. It's a performance-oriented JSON iterator / tokenizer you might want to take a look at if interested in high performance zero allocation JSON parsing in Go.
- hknmtt 3y agowhat does this bring over goccy's json encoder?
- EdwardDiego 3y agoA person who helped me out a lot when I was learning to code wrote his own .NET JSON library because the MS provided one had a rough API and was quite slow. His lib became the defacto JSON lib in .NET dev and naturally, MS head-hunted him. Fast JSON is that important these days.
- flaie 3y agoThis was a very good read, and I did learn some nice tricks, thank you very much.
- rurban 3y agoThis is a very poor and overly simplified text to write basic JSON parsers, not touching any topic of writing actually fast JSON parsers. Such as not-copying tokenizers (e.g. jsmn), word-wise tokenizers (simdjson) and fast numeric conversions (fast_double_parser at al).
- thomasvn 3y agoIn what cases would an application need to regularly parse gigabytes of JSON? Wouldn't it be advantageous for the app to get that data into a DB?
- mleonhard 3y agoI wrote a Rust library that works similarly to the author's byteReader: https://crates.io/crates/fixed-buffer https://crates.io/crates/fixed-buffer
- mikhailfranco 3y agoI notice 'sample.json' contains quite a few escaped nulls \u0000 inside quoted strings. Is "\u0000" legal JSON? P.S. ... and many other control characters < \u0020