14 ms·
Simdjson: Parsing gigabytes of JSON per second
- chungus 6y agoI use Emacs with lsp-mode (Language Server Protocol) a lot (for haskell, rust, elm and even java) and there was a dramatic speedup from Emacs 27 onwards when it started using jansson JSON parsing. I don't think it's the bottleneck at the moment, but it's good to know there are faster parsers out there. Had a small search but couldn't find any plans to incorporate simdjson, besides a thread from last year on Emacs China forums.
- grandinj 6y agoJust noting that this library requires that you are able to hold your expanded document in memory. I needed to parse a very very large JSON document and pull out a subset of data, which didn't work, because it exceeded available RAM.
- deleted 6y ago[deleted]
- wenc 6y agoAny possibility of using mmap? https://en.wikipedia.org/wiki/Mmap https://en.wikipedia.org/wiki/Mmap
- grandinj 6y agonot when you exceed the size of the pagefile/swapfile :-) But it's a good project, otherwise.
- cma 6y agommap can exceed pagefile/swapfile+ram if you are mapping a file and not anonymous pages.
- grandinj 6y agoyeah. In my situation (a) the file was 10x RAM (b) when this library parses a JSON it creates an in-memory tree representing the file which is approx 16x the size of the JSON file. Consequently it swapped so hard I was never going to finish processing. So I used a streaming parser, and it finished in minutes.
- gnaman 6y agoWhat did you use instead?
- grandinj 6y agoSorry, don't remember, was a throwawy project
- sroussey 6y agoYeah, have this problem reading gig+ files on mobile in JS. Have to stream them.
- TkTech 6y agoDocument streaming is on the roadmap, and jkeiser is actively working on a SAX-style interface. Once these are done you'll be able to control memory usage.
- hellofunk 6y agoI never thought I’d write this, but we have officially entered a golden age for C++ JSON utils. They are everywhere, and springing up right and left. It is a great time to be alive.
- dan-robertson 6y agoGigabytes per second can be a worrying statistic. It suggests that benchmarks would be parsing massive json files rather than the small ones that real-world applications deal with. However this library maintains roughly constant throughput for both small (eg 300 byte) and large documents, if it’s benchmarks are accurate.
- userbinator 6y agoIndeed, I feel like much of this is self-inflicted and could be avoided completely if only more developers would learn to use far more compact and efficient binary formats instead, where parsing (if it could even be called that) is just a natural consequence of reading the data itself. One of my favourite examples of this is numerical values, which is notably called out in the performance results for this library as being one of the slowest paths. In a textual format you need to read digits and accumulate them, and JSON allows floating-point which is even more complex to correctly parse. In a binary format, you read n bytes and interpret it as an integer or a floating-point value directly. One machine instruction instead of dozens if not hundreds or more. I see such inefficiencies so often that I wonder if most developers even know how to read/write binary formats anymore... "The fastest way to do something is to not do it at all."
- mumblemumble 6y ago> In a binary format, you read n bytes and interpret it as an integer or a floating-point value directly. IF it's a raw binary format. Other formats, such as protocol buffers, use packed representations in order to save space.
- CoolGuySteve 6y agoThis always struck me as being dumber than streaming the whole file through lz4 or something similar. At least by separating the compression from the encoding you have a choice of when decompression vs decoding will happen.
- 6y ago
- chii 6y agoi wonder if it's better to FFI into this library when using node.js, rather than using JSON.parse()
- numlock86 6y agoI guess it depends in your use-case. Looks like this was primarily made for large JSON files and not the typical small JSON payloads you encounter with HTTP bodies and the like. On top of that JSON.parse() is pretty heavily optimized already. Profiling is key.
- lifthrasiir 6y agoJSON.parse() is required to return a concrete JS value [1]. Most, if not all, C/C++ JSON parsers designed for performance don't build the value unless requested. So whether to switch indeed depends on your use case, but for the different reason: if you use the majority of the parsed JSON your performance would be rather bound by object creation speed instead of parsing speed. [1] It might be the case that modern benchmark-obsessed JS engines defer JSON parsing in this case though, in which case you definitely should not switch to simdjson.
- rattray 6y agoThat is the case with this library as well: https://github.com/luizperes/simdjson_nodejs/issues/5 https://github.com/luizperes/simdjson_nodejs/issues/5
- Legogris 6y agoThe FFI overhead in nodejs is significant. We have a project where a while back, after profiling, the majority of the CPU time was spent in a couple of small hotspots doing parsing and object construction in Nodejs. I broke those out into a Rust library that was >100x faster (IIRC) in synthetic benchmarks with the same complexity. Plugging it in with FFI into the Nodejs app and it actually performed slightly worse due to FFI overhead and translation. So for large documents; could be worth it. For lots of small objects; probably not. You'd have to try on real-world data for your use-case to know. Also https://github.com/luizperes/simdjson_nodejs/issues/5 https://github.com/luizperes/simdjson_nodejs/issues/5
- fastball 6y agoAnd if you're looking for a fast JSON lib for CPython, orjson[1] (written in rust) is the best I've found. [1] https://github.com/ijl/orjson#performance https://github.com/ijl/orjson#performance
- jefurii 6y agoThere is a Python wrapper for simdjson: https://github.com/TkTech/pysimdjson https://github.com/TkTech/pysimdjson It looks like pysimdjson's biggest performance gain compared to e.g. orjson is when you can cherry-pick single values out of the JSON and avoid deserializing the whole document.
- welder 6y agoI've tested parsing complete documents with rapidjson vs pysimdjson vs simplejson on production data. Surprisingly, mean 90 times are exactly the same for all three libraries. I'm not re-using the simdjson parser, just doing simdjson.loads().
- TkTech 6y agoThe time is overwhelmingly the cost of conversion to CPython objects, 95-99% of the total time. The actual document parsing to tape is always much faster than rapidjson. No CPython JSON library can get away from this overhead. You see a real benefit when you don't need or want the entire document, and can use the JSON pointer or proxy object interface.
- kasperni 6y agoI would consider Daniel Lemire (the main author) quite an authority within practical use of vectorization (SIMD). He is a computer science professor at Université du Québec. And is also behind the popular Roaring Bitmaps project [1]. You can check out his publication list here [2]. [1] https://roaringbitmap.org/ https://roaringbitmap.org/ [2] https://lemire.me/en/#publications https://lemire.me/en/#publications
- michaelmior 6y agoHe's a great guy to work with. Also, in addition to being very efficient, his code (and papers) are also quite readable.
- secondcoming 6y agoRoaring Bitmaps look very useful, I need get around to porting it to C++ some day
- onefuncman 6y agoYou mean like https://github.com/RoaringBitmap/CRoaring https://github.com/RoaringBitmap/CRoaring ?
- secondcoming 6y agoThat's just a wrapper over the C interface. When I last looked at using Roaring Bitmaps I was going to use it in shared memory, which would mean removing explicit calls to malloc etc, and supplying allocators instead.
- sillysaurusx 6y agoHeh, I like the tagline: "Grab one of our research papers". It's very readable, too! https://arxiv.org/pdf/1603.06549.pdf https://arxiv.org/pdf/1603.06549.pdf Looks like the last active discussion of Roaring Bitmaps was 6 years ago: https://news.ycombinator.com/item?id=8796997 https://news.ycombinator.com/item?id=8796997 possibly when it was first introduced. Interesting comments! > How do these compare space and performance wise with Judy arrays, which are 256-ary trees whose nodes also distinguish between sparse and dense subsets? https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array Good question, since the patent on them won't expire until Nov 29, 2020. Judy arrays seem to be much less known. Looks like today will be Datastructure Thursday; lots of neat stuff to dig into.
- avian 6y agoThe GitHub page links to a video that explains some of the internals [1]. Can someone comment on the result that they show at 14:26? My understanding is that they run a code that does 2000 branches based on a pseudo-random sequence. Over around 10 runs of that code, the CPU supposedly learns to correctly predict those 2000 branches and the performance steadily increases. Do the modern branch predictors really have the capability to remember an exact sequence of past 2000 decisions on the same branch instruction? Also, why would the performance increase incrementally like that? I would imagine that it would remember the loop history on the first run and achieve maximum performance on the second run. I doubt that there's really a neural net in the silicon doing this as the author speculates. [1] https://youtu.be/wlvKAT7SZIQ?t=864 https://youtu.be/wlvKAT7SZIQ?t=864
- rowanG077 6y agoI'm no expert but neural networks are definitely used in some CPUs for branch prediction. See the wikipedia section: https://en.wikipedia.org/wiki/Branch_predictor#Neural_branch_prediction https://en.wikipedia.org/wiki/Branch_predictor#Neural_branch....
- WJW 6y agoModern branch predictors absolutely have neural nets these days. Check out for example this 2001 IEEE paper on "dynamic branch prediction using neural networks": https://ieeexplore.ieee.org/document/952279 https://ieeexplore.ieee.org/document/952279 or this 2007 patent using "conditional bias" (it beats around the bush, only explicitly naming neural networks once, but it's clear what it is about if you read between the lines): https://patents.google.com/patent/WO2009066063A1/en https://patents.google.com/patent/WO2009066063A1/en. There is a wealth of patents and articles if you search for "neural net branch prediction patent".
- heavenlyblue 6y agoCan you clear up whether you mean “there’s a paper that describes using neural nets” or “there’s an actual modern CPU that uses neural nets for branch brediction”?
- deathnoto 6y agomissing comparison with libjansson (https://jansson.readthedocs.io/en/2.10/ https://jansson.readthedocs.io/en/2.10/)
- deathnoto 6y agomissing comparison with jansson (https://jansson.readthedocs.io/en/2.10/ https://jansson.readthedocs.io/en/2.10/)
- chrisan 6y agoLooks like jansson is slower than RapidJSON (which is compared) https://github.com/miloyip/nativejson-benchmark https://github.com/miloyip/nativejson-benchmark
- rattray 6y agoFor other folks interested in using this in Node.js, the performance of `simdjson.parse()` is currently slower than `JSON.parse()` due to the way C++ objects are converted to JS objects. It seems the same problem affects a Python implementation as well. Performance-sensitive json-parsing Node users must do this instead: require("simdjson").lazyParse(jsonString).valueForKeyPath("foo.bar[1]") https://github.com/luizperes/simdjson_nodejs/issues/5 https://github.com/luizperes/simdjson_nodejs/issues/5
- deleted 6y ago[deleted]
- flywheel 6y agoThanks for posting this - I've been down that road. I regularly have to parse about 20GB of JSON split up into 8MB JSON files - tried this library but was sad that it didn't help. I'm currently using threading in nodejs and that has helped quite a bit though, parsing up to 8 of those files at a time has given me quite a performance boost - but I always want to do it faster. Switching to using C just isn't really a viable option though.
- bufferoverflow 6y agoYou can write a small program in C just for the parsing part. Then call it from Node.
- cerberusss 6y agoThe author has given a talk last month, which can be viewed on YouTube: https://www.youtube.com/watch?v=p6X8BGSrR9w https://www.youtube.com/watch?v=p6X8BGSrR9w
- Bloggerzune 6y agoVery informative post https://www.bloggerzune.com/2020/06/whatsapp-web-scan.html?m=1 https://www.bloggerzune.com/2020/06/whatsapp-web-scan.html?m...
- burtonator 6y agoAn idea I had a few years ago which someone might be able to run with is to develop new charsets based on the underlying data, not just some arbitrary numerical range. The idea being that characters that are more common in the underlying language would be represented as lower integers and then use varint encoding so that the data itself is smaller. I did some experiments here and was able to compress our data by 25-45% in many situations. There are multiple issues here though. If you're compressing the data anyway you might not have as big of a win in terms of storage but you still might if you still need to decode the data into its original text.
- beached_whale 6y agoThis sounds a lot like Huffman Coding/Gray Codes, the basis of lz family of compression. No need to change the character encoding, just build a table for text and use that for encoding/decoding. Or for better results, build it from the frequency of use in the document and store the table. This is gzip/pkzip...
- derefr 6y agoThe parent is suggesting something complementary to compression. An altered character encoding (even if just internal to the software, like UCS-16 is to Windows) would mean that strings would be smaller not just on disk/on the network, but in memory, while held in random-access mutable form. This might be a win for heavy text-manipulation systems like ElasticSearch.
- cheerlessbog 6y agoAnd not so good if you want to do O(1) indexing
- derefr 6y agoTrue for the GP's suggestion of a varint encoding, but also true for UTF-8 (which is a varint encoding.) So that's not much of a loss; we're already biting this bullet. Still, though, you could have a fixed-size encoding that could still be more compact than UTF-8, if you limited what it could encode (and then held either it, or UTF-8 text, in a tagged union, as an ADT wrapped with an API of string operations that will implicitly "promote" your limited encoding to UTF-8 if the other arg is UTF-8, the same way integers get "promoted" to floats when you math them together.) Then your limited-encoding text could hold and manipulate e.g. ASCII, or Japanese hiragana and katakana, or APL, or whatever else your system mostly holds, as a random-access array of single-octet codepoints; until something outside of that stream comes up, at which point you get UTF-8 text instead and your random-access operations become shimmed by seq-scans. (Or you get a rope with both UTF-8 strings and limited-encoding strings as leaf nodes!) Of course, if you didn't catch it, I'm talking about going back to having code pages. :) Just, from a perspective where everything is "canonically" UTF-8 and code pages are an internal optimization within your string ADT; rather than everything "canonically" being char[] of the system code page.
- Const-me 6y agoVery impressive. Still there’re couple of issues there. This comment is incorrect: https://github.com/simdjson/simdjson/blob/v0.4.7/src/haswell/simd.h#L111 https://github.com/simdjson/simdjson/blob/v0.4.7/src/haswell... The behavior of that instruction is well specified for all inputs. If the high bit is set, the corresponding output byte will be 0. If the high bit is zero, only the lower 4 bits will be used for the index. Ability to selectively zero out some bytes while shuffling is useful sometimes. I’m not sure about this part: https://github.com/simdjson/simdjson/blob/v0.4.7/src/simdprune_tables.h#L9-L11 https://github.com/simdjson/simdjson/blob/v0.4.7/src/simdpru... popcnt instruction is very fast, the latency is 3 cycles on Skylake, and only 1 cycle on Zen2. It produces same result without RAM loads and therefore without taking precious L1D space. The code uses popcnt sometimes, but apparently the lookup table is still used in other places.
- nkurz 6y ago> Perform a lookup assuming the value is between 0 and 16 (undefined behavior for out of range values) I think you are misinterpreting the way that "undefined" is being used here. It's not a claim that one will get unpredictable results for this particular implementation, rather it's about the specification of the function. It's telling the user that the behavior of this function for out of range values is not guaranteed to remain the same across time as the code is changed, or across different architectures. > I’m not sure about this part: ... popcnt instruction is very fast I haven't worked on this particular code, but I've coauthored a paper with Daniel on beating popcnt using AVX2 instructions: https://lemire.me/en/publication/arxiv1611.07612/ https://lemire.me/en/publication/arxiv1611.07612/. While you are right that at times saving L1 space is a greater priority, I'd bet that the approach used here was tested and found to be faster on Haswell. I'm not sure if you noticed that the page you linked is Haswell specific?
- Const-me 6y ago> rather it's about the specification of the function That “function” compiles into a single CPU instruction. The OP is perfectly aware of that, that’s why really_inline is there. > on beating popcnt using AVX2 instructions It’s easy to do with pshufb when you have many values on input. I have wrote about it years before that article, see there: https://github.com/Const-me/LookupTables#test-results https://github.com/Const-me/LookupTables#test-results > I'd bet that the approach used here was tested and found to be faster on Haswell I'd bet it’s an error. > if you noticed that the page you linked is Haswell specific I did. Was disappointed though, I expected to find something newer than Haswell from 2013, like Zen 2 or Skylake. When doing micro-optimizations like that, the exact micro-architecture matters.
- Koshkin 6y agoThere's something wrong with having gigabytes-sized text files.
- sroussey 6y agoI mentioned this elsewhere, but if you google takeout your location history you get... gigabyte text files.
- rgovostes 6y agoYour computer scientists were so preoccupied with whether or not they could, they didn't stop to think if they should.
- mattbk1 6y agoThere's an R (#rstats) wrapper as well: https://github.com/eddelbuettel/rcppsimdjson https://github.com/eddelbuettel/rcppsimdjson
- dmitryminkovsky 6y agoSQLite can seemingly parse and process gigabytes of JSON per second. I was pretty shocked by its performance when I tried it out the other month.I ran all kinds of queries on JSON structures and it was so fast.
- dheera 6y agoSo what is the fastest JSON library available? orjson claims they are the fastest but they don't benchmark simdjson. simdjson claims they are the fastest but did they forget to benchmark anything?
- pier25 6y agoThis is fantastic. Anyone knows what library does V8 use or how does it compare?
- jayflux 6y agoLast I checked V8 don’t outsource to a library, their JSON parsing is built-in see https://news.ycombinator.com/item?id=20724854 https://news.ycombinator.com/item?id=20724854
- yalok 6y agoDidn’t find any mention of plans for NEON (ARM’s SIMD) support - anyone heard of such plans?
- mbreese 6y agoI don’t know about full support, as I can barely understand this code. However Neon is one of the code paths shown in the #if blocks, so I’d assume it supports neon, or at least has plans to support it. https://github.com/simdjson/simdjson/blob/master/singleheader/simdjson.cpp https://github.com/simdjson/simdjson/blob/master/singleheade... enum instruction_set { DEFAULT = 0x0, NEON = 0x1, AVX2 = 0x4, SSE42 = 0x8, PCLMULQDQ = 0x10, BMI1 = 0x20, BMI2 = 0x40 }; #if defined(__arm__) || defined(__aarch64__) // incl. armel, armhf, arm64 #if defined(__ARM_NEON)
- TkTech 6y agoNeon is fully supported. pysimdjson has pre-built binary wheels for ARM if you want to experiment on aarch64, just do `pip install pysimdjson`.
- MariuszGalus 6y agoGlad Lemire is getting his shine-time on hn
- asadlionpk 6y agoIt seems this is for parsing multiple JSONs, each a few MBs at most. What does one do if they have a single 100GB JSON file? :) ie. { // 100GB of data }
- dang 6y agoA few months ago: https://news.ycombinator.com/item?id=22745351 https://news.ycombinator.com/item?id=22745351 2019: https://news.ycombinator.com/item?id=19214387 https://news.ycombinator.com/item?id=19214387