This is very cool. Meanwhile, in the xi-editor project, we're struggling with the fact that Swift JSON parsing is very slow. My benchmarking clocked in at 0.00089GB/s for Swift 4, and things don't seem to have improved much with Swift 5. I'm encouraging people on that issue to do a blog post.
I wrote my own Swift JSON parser quite a while ago, https://github.com/postmates/PMJSON. In my limited benchmarking it parses slower than Foundation's JSONSerialization (by a factor of 2–2.5 IIRC) but encodes faster, and my impression was most of the time was spent constructing Dictionaries, but I didn't do too much performance work on it. It might be interesting to have someone else take a crack at improving the performance.
That said, it also includes an event-based parser (called JSONDecoder), so if you want to handle events in order to decode into your own data structure and skip the intermediate JSON data structure, you might be able to get faster than JSONSerialization that way.
Why does Xi use JSON in the first place? It would be easier and faster to use a binary format, e.g. Protobufs, Flatbuffers or if the semantics of JSON is needed: CBOR.
> JSON. The protocol for front-end / back-end communication, as well as between the back-end and plug-ins, is based on simple JSON messages. I considered binary formats, but the actual improvement in performance would be completely in the noise. Using JSON considerably lowers friction for developing plug-ins, as it’s available out of the box for most modern languages, and there are plenty of the libraries available for the other ones.
We actually do get 60fps, but JSON parsing on the Swift side takes more than its share of total CPU load, affecting power consumption among other things. So (partly to address the trolls elsewhere in the thread), the choice of JSON does not preclude fast implementation (as the existence of simdjson proves), but it does make it dependent on the language having a performant JSON implementation. I made the assumption that this would be the case, and for Swift it isn't.
At some point though, isn't it maybe easier just to use an inherently more efficient format than trying to rely on clever implementations to save you?
I totally get json for public internet services where you want to have lots of consumers and using a more efficient format would be significant friction, but writing an editor frontend is a very large endeavor -- it seems like the extra work of adopting something more efficient than json (like flatbuffers or whatever) would really be in the noise.
One of the other performant libraries in the comparison section of simdjson has a Swift wrapper: https://github.com/chadaustin/sajson. Haven't tried it, but one option would be to bring that up to date. Another option, now that Swift 5 strings use utf8 as a native encoding, it may be possible to write a fast Json parser in native Swift. Likely someone already has or is doing that.
Given equally-high quality JSON and binary serdes, JSON is sufficiently fast. Raphlinus is saying that Swift's built-in deserialiser is obnoxiously slow.
Xi has multiple components written in multiple languages. In the rust core, json de/serialization is not a problem, but swift is lacking a similar high-performance library.
I'm going off topic at this point but I'd think for a native app the main advantages of a binary format would be the static typing and code generation that come from using an IDL.
I'm familiar with serde. It's an incredible project, but I wouldn't quite call it "static typing for JSON". You still have to unwrap the parse at some point. However, I will concede the point that if you have Rust on both sides then you'll get most of the benefits.
Because JSON encoding/decoding was not found to be a typical performance bottleneck, and because JSON is supported in virtually every programming language (Xi allows you to write frontends in pretty much any language you want).
After spending most of a year doing deep surgery on systems that used CBOR extensively, I can report that the common CBOR parsers are not faster than common JSON parsers; surprisingly, they are actually slower. CBOR is also not easier; it's much less widely supported, and you need a separate debugging representation. It does have three real advantages over JSON: it supports binary strings, it's a monument to Carsten Bormann's ego, and data encoded in CBOR takes slightly fewer bytes than the same data encoded in JSON. (The second is only an advantage if you're Carsten Bormann.)
1) there's a distinction between integers and floating point values;
2) you can semantically tag values (yes, this is a text string, but treat it as a date; this is a binary string, but treat it as a big number; etc.);
3) you can have maps with non-text keys.
I'm not sure what Carsten Bormann's ego has to do with CBOR, but I found RFC-7049 one of the better written specs, with plenty of encoding examples. It made it real easy to write a encoder/decoder [1] and use the examples as test cases.
All three of those could be advantages under some circumstances, but I've more often found them to be disadvantages. What do you do with maps with non-text keys when you're deserializing in JS or Perl? For that matter, what do you do in Python when the key of a map is a map? When you have a date, do you decode it as a datetime object, as a text string, or as some kind of wrapper object that gives you both alternatives?
I agree that having lots of examples in the spec is good.
> What do you do with maps with non-text keys when you're deserializing in JS or Perl?
Um, use another language? I use Lua, which can deal with non-text keys. As for decoding dates (if they're semantically tagged, which you can with CBOR) I convert it to a datetime object, on the grounds that if I care about tagged dates, I'm going to be using them in some capacity.
But that's not to say you have to use the flexibility of CBOR. But for me, having distinct integer and floating point values, plus distinct text and binary data, is enough of a win to use it over JSON.
While theoretically true, in practice the actual character parsing tends to a small to negligible part of the overall time. Which leads to the measurable fact that on macOS/iOS, the JSON serialization stuff is actually one of their fastest, faster than their binary stuff.
I ran one of the Codable benchmarks in instruments, and here's what the top functions were:
19.98 s swift_getGenericMetadata
19.15 s newJSONString
16.17 s objc_msgSend
15.33 s _swift_release_(swift::HeapObject*)
14.45 s tiny_malloc_should_clear
12.81 s _swift_retain_(swift::HeapObject*)
11.28 s searchInConformanceCache(swift::TargetMetadata<swift::InProcess> const*, swift::TargetProtocolDescriptor<swift::InProcess> const*)
10.46 s swift_dynamicCastImpl(swift::OpaqueValue*, swift::OpaqueValue*, swift::TargetMetadata<swift::InProcess> const*, swift::TargetMetadata<swift::InProcess> const*, swift::DynamicCastFlags)
So it looks like a lot of the time is going into memory management or the Swift runtime performing type checking.
Yeah, I've done some analysis, it's creating a ton of objects to conform to the Codable protocol, and a lot of those objects are for codingPath, which is updated for basically every node in the tree. It's not a mystery, we just don't know the best way to fix it.
Is there a reason you need to use Codable? Sorry if this sounds uninformed, I haven't taken that much time to look at what you're doing exactly (I just ran https://github.com/jeremywiebe/json-performance).
That's one of the things we're considering. But it is by far the most idiomatic way to do things in Swift. One of the alternatives we're considering is implementing the line cache (including the update protocol) in Rust, which would be a huge performance jump.
No, I don’t think the project needs to use Codable. The point of that benchmark was to evaluate Codable’s performance under Swift 5. It was posed that performance was much improved. The benchmark points out that it has a little bit but not significantly.
Codable is desirable because it encodes/decides directly to strifes vs manually picking fields out of dicts.
Can you see any differences with different levels of optimization? I recall a presentation at some point where the old obj-C style compiled code did a lot of checks before and after calling a method ("does this object listen to this message?"), while with an optimization option enabled (whole module optimization?) these calls could be optimized out. That is, with Swift they can make the resulting machine code less er, "checking for safety", so to speak.
This was done at -O I believe (whatever the default is for "Profiling" in Xcode). This is anecdotal, but the fact that the code isn't littered with _swift_retain/_swift_release calls probably means that most of the standard reference-counting boilerplate has been optimized away.
Yeah, Swift-most-everything is pretty slow, but particularly parsing/generating. Pre-Swift Foundation serialisation code was already...majestic, and in the Swift conversion they've typically managed to slow things down even further. Which didn't seem possible, but they managed.
I have given a bunch of talks[1] on this topic, there's also a chapter in my iOS/macOS performance book[2], which I really recommend if you want to understand this particular topic. I did really fast XML[3][4], CSV[5] and binary plist parsers[6] for Cocoa and also a fast JSON serialiser[7]. All of these are usually around an order of magnitude faster than their Apple equivalents.
Sadly, I haven't gotten around to doing a JSON parser. One reason for this is that parsing the JSON at character level is actually the smaller problem, performance-wise, same as for XML. Performance tends to be largely determined by what you create as a result. If you crate generic Foundation/Swift dictionaries/arrays/etc. you have already lost. The overhead of these generic data structure completely overwhelms the cost of scanning a few bytes.
So you need something more akin to a steaming interface, and if you create objects you must create them directly, without generic temporary objects. This is where XML is easier, because it has an opening tag that you can use to determine what object to create. With JSON, you get "{" so basically you have to know what structure level corresponds to what objects.
That resonates well with my conclusions that led to the Replicated Object Notation project. [1]. If the parser creates an AST tree or some number of dictionaries or some other bullshit... "now you have two problems", that's it.
I settled on a tabular-log format, which is streamed and immediately consumed most of the time, no intermediate object structures.
Then, that "text vs binary" distinction became mostly moot. The binary is slightly more efficient, but grossly less readable, so no big gain, unless at grand scale.
What are you using? Have you tried NSJSONSerialization? It’s quite fast (am very curious how it shows in these benchmarks), but I don’t think it does the fancy Codable stuff.
Swift has JSONEncoder and JSONDecoder types to do Codable, though internally they have to encode to/decode from the Foundation objects that JSONSerialization produces.
Hadn't seen that particular wrapper, but if we're going to take on an FFI solution, we're more likely to use Rust for this, and implement more logic than just JSON parsing.
One of the two authors here. Happy to answer questions.
The intent was to open things but not publicize them at this stage but Hacker News seems to find stuff. Wouldn't surprise me if plenty of folks follow Daniel Lemire on Github as his stuff is always interesting.
I think the behavior of all the code that touches is undefined (it breaks the calling convention of the ABI), and while this often results in corrupted floating point values in registers, maybe you won't see much if you are not using the FPU. Still, since the function is inline, chances that this gets inlined somewhere where it could cause trouble seem high.
You might want to look into that.
Also, I wish this would all be written in Rust, there is great portable SIMD support over there. Might make your life easier trying to target other platforms.
EDIT: as burntsushi mentions below, that's not available in stable Rust, but if you want to squeeze out the last once of performance out of the Rust compiler, chances are you won't be using that anyways.
I would be extremely surprised if we were somehow accidentally using MMX; it's not our intention. It is my belief that we are using only AVX2, which, like the 19-year old SSE/SSE2 extension, has its own registers that are independent of the x87 floating point set.
If, once you review our codebase and verify that we are not inadvertently using a 22-year-old SIMD extension but still have undefined behavior, please write an issue on github.
I'm admiring Rust from a distance at this stage. I am comfortable enough with writing bare intrinsics and slapping a giant #ifdef around stuff.
If they want to squeeze out the last ounce of performance out of the Rust toolchain it probably wouldn't make sense to use stable Rust anyways, so I don't think that's a big downside.
Also, they are already relying on "unstable" (non-standard conforming) C++ features (e.g. the code uses non-standard attributes behind macros, etc.). Using nightly Rust isn't worse than that per se.
Using Rust does have downsides. For the type of code they are writing, the main downside would probably be losing an alternative GCC backend, which might or might not be better than LLVM for their application.
Still, they would win portable SIMD and being able to target not only x86_64 but also ARM, Power, RISCV, WASM, etc., which is always cool to show in research papers.
I'm not suggesting that Rust is a perfect trade-off, only that it's an interesting one depending on what they want to do.
Sure. I'm just trying to be careful that we aren't going around advertising features that aren't stable yet without specifically saying that they aren't stable. It leads to a disappointing expectations mismatch.
I do think stable Rust is perfectly capable though. I don't generally target nightly Rust and am happy with how much I can squeeze out of it. :-) (Check out the benchmarks for the memchr crate, which use SIMD internally and should be competitive with glibc's x86_64 implementation that's in Assembly.)
Most programming languages don't have a stable / unstable distinction at all, and unless one is "in the Rust loop", stating something like "_unstable_ Rust can do X" won't probably mean what the reader think it means.
Unstable Rust sounds very dangerous, like something that breaks every day. Definitely more dangerous than stable Rust.
Yet if one is in the Rust loop, one knows that this is often not the case. I've been using some unstable features on nightly, like const fn, specialization, function traits, etc. for years (3 years?), and I've never had a CI build job fail due to a change to the implementation of these features.
Yet some features in stable Rust like Rust2018 uniform_paths or stable SIMD have caused many build job breaks and undefined behavior due to bugs in the compiler over the last months.
So whatever stability means, it does not mean "using this feature won't result in your code not breaking". It also doesn't mean "you have to use a nightly toolchain to use the feature".
An unstable Rust feature is more like a "compiler extension" in C / C++. It is just something that hasn't fully gone through the process of standardization.
I don't think it is a fair characterization that code that uses this extensions is not Rust. Pretty much all C++ code uses compiler extensions, and nobody says that this code is not C++ just because it uses one of them.
Explaining all of this when telling someone "Rust is a technology that allows you to solve problem X nicely" isn't helpful.
Many people vocal about Rust seem to think that Rust is the end in of itself. The goal isn't solving a problem, but using Rust to solve it. I see many of these people argue that unstable Rust isn't Rust, and that people should be using stable Rust etc. For most people, using Rust isn't the goal, solving their problem is. Whether one or many compiler extensions have to be enabled for that is pretty much irrelevant to them. Sure it would be nice if one didn't need to do that, but it isn't a big deal either. The big embedded community is living proof of that. Only a small minority of this community cares about the language enough to participate in its evolution. Most people don't care enough about that, they have more interesting problems to solve.
I'm writing an IoT library for devices with tiny microprocessors and have been sending data as JSON or BSON (binary JSON). On the backend, I've been storing reports from IoT devices into a database (MariaDB on AWS). How crazy would it be to just store all the data as JSON files on disk (or S3 bucket) and then batch process them when I need to perform data analysis on them? If a million devices sends dozens of status reports per day, that's going to be a crapton on files... but that might be faster to process than querying the database.
If you or anyone else has some opinions on this, please let me know! I'd really like to learn how people do this type of analysis at scale.
reading lots of small files on s3 or local filesystems is tricky. a million devices with one dozen files, so lets say 12 million files.
One thing locally is each file takes up a full block. So even if you only need 500 bytes of data in a file, and a block is 4kb, youve wasted 3.5kb of space and IO. Multiply that by a million and youre wasting gigabytes of space.
In S3, listing 12 million files takes 12 thousand http(max return is 1000 items). So that would take two minutes if you assume its 10ms per round trip. Let's say you wanted to read each file, and again each read takes 10ms.. youre looking at 1.4 days. Obviously this can be parallelized, but when you look at the raw byte size this is a huge overhead, and this is just to read one day of data.
If you concatenate the files together to get a reasonable size and number of files, raw json on s3 is really powerful. Point athena at it, and you just write sql and it handles the rest, and is serverless. But it does make single row lookups more expensive(supplementing with dynamodb could keep it serverless if single row lookups are frequent).
lots of optimizations will get improvements, like parquet that
tobilg mentioned(binary format and columnar), but anything with a decent file size will work.
The best way to not lose messages is to minimize the work done by your log receiver. So we did. It receives the uploaded log file chunk and appends it to a file, and that's it. The "file" is actually in a cloud storage system that's more-or-less like S3. When I explained this to someone, they asked why we didn't put it in a Bigtable-like thing or some other database, because isn't a filesystem kinda cheesy? No, it's not cheesy, it's simple. Simple things don't break.
We‘re using AWS Kinesis delivery streams to batch incoming JSON messages from IoT devices to Parquet files in S3. Those can directly be read by different AWS services like Redshift, EMR or Athena...
We use Athena for all our robotics data, which we ETL into JSON. It's fantastic for queries that are simple time-slice queries, as most are because sensor data is inherently time-series. When more complicated joins are necessary, the performance is there across terabytes, and the cost is very very low, $5 per terabyte scanned (storage costs are another thing).
This comment needs to be higher up; Amazon has a service for doing just this, dumping 'dumb' files (like json, csv, etc) into S3 buckets and performing SQL queries on them. No need to have to think about how to store things for future querying.
I've used Athena really effectively to solve similar problems. If your data storage is relatively small and/or your queries relatively infrequent, JSON can be a good fit. As one of those dimensions expands, you can decrease costs/increase performance by converting to Parquet and compressing.
I am replying to you as an engineer at an IoT company that provides SaaS in AWS for the data our devices produce. To solve this problem, we transmit our data in a proprietary "raw" binary format that then gets parsed into a protobuf. All data for a given UTC day is appended to this protobuf file and hosted in S3. Retrieving data requires downloading the protobuf file from S3, unmarshalling the protobuf, and finding the entry you care about.
If you are considering using plain files instead of a DB server, you could try a compromise and use an embedded key-value store like RocksDB, LevelDB, BadgerDB etc.
It's local storage only, limited query capabilities depending on the DB, but should be extremely fast.
well if you need indexed lookups, then use a database
if you're doing "table scan" processing of entire datasets, sure just-a-bunch-of-files would work too.
Databases can be surprisingly fast for things like that, since high performance file i/o is full of tricky/annoying stuff that databases have already optimized for.
I haven't used it but have been given a presentation by them on it, and it was very very good.
They store data in S3 and use FoundationDB for indexes. You can feed it JSON and it'll index it and let you query it on a massive scale shockingly fast.
Obviously they are not aimed at small hobby projects but if your project has money / serious product depending on your needs it's well worth looking at.
On the S3 cheaper / smaller end you can batch up data daily / weekly etc. So the landing bucket acts as a queue that gets processed creating daily batch files from the small files aggregated together. You can then take the daily batches to create weekly batches etc etc, essentially partitioning. This will reduce the total number of files needed to query. If you use deterministic names based on how you plan to query this can also reduce the number of files you need to list / parse. When batching / re-partitioning the data you can also use the Apache Parquet format to compress a little better + also import in some of the querying tools out there.
I've written my fare share of performant code over the years, but this is some next level shit. I've been reading it the last few hours. The only question I have is what is the term for that place considered two degrees past black magic? Since you live there, I have to assume you know the name.
It's not magic. The things that enable writing this kind of code are essentially practice and specialization. Most people have to write code that works all all architectures and where performance is probably less critical than having a simple, workable codebase - so the opportunities to practice writing SIMD code are rare under those constraints.
Unfortunately, the fragmentation of SIMD standards and various pitfalls in implementation (the much ballyhoo'ed "running AVX will make your processor clock to half its speed or something" exaggerations, for example) make a lot of people nervous about putting in the time to commit to developing expertise, which is a shame.
Not really a question, but if you ever get to the point of wondering what a good next challenging project would be, consider generalizing some of these techniques into a next generation Yacc / Bison replacement.
Something that can take generic grammer rules and turn it into a high performance parsing engine.
It wouldn't have to support every possible grammar or option. Json isn't that complex of a language, but even a limited set of grammar options in exchange for a performant parser could be of benefit for a very large set of problems.
It's on the list as a research project. It's not obvious to me at this stage that the bottlenecks for more advanced parsers are necessarily going to be in the same place as they are for JSON. It might make more sense to look at a state-of-the-art parser and see if we can contribute a few tricks instead.
Probably not too hard. It would come down to how easy it is to detect quoting conventions so you don't accidentally parse () chars in strings. JSON is medium-easy. I don't know where the canonical definition of s-expressions you're using comes from (is it just Common Lisp?) so I don't know how this works.
We'd like to have some more examples of formats people care about - I'm interested in generalizing this work. So if you want to followup with more detail please do.
The big difference between RapidJson and sajson is surprising to me. When I benchmarked them their performance was comparable: https://github.com/project-gemmi/benchmarking-json . Did you use RapidJson in full-precision mode?
By the way, nativejson-benchmark (from RapidJson) has a nice conformance checker that tries various corner cases. But you probably know it.
More performance details beyond what's on the site will follow (in a while).
We use RapidJSON in the high-performance mode not the funky mode that minimizes FP error (which is some astounding work - I had no idea that strtof was so involved!). Number conversion is not our #1 focus - doing it well is nice, but all implementations have access to the same FP tricks, so you don't really learn much by going wild on this aspect.
At least, you don't unless FP conversion is your focus, in which case you should share your FP conversion code with everyone!
You should take a look at std::from_chars IIRC it can completely destroy other parsers within the stdlib because it's not intended to take locale into consideration.
I recently saw people using gpu to parse csv files. there are also other articles on using gpu to parse json. do you think if gpu can perform well on this type of tasks?
I'm not aware of an article that covers a actual implementation or that has a benchmark of performance. As for GPGPU: it's possible. Our first stage of matching is very parallel. But Amdahl's law would, of course, suggest that the serial parsing step would dominate.
I'm interested in this: some aspects of our very serial 'stage 2' (the parsing step) could be made parallel. This would be very interesting. Unfortunately I personally cannot be made parallel, so working on this needs to go into a big queue with a lot of other work.
How hard would it be to extend the parser to handle arbitrary-precision numbers? Strictly speaking the JSON spec does not require numbers to fit into 64-bit ints / doubles.
Daniel Lemire did most of the work on the number handling, but our general approach was to try to do work that's similar to what the bulk of other libraries do. I believe pretty much everyone throws oversize numbers on the floor.
I don't think it would be hard at all; it would just be extra effort that wasn't needed to run obvious comparisons.
This would imply an ARM port, I guess, as x86 android isn't much of a thing anymore AFAIK.
I don't think either of us know much about android - not enough to do that. But an ARM port is very interesting.
Since I'm no longer an Intel employee I don't see why I shouldn't skill up and do a Neon port (I got interested in SVE, but since ARM doesn't seem to want to bother releasing cores that run SVE, I'm not going to go too far down that path right now). Neon, on the other hand, is in tons of places. As far as I know all the required permutes, carryless multiplies and various other SIMD bits and pieces are there on Neon. So it's a simple matter of porting.
If you're working with json objects with sizes on the higher end quite often you're not going to need the entirety of them, just a small part of them. If that is the workload what then to do is simply parse as little data as possible: skip the validation, locate the relevant bits, and then start parsing, validation and all the stuff. In this optimizing the json scanner/lexer gives much greater improvement than optimizing the parser.
Though this job is trickier than it may look. The logic to extract the "relevant" bits is often dynamic or tied to user input but for the scanner/lexer to be ultrafast it has to be tightly compiled. You can try jitting but libllvm is probably too heavyweight for parsing json.
Jitting is a common tool that people seem to reach for whenever they are parsing or lexing anything at any time. It's really not necessary; there are plenty of fast search methods out there.
JIT approaches make a lot of sense for lex/yacc and their numerous descendants, as these typically need to put a lot of extra logic into the process of parsing. You don't need to JIT just to look up some strings and/or parse a fairly simple hierarchical structure.
Parsing itself doesn't need jitting but as soon as you start to use the parsed data to interface with some typed containers the data plumbing consumes much more time than parsing does and drags down all the optimization. For parsing to interact well with static languages jitting is a possible solution to look at.
I agree that's a good strategy for big JSON. Do you know of any such "lazy" parsers?
I think the problem is that to extract arbitrary keys, you really need to parse the whole thing, although you don't need to materialize nodes for the whole thing.
But if you have big JSON with a given schema, you may be able to skip things lexically. You basically need to count {} and [], while taking into account " and \ within quoted strings.
That doesn't seem too hard. I think a tiny bit of http://re2c.org/ could do a good job of it.
It still walks the full tree like a regular parser, but just avoids creating any data items unless the selector matches. Though there is an outstanding issue to support JSONPath in the selector, currently it only matches individual keys and values.
It’s not exactly the lazy parser you describe, but Sparser[1] builds filters to exclude json lines/files that can’t contain what you’re looking for, and only parses those that might.
The Morning Paper’s writeup[2] from last year provides a good summary
This work is somewhat orthogonal to ours as it assumes that you can locate JSON records without doing parsing; if I remember correctly, it groups JSON records as lines. If your JSON has been formatted to conform to this, I suppose it would be quite effective.
That's what our first stage does, pretty much. I would imagine we do it way faster than re2c would do it.
Parsing the entire document lock stock and barrel is an easier thing to write about and benchmark. The problem is with skipping around and pulling out bits of JSON from a benchmarking framework is that attempting to present such data often amounts to "hey, we asked ourselves a question and then we got a really good answer for it!". It's hard to picture what a 'typical' query for some field over a JSON document would look like. Conversely, it's pretty easy to know when you finished parsing the Whole Thing.
> It's hard to picture what a 'typical' query for some field over a JSON document would look like.
Exactly. A "query" would have to define not only the path, type of the field in the source data but also the type/interface of where you want to put that data. Combining dynamic queries and typed data you get a fairly tricky problem, which is why I said this is tricky. I worked on a similar thing for protobuf and jitting was a solution I looked into (in that project libllvm was too unwieldy to use).
I'm not sure what you mean by arbitrary? What parsing in this case means e.g. turning a string of digits into a ieee754 float number in memory. I think this project is meant to accelerate this part with SIMD, but a greater improvement can be obtained by simply not doing this for as much data as possible. If the actual materialized data constitutes a small part of the original, there should be ways to do minimum work for the rest.
Number handling looks like it would be a problem. There are Test suites for json parsers and lots of parsers that fail a lot of these tests. Check e.g. https://github.com/nst/JSONTestSuite which checks compliance against RFC 8259.
Publishing results against this could be useful both for assessing how good this parser is and establishing and documenting any known issues. If correctness is not a goal, this can still be fine but finding out your parser of choice doesn't handle common json emitted by other systems can be annoying.
Regarding the numbers, I've run into a few cases where Jackson being able to parse BigIntegers and BigDecimals was very useful to me. Silently rounding to doubles or floats can be lossy and failing on some documents just because the value exceeds max long/in t can be an issue as well.
> We store strings as NULL terminated C strings. Thus we implicitly assume that you do not include a NULL character within your string, which is allowed technically speaking if you escape it (\u0000).
I lost count to broken JSON parsers which all fall to that.
Yeah, this is unforgivable, and for me makes the whole speed argument void.
Edit: to be fair, they handle a couple of other things, which many similar libraries ignore. I particulary like the support for full 64bit integers. And at least they document their limitation on NULL bytes.
"Unforgivable" is a bit strong. I don't think this is something which invalidates our entire approach - nothing in the algorithm depends on this behavior as the \0 chars don't appear until quite late. Even then, we are not dependent on sighting a \0 in our string normalization and as such we can probably just store a offset+length in our 'tape' structure rather than assuming we have null terminated strings.
Please add an issue on Github.
Edit: I went ahead and added an issue. Seems like something we should fix.
I feel like if you need to parse Gigabytes per second of JSON, you should probably think about using a more efficient serialization format than JSON. Binary formats are not much harder to generate and can save a lot of bandwidth and CPU time.
I have in the past parsed terabytes of JSON. The specific use case was analysing archived Reddit comments. The Reddit API uses JSON, and somebody [1] runs a server that just dumps them in a file, one line of JSON per comment, and offers them for download (compressed, obviously). So now you end up with Gigabytes of small JSONs per month, and anything you do will be quickly dominated by JSON parsing time.
You could store them in some binary format, but the API response format changed over the years with various fields being added and removed, and either your binary format ends up not much better than JSON or you end up reencoding old comments because the API changed.
The parsed format in tape.md is quite close to the flatbuffer format. Flatbuffer can encode any json file just fine. The parse time is immediate and requires no extra memory.
It’s a great way to store big json files where you only want to access a subset of data very quickly and not load the whole file into memory.
> either your binary format ends up not much better than JSON or you end up reencoding old comments because the API changed
Those are other options too, eg, storing the schema separately from the records (then batching records with identical schemas in compact binary files) and defining migration rules between different schemas (eg, if schema A has required field "foo" while schema B has required field "foo" and optional field "bar" then data which follows schema A can be trivially migrated to schema B at read time without needing to reencode on disk).
I agree. But JSON serialization is very complicated for very little gain. It would make it impossible to do things like opening the json file in an editor to change some property names. So watch out for premature optimization.
For storing stuff yourself, sure, but as a web developer, most data I consume is JSON served by some third-party REST API and the format they serve me is definitely not under my control. Anecdotally, most developers I know or have spoken to are in similar situations for a large portion of their data-processing needs (at least, for stuff that's not in a database, although even in DB's, JSON is increasingly popular for a number of reasons).
Even for output, there is the common case where your clients expect JSON because its the de facto standard and is super accessible (every language has parsers for it), so you have little choice but to serve your data as JSON.
This would be an easy extension if you wanted to concatenate the files. The plumbing and API aren't there right now, but it isn't hard to see how to do it.
I guess the question is, what do you parse it to? I'm guessing definitely not turning objects into std::unordered_map and arrays into std::vector or some such. So how easy it is to use the "parsed" data structure? How easy is it to add an element to some deeply nested array for example?
The ParsedJson type is immutable and accessed mutating iterators (up and down the tree, forward and backward through members and indices).
My immediate thought is to compare it to rapidjson, which I've used before. The paradigm of mutating iterators seems awkward at first but should be just as powerful as rapidjson's Value. For example, both approaches end up doing a linear scan to find an object member by name.
The fact that rapidjson supports mutation of Values and simdjson does not has huge implications (as mentioned in the simdjson README scope section), I suspect this tradeoff explains most of the performance differences as I know rapidjson also uses simd internally.
I can't speak for this project, but my own for CSV files ( https://github.com/dw/csvmonkey ) provides a high level interface that allows the tokenized data to be manipulated in-place without full decoding. The interface exported in Python is that of a plain old dictionary with one added magical semantic (lazy decode on element access). The internal representation of the parse result is a simple fixed array of (ptr, size) pairs
Methods like this are used for batch search / summation where only a fraction of the parsed data is actually relevant during any particular run. You'll find similar approaches used in e.g. the row format parser of a database like MongoDB or Postgres
> Requirements: […] A processor with AVX2 (i.e., Intel processors starting with the Haswell microarchitecture released 2013, and processors from AMD starting with the Rizen)
iirc, it's complicated. Some instructions don't reduce the frequency; some reduce it a little; some reduce it a lot.
I'm not sure AVX2 is as ubiquitous as the README says: "We assume AVX2 support which is available in all recent mainstream x86 processors produced by AMD and Intel."
I guess "mainstream" is somewhat subjective, but some recent Chromebooks have Celeron processors with no AVX2:
It doesn't seem that laughable to me to want faster JSON parsing on a Chromebook, given how heavily JSON is used to communicate between webservers and client-side Javascript.
"Faster" meaning faster than Chromebooks do now; 2.2 GB/s may simply be unachievable hardware-wise with these cheap processors. They're kinda slow, so any speed increase would be welcome.
AVX2 also incurs some pretty large penalties for switching between SSE and AVX2. Depending on the amount of time taken in the library between calls, it could be problematic.
This looks mostly applicable to server scenarios where the runtime environment is highly controlled.
There is no real penalty for switching between SSE and AVX2, unless you do it wrong. What are you referring to specifically?
Are you talking about state transition penalties that can occur if you forget a vzeroupper? That's the only thing I'm aware of which kind of matches that.
I wonder how this compares to fast.json: "Fastest JSON parser in the world is a D project?" (https://news.ycombinator.com/item?id=10430951), both in an implementation/approach sense and in terms of performance.
Sadly it will not. Arguably we could 'stream' things, but we don't have an API or a use case for it. If you could capture your requirements and put them on an issue on Github, it would be helpful. We're not against the streaming use case, we just don't understand it very well.
Probably not. I requires a memory allocation the size of the file for parsing.
However they have the ability to build a tape out of the json and find the interesting marks. Perhaps it can be adapted to make a fast parser than only parses the relevant stuff but zooms through the large file in blocks.
It's probably relevant to mention https://github.com/BurntSushi/rust-csv. It uses a state machine (which seems to be the author's expertise) to parse CSVs really fast. Based on some other work, you can do better if you use some of the new SIMD instructions.
I've developped a full RFC compliant CSV parser with Python bindings and supporting SSE4 to AVX-512 instruction sets, however i'm struggling with my hierarchy to open-source it at the moment.
But, the goal of my message is not to tease you with an unavailable code. It's just to say it is a lot more simpler to write a CSV parser than a JSON parser.
So, do not hesitate to write one yourself ! It's easy and a nice way to introduce yourself to SIMD instructions.
Perhaps I'm misunderstanding or don't have a good enough grasp of this, but, in what circumstance would you need to parse gigabytes? I've only seen it be used in config files, so...
What usually happens is someone creates an API, one which did not initially have to handle much data, and then it just grew over time. (I guess it's similar to how a lot of the Internet's early application-layer protocols like HTTP, SMTP, etc. are text-based --- the text format was initially more "convenient" for a variety of reasons, but obviously is not very efficient at scale.)
Or, perhaps a more common scenario today, it was designed by people who simply had no knowledge of binary protocols or efficiency at all --- not too long ago I had to deal with an API which returned a binary file, but instead of simply sending the bytes directly, it decided to send a JSON object containing one array, whose elements were strings, and each string was... a hex digit. Instead of sending "Hello world" it would send '{"data":["4","8"," ","6","5"," ","6","C"," " ... '
Log files? More and more places are switching to easily machine-parsable logs to run statistics and checks over, and JSON is a common format (e.g. because it's still somewhat human-readable and will work over logging infrastructure set up to transport lines of text)
If this kind of work is interesting to you, you might like Daniel Lemire's blog (https://lemire.me/blog/).
He's a professor, but his work is highly applied and immediately usable. He manages to find and demonstrate a lot of code where we assume the big-O performance, but the reality of modern processors and caching (etc.) mean very difference performance in practice.
Thanks for posting. I've been working with lidar/robotic data more recently and it's nice to work with JSON directly, when the performance is good enough.
The JSON spec [1] never had any updates, so it couldn't have diverged.
Kudos to Douglas Crockford for keeping it simple. I wish more standards committees would take a cue from him. (Looking at ECMAScript [2] and C++.)
There's been a tremendous amount of growth and value around JSON precisely because it's so simple and easy to implement.
People complain about the lack of comments and trailing commas, but I think those are really expanding on the initial use case of JSON, and the benefit isn't worth cost of change. JSON does some things super well, other things marginally well, and some not at all, and that's working as intended.
You can always make something separate to cover those use cases, and that seems to have happened with TOML and so forth.
(I recall there was an RFC that cleaned up ambiguities in Crockford's web page, but it just clarified things. No new features were added. So JSON is still as much of a subset of JavaScript as it ever was. On the other hand, JavaScript itself has grown wildly out of control.)
> Although Douglas Crockford originally asserted that JSON is a strict subset of JavaScript, his specification actually allows valid JSON documents that are invalid JavaScript. Specifically, JSON allows the Unicode line terminators U+2028 LINE SEPARATOR and U+2029 PARAGRAPH SEPARATOR to appear unescaped in quoted strings, while ECMAScript 2018 and older does not.
Yeah I remember that quirk, and that's why I said it's "as much of a subset as it ever was". :) Because of this issue, it was technically never a subset.
But almost all real JSON documents are subsets of JavaScript, unless they happen to have those characters.
And the salient point is that if JSON never changes, then no further divergence from JavaScript is possible.
But remember that your comment wasn't actually addressing avmich's objection to the assertion "All JSON is JavaScript, but not all JavaScript is JSON".
That assertion is indeed incorrect.
avmich then wrote "I thought they diverged specifications".
That is also correct. JSON was meant to be a perfect subset of JavaScript. Instead, and by accident, it diverged from the relevant specification.
Your comment instead was mostly focused on opposition to changing the existing JSON specification, which is a different topic.
> JSON allows the Unicode line terminators U+2028 LINE SEPARATOR and U+2029 PARAGRAPH SEPARATOR to appear unescaped in quoted strings, while ECMAScript 2018 and older does not.
My code has parsed a lot JSON and that is new data to me. Thank you for that!
Do you know the historical reasoning for this particular deviation? Are there any infamous bugs or common use cases this departure impacts?
This is another useful resource, discussed here already - http://seriot.ch/parsing_json.php - which lists relevant standards. But "the" standard is static, so divergence, is any, is with other standards (different from json.org) vs. evolving JavaScript.
> People complain about the lack of comments and trailing commas,
Yeah, I don't think JSON should include those things. I think the lack of comments makes JSON a poor format for config files, but that just means you should use another format for config files. JSON is good for machine-to-machine communication.
Basically saying any valid-format JSON is valid JS as well. But JSON doesn't have any programming features (or the nice things like non-quoted keys/trailing commas)
This is a dangerous assumption to make, and one that bit us a while ago when using trigger.io for an app.
We had a lot of user supplied data in the strings of our API responses, some of it copied from Word documents and were ridden with U+2028 and U+2029 whitespace. Turns out that on iOS, the trigger.io library makes the all too popular assumption that any well-formated JSON can be interpreted as JS, and parses the responses with "eval", thus turning all those unicode characters _within JSON strings_ into newlines!
To my knowledge, it is limited to posting "Towards JSON Parsing on a GPU" type articles. Writing that sort of article is easy and fun, without the tedious burden of implementing things.
The people complaining about dependency management in Python should try doing it in C++; there seems to be half a dozen competing ones. And three times as many build systems.
Though from the readme on that module the dev says "it turns out that you’re better off using the normal Node.js/V8 implementation unless you’re operating on huge JSON.
... the bridging from V8 to C++ is a bit too costly at this stage."
This code in particular won’t, since it relies on a particular extension of the x86 instruction set. I don’t believe Arduino compatible chips have simd instructions, but if they do, a similar approach could be taken.
I'm not aware of any SIMD-capable Arduino chips; even when Quark was a thing, it didn't support SIMD.
It's possible to do SWAR (SIMD Within A Register) tricks to try to substitute, but on a 32-bit processor (or even a 64-bit processor) I doubt our techniques would look good. In Hyperscan, my regex project, we used SWAR for simple things (character scans) but I doubt that simdjson would work well if you tried to make it into swarjson. :-)
[1]: https://github.com/xi-editor/xi-mac/issues/102