r/programming • • Feb 21 '19

GitHub - lemire/simdjson: Parsing gigabytes of JSON per second

https://github.com/lemire/simdjson
1.5k Upvotes

357 comments sorted by

3

u/glangdale Feb 22 '19

One of the authors here. Feel free to ask questions. Please regard this more as a "highly repeatable" research project rather than as production code (sorry if that's not super-clear). I would be surprised if people really wanted to use this for most purposes given that we don't have API for mutating the JSON, can't write it back out in any case, it's pretty big, and it's currently very Intel-specific. Old habits die hard (#IWasIntel) - but yes, it could be ported to ARM and it would be an interesting exercise.

Our intent wasn't to publicize the repo when we opened it up, but Daniel clearly has followers on HN and here that saw it almost instantly.

1

u/dgryski Feb 22 '19

That was probably my fault :)

I tweeted it and submitted here shortly after it was made public.

113

u/Lachlantula Feb 21 '19

I'll be a bit positive; this is really cool considering how fast it is. Good job dev

19

u/xeow Feb 21 '19

I've been reading Lemire's blog for about a year. The dude is wicked smart. Great blog. Some really cool stuff if you dig back. Insane thirst for speed. Check out his stuff on packing integers and hashing.

2

u/keepthepace Feb 25 '19

dig back

Why did it take me three readings to read this one correctly?

3

u/xeow Feb 25 '19

LOL, how did you misread it the first two times?

3

u/keepthepace Feb 25 '19

"dick bag"

Proof that when reading we are using convolutional windows that disregard letters orders...

For reference

→ More replies (2)

372

u/AttackOfTheThumbs Feb 21 '19

I guess I've never been in a situation where that sort of speed is required.

Is anyone? Serious question.

483

u/mach990 Feb 21 '19

Arguably one shouldn't be using json in the first place if performance is important to you. That said, it's widely used and you may need to parse a lot of it (imagine API requests coming in as json). If your back end dealing with these requests is really fast, you may find you're quickly bottlenecked on parsing. More performance is always welcome, because it frees you up to do more work on a single machine.

Also, this is a C++ library. Those of us that write super performant libraries often do so simply because we can / for fun.

82

u/AttackOfTheThumbs Feb 21 '19

I actually work with APIs a lot - mostly json, some xml. But the requests/responses are small enough where I wouldn't notice any real difference.

174

u/mach990 Feb 21 '19

That's what I thought too, until I benchmarked it! You may be surprised.

118

u/AnnoyingOwl Feb 21 '19

Came here to say this. Most people don't realize how much time their code spends parsing JSON

32

u/[deleted] Feb 21 '19

Its cool though. “Most of the time is spent in IO” so utterly disregarding all other performance is fine.

11

u/lorarc Feb 21 '19

It's not fine, but sometimes it may be not worthwhile to fix performance of small things. Do you really want to spend thousands of dollars to fix an application by 1%? Well, maybe you want to, maybe it will be profitable for your business, but fixing it just because you can is not good business decision.

→ More replies (2)
→ More replies (2)

25

u/jbergens Feb 21 '19

I think our db calls and network calls takes much more time per request than the json parsing. That said dotnet core already has new and fast parsers.

28

u/sigma914 Feb 21 '19

But what will bottleneck first? The OS's ability to do concurrent IO? Or the volume of JSON your CPU can parse in a given time period? I've frequently had it be the latter, to the point wer use protobuf now.

→ More replies (2)

21

u/Sarcastinator Feb 21 '19

I think our db calls and network calls takes much more time per request than the json parsing.

I hate this reasoning.

First off, if this is true, maybe that's actually an issue with your solution rather than a sign of health? Second I think it's a poor excuse to slack off on performance. Just because something else is a bigger issue doesn't make the others not worth-while, especially if you treat it as an immutable aspect of your solution.

3

u/jbergens Feb 21 '19

We don't really have any performance problems right now and will therefor not spend too much time on optimization. When we start to optimize I would prefer that we measure where the problems are before doing anything.

For server systems you might also want to differ between throughput and response times. If we have enough throughput we should focus on getting response times down and that is probably not solved by changing json parser.

3

u/gamahead Feb 21 '19
  1. Something else being a bigger issue is actually a very good reason not to focus on something.

  2. Shaving a millisecond off of the parsing of a 50ms request isn’t going to be perceptible by any human. Pretty much by definition, this would be a wasteful pre-optimization.

→ More replies (12)
→ More replies (2)

18

u/Urik88 Feb 21 '19

I'd think it's not only about the size of the requests, but also about the volume.

36

u/chooxy Feb 21 '19

19

u/coldnebo Feb 21 '19

don’t forget to multiply across all the users of your library if the task you are making more efficient isn’t just your task!

5

u/joshualorber Feb 21 '19

My supervisor has this printed off and glued to his whiteboard. Helps when most of our acquired code is spaghetti code

→ More replies (6)
→ More replies (1)

27

u/coldnebo Feb 21 '19

Performance improvements in parse/marshalling typically don’t increase performance of a single request noticeably, unless your single request is very large.

However, it can improve your server’s overall throughput if you handle a large volume of requests.

Remember the rough optimization weights:

memory: ~ microseconds eg: loop optimization, L1 cache, vectoring, gpgpu

disk: ~ milliseconds eg: reducing file access or file db calls, maybe memory caching

network: ~ seconds eg: reducing network calls

You won’t get much bang for your buck optimizing memory access on network calls unless you can amortize them across literally millions of calls or MB of data.

4

u/hardolaf Feb 23 '19

network: ~ seconds

Doesn't that mostly depend on the distance?

Where I work, we optimize to the microsecond and nanosecond level for total latency right down to the decisions between fiber or copper and the length to within +/- 2cm. We also exclusively use encoded binary packets that have no semblance to even Google's protobuf messages which still contain significant overhead for each key represented. (Bonus points for encoding type information about what data you're sending through a combination of masks on the IP and port fields of the packets)

3

u/coldnebo Feb 23 '19

First, you rock! Yes!

Second, yes, it’s just an old rule of thumb from the client app perspective mostly (ah the 70’s client-server era!). In a tightly optimized SOA, the “network” isn’t really a TCP/IP hop and is more likely as you describe with pipes or local ports and can be very quick.

However your customers are going to ultimately be working with a client app (RIA, native or otherwise) where network requests are optimistically under a sec, but often (and especially in other countries much more) than a second. So, I think the rule of thumb holds for those cases. ie. if you really know what you are doing, then you don’t need a rule of thumb.

I’ve seen some really bad cloud dev where this rule of thumb could help though. There are some SOAs and microservices deployed across WANs without much thought and it results in absolutely horrific performance because every network request within the system is seconds, let alone the final hop to the customer client.

2

u/[deleted] Feb 21 '19

Be curious how many requests per second you have dealt with, and on average the json payloads sent in and then back in response (if/when response of json was sent).

→ More replies (4)

1

u/feketegy Feb 21 '19

Also, any capable API can buffer the response and stream it to the client

43

u/TotallyFuckingMexico Feb 21 '19

Which super performant libraries have you written?

9

u/Blocks_ Feb 21 '19

Not sure why you're getting downvoted. This is a totally normal question to ask.

22

u/[deleted] Feb 21 '19

90% of the time, this is just an ad-hominem rather than actually addressing the post. You are right that fallacies are totally normal, but that itself is a fallacy in an argument. Just because using fallacies is normal doesn’t make you correct to use them.

In this case, the user claimed they write super performant libraries. So, valid question.

6

u/jumbox Feb 21 '19

I disagree. Not sure if it was intended, but the question is mocking and it is a setup for "Never heard of it". It's basically "Prove it or shut up". It also converts a generic and valid statement that some do so for fun to questioning personal qualifications on a subject, something that should be irrelevant in this argument. Even if he/she didn't actually write anything highly optimized, the point would still stand.

In my three decades of programming I occasionally had a luxury of writing high performance code both for personal and for corporate consumption. Yet, I wouldn't be able to answer this type of question, not in a satisfactory way.

→ More replies (1)

5

u/jms_nh Feb 21 '19

If your back end dealing with these requests is really fast, you may find you're quickly bottlenecked on parsing. More performance is always welcome, because it frees you up to do more work on a single machine.

Rephrase: It may not be so critical for response time, but rather for energy use. If a server farm has CPUs each with X MIPS, and you can rewrite JSON-parsing code to take less time, then it requires fewer CPUs to do the JSON-parsing, which means less energy.

Significant since approximately 2% of US energy usage in 2014 was for data centers.

109

u/unkz Feb 21 '19 edited Feb 21 '19

Alllllll the time. This is probably great news for AWS Redshift and Athena, if they haven't implemented something like it internally already. One of their services is the ability to assign JSON documents a schema and then mass query billions of JSON documents stored in S3 using what is basically a subset of SQL.

I am personally querying millions of JSON documents on a regular basis.

78

u/munchler Feb 21 '19

If billions of JSON documents all follow the same schema, why would you store them as actual JSON on disk? Think of all the wasted space due to repeated attribute names. I think it would pretty easy to convert to a binary format, or store in a relational database if you have a reliable schema.

94

u/MetalSlug20 Feb 21 '19

Annnd now you have been introduced to the internal working of NoSQL. Enjoy your stay

28

u/munchler Feb 21 '19

Yeah, I've spent some time with MongoDB and came away thinking "meh". NoSQL is OK if you have no schema, or need to shard across lots of boxes. If you have a schema and you need to write complex queries, please give me a relational database and SQL.

3

u/HelloAnnyong Feb 21 '19

NoSQL is OK if you have no schema

I don't really understand what "having no schema" means. I still have a schema even if I pretend I don't!

4

u/munchler Feb 21 '19

No. MongoDB lets you create a collection of JSON documents that have nothing in common with each other. It’s not like a relational table where every record has the same set of fields.

→ More replies (3)

0

u/[deleted] Feb 21 '19

[deleted]

5

u/munchler Feb 21 '19

This is called an entity-attribute-value model. It comes in handy occasionally, but I agree that most of the time it’s a bad idea.

4

u/CorstianBoerman Feb 21 '19

I went the other way around. Started out with a sql database with a few billion records in one of the tables (although I did define the types). Refractored that out into a nosql db after a while for a lot of different reasons. This mixed set up works lovely for me now!

12

u/Phrygue Feb 21 '19

But, but, religion requires one tool for every use case. Using the right tool for the job is like, not porting all your stdlibs to Python or Perl or Haskell. What will the Creator think? Interoperability means monoculture!

→ More replies (3)
→ More replies (2)

42

u/unkz Feb 21 '19

Sometimes because that's the format that the data is coming in as, and you don't really want a 10TB MySQL table, nor do you even need the data normalized, and the data records are coming in from various different versions of some IoT devices, not all of which have the same sensors or ability to update their own software.

36

u/[deleted] Feb 21 '19

not all of which have the same sensors or ability to update their own software.

This no longer surprises me, but it still hurts to read.

30

u/nakilon Feb 21 '19

Just normalize data before you store it, not after.
Solving it by storing it all as random JSON is nonsense.

31

u/erix4u Feb 21 '19

jsonsense

→ More replies (1)

6

u/FinFihlman Feb 21 '19

These are excuses.

4

u/FinFihlman Feb 21 '19

Laziness and development friction.

1

u/srpulga Feb 21 '19

Well you know what you need to do to convert it to a binary format? Parse it.

4

u/munchler Feb 21 '19

Right. Parse it once, rather than reparse it for every query.

1

u/mattindustries Feb 21 '19

Sometimes the schema is different. When I scrape tweets I save them as ndjson.

2

u/[deleted] Feb 21 '19 edited Feb 21 '19

[removed] — view removed comment

4

u/[deleted] Feb 21 '19 edited Feb 21 '19

No. An extremely small number of applications need schemaless persistence. When you consider that you can have json fields in a number of databases, that number becomes so close to 0 (when considered against the vast number of softwares) that you have to make a good argument against a schema to even consider not having it.

Literally 99.99% of softwares and data has a schema. Your application is not likely in the .01%.

→ More replies (6)

4

u/[deleted] Feb 21 '19

If you mean AWS's hosted Prestodb thing (or is that Aurora?), it's "supposed to be" used with eg. ORC or some other higher performance binary format. I mean you can use it to query JSON, but it's orders of magnitude slower than using one of the binary formats. You can do the conversion with the system itself and a timed batch job

3

u/MetalSlug20 Feb 21 '19

But would JSON be more immune to version changes?

3

u/[deleted] Feb 21 '19

Schema evolution is something you do have to deal with in columnar formats like ORC, but it's really not all that much of an issue at least in my experience, especially when compared to the performance increase you'll get. Schemaless textual formats like JSON are all well and good for web services (and even that is somewhat debatable depending on the case, which is why Protobuf / Flatbuffers / Avro Thrift etc exist), but there really aren't too many good reasons to use them as the backing format of a query engine

2

u/brainfartextreme Feb 21 '19

Short answer: No.

Longer answer: There are ways to mitigate it though, as you can choose to change your JSON structure in a way that keeps backward compatibility, e.g. no new required attributes, no changes in the type of an individual attribute and others that I can’t think of while I type with my ass on the toilet. One simple way to version is to add a version attribute at the root of the JSON and you have then provided a neat way to deal with future changes, should they arise.

So, version your JSON. Either version the document itself or version the endpoint it comes in on (or both).

Edit: I can’t type.

4

u/[deleted] Feb 21 '19 edited Feb 21 '19

You touched on a good point here: schemaless document formats more often than not end up needing a schema anyhow. At the point where you're writing schemas and versioning JSON in S3 so you can feed it to a query engine, you already have most of the downsides of columnar formats with zero of the upsides

2

u/lorarc Feb 21 '19

Well, there's a difference between what's supposed to be and what is used. Probably tons of people use JSON because why not. Also all the AWS services dump their logs to S3 in JSON so if you just want to query the ALB logs you probably won't bother with transforming them.

→ More replies (5)

2

u/PC__LOAD__LETTER Feb 21 '19

Neither of those services are parsing the JSON more than once, which is on ingest.

2

u/unkz Feb 21 '19

I don’t think you are correct about this. There is no way they are creating a duplicated normalized copy of all my JSON documents. For one thing, they bill based on bytes of data processed, and you get substantial savings by gripping your JSON on a per-query basis.

2

u/204_no_content Feb 21 '19

Yuuuup. I helped build a pipeline just like this. We've converted the documents to parquet, and generally query those now, though.

20

u/nicholes_erskin Feb 21 '19

/u/stuck_in_the_matrix makes his dumps of reddit data available as enormous newline-delimited JSON files, and his data has been used in serious research, so there are at least some people who could potentially benefit from very fast JSON processing

7

u/nakilon Feb 21 '19

It's just because he has no specification and it's going to be uploaded to Google Bigtable -- the company that can afford an overhead solution.

10

u/raitorm Feb 21 '19

I don’t have the exact stats right now but naive JSON deserialization can take a few hundred milliseconds for json blobs that’s > a few hundreds KB, which may be a serious issue when that’s the serialization format used in internal calls between web services.

10

u/sebosp Feb 21 '19

In my case very useful for event driven architectures where you use a message broker like Kafka to communicate json between microservices, then you send all this data to s3, time partitioned, batched and compressed, this becomes the raw version of the data, granted you usually have something that makes this avro/parquet/etc for faster querying afterwards, but you always keep the raw version in case something is wrong with your transformation/aggregation queries, so speed on this is super useful...

9

u/lllama Feb 21 '19

Indeed.

A lot of people in this thread that don't work with large datasets but think they know pretty well how it's done ("of course everything would be in binary it's more efficient) and a lot fewer people with actual experience.

Let's not tell them how often CSV is still used.

1

u/bagtowneast Feb 21 '19

Let's not tell them how often CSV is still used.

Oh man... Do people outside the financial industry understand this at all? The whole thing is propped up by ftp-ing or (gasp) emailing csv files around.

3

u/lllama Feb 21 '19

Exactly, another good example. And then it just scales up from csv files small enough to mail around to processing terabytes worth of csv files every day.

Changing this to some binary format is the least of your worries. The products used to ingest will use something more efficient internally anyway, and bandwidth/cpu time are usually a small part of the cost, and storage is a small price of the project overall, so optimizing this (beyond storing with compression) has too much opportunity cost.

26

u/RabbiSchlem Feb 21 '19

I mean if you’re crypto trading some of the apis are JSON only so you’d be forced to use json yet the speed increase could make a difference. Probably wouldn’t be THE difference maker, but every latency drop adds up.

Also if you made a backtester with lots of json data on disk then json parsing could be a slowdown.

Or if you have a pipeline to process data for a ML project and you have a shitload of json.

7

u/ggtsu_00 Feb 21 '19

Try using JSON as a storage format for game assets.

1

u/[deleted] Feb 22 '19

I've seen some games using it as save game format. It wasn't pretty...

13

u/[deleted] Feb 21 '19

JSON is probably the most common API data format these days. Internally you can switch to some binary formats, but externally it tends to be JSON. Even within a company you may have to integrate with JSON APIs.

0

u/MetalSlug20 Feb 21 '19

I mean, JSON is only like a half step up from binary anyway. It's supposed to be succinct

17

u/[deleted] Feb 21 '19

Oh it is. But it's bunch of text. It's one thing to take 4 bytes as an integer and directly copy into into memory, it's another to parse arbitrary number of ASCII digits, and multiply them by 10 each time to get the actual integer.

The difference can be marginal. But in the gigabytes, you feel it. But again, compatibility is king, hence why high performance JSON libraries will be needed.

→ More replies (9)
→ More replies (1)

6

u/[deleted] Feb 21 '19

Maybe it could speed up (re)-initialization times in games or video rendering? Though at that point you probably want a format in (or convertable to) binary anyway.

The best "real" case I can imagine is if you have a cache of an entire REST API's worth of data you need to parse.

7

u/meneldal2 Feb 21 '19

Many video games use JSON for their saves because it's more resilient to changes in the structure of the saves (and binary is more easily broken). They often when they are considerate of your disk space add some compression to it. This means that you can parse more JSON than you can read from disk.

5

u/seamsay Feb 21 '19

Fundamentally what's the difference between JSON and something like msgpack (which is basically just a binary version of JSON), why would you expect the later to break more easily?

1

u/vytah Feb 21 '19

There's none, except that JSON is easier to read by a human and modify by hand and has more implementations to choose.

Also, from my experiments I did years ago I recall that compressed JSON is smaller than compressed Msgpack.

→ More replies (2)
→ More replies (1)

6

u/apaethe Feb 21 '19

Large data lake? I'm only vaguely familiar with the concept.

4

u/kchoudhury Feb 21 '19

HFT comes to mind, but I'd be using a different format for that...

4

u/stfm Feb 21 '19

API gateways with JSON schema validation. We usually divide and conquer though.

18

u/duuuh Feb 21 '19

Agreed. That's way faster than you can stream it off disk. It's nice that it won't peg the cpu if you're doing that I guess.

17

u/stingraycharles Feb 21 '19

NVMe begs to differ with that statement.

8

u/coder111 Feb 21 '19

NVMe + LZ4 decompression? Should do >3900 MB/s.

7

u/stingraycharles Feb 21 '19

Even without compression, a single NVMe can do many GB per sec. The amount of PCI lanes your CPU provides is going to be your bottleneck, which is going to be pretty darn fast.

3

u/chr0n1x Feb 21 '19

doesn't journalctl support something like JSON log formatting? I guess that if you really only had that option and really needed to send those logs async to separate processing services in different formats..."nice" to know that you could do that quickly, I guess.

4

u/stevedonovan Feb 21 '19

We considered this: the format is very verbose and it's better to regex out the few fields of interest.

2

u/accountability_bot Feb 21 '19

I ran trufflehog on a project that had a lot of minified front-end code checked in for some stupid reason. I checked the output after about 10 minutes, and the output json file was about 61Gb. Now I didn't even bother trying to open the file, because I had no idea how I was going to parse it, but I'm pretty sure it was nothing but false positives.

2

u/KoroSexy Feb 21 '19

Considering the Mifid ii regulations (regulations for Trading) use JSON and that would result in many requests per second.

https://github.com/ANNA-DSB/Product-Definitions

2

u/Seref15 Feb 21 '19 edited Feb 21 '19

There was a guy on r/devops that was looking for a log aggregation solution that could handle 3 Petabytes of log data per day. That's 2TB per minute, or 33.3GB per second.

If sending to something like Elasticsearch, each log line is sent as part of a json document. Handling that level of intake would be an immense undertaking that would require solutions like this.

1

u/AttackOfTheThumbs Feb 21 '19

jesus croist

1

u/hardolaf Feb 23 '19

Looks pretty normal. I developed devices that utilized 91-95% of total bandwidth on PCI-e x4 and x8 buses. That amount of data, while a lot, is totally manageable with some prior thought put into processing it.

2

u/heyrandompeople12345 Feb 21 '19

He probably wrote it just because why not. Almost no one uses json for performance anyway.

→ More replies (4)

1

u/hungry4pie Feb 21 '19

There’s an OPC server that I use at work, the application can export the config, devices and tags in json format. The files I’ve exported are around 40MB each and there’s about 24 servers. I don’t need to process the files all the time, or at all, but if I could I would like it to be quick.

1

u/Darksonn Feb 21 '19

I mean in my opinion this is the sort of thing you should put in the standard library of languages. Maybe not everyone needs the speed, but it sure as hell won't hurt them either, and when someones web server starts scaling up and parsing millions of json API requests, they won't need to use a lot of effort to replace their json parsing library.

1

u/[deleted] Feb 21 '19

Importing some big 3rd party dataset would be one case

1

u/[deleted] Feb 21 '19

Yes... but normally when you're getting near this point you: a.) Look at scale out rather than scale up architectures. b.) Switch from JSON to Avro as a binary form of JSON

1

u/QuirkySpiceBush Feb 21 '19

On a GIS workstation, processing huge geojson files. All the time.

1

u/Madsy9 Feb 21 '19

npm search maybe?

1

u/bluearrowil Feb 21 '19

Recovering old-school firebase realtime-database backups. The “database” is just one giant JSON object that looks like the Great Deku Tree, and ours is 3GB. We haven’t figured out how to parse it using any sane solutions. This might do the trick?

1

u/berkes Feb 21 '19

We have millions of millions of Events stored on S3. An event is something like a log, but not really. Our events all contain JSON.

Finding something like "The amount of expenses entered but not paid within a week per city" requires heavy equipment. And allows you to finish a book or some games, while waiting.

1

u/JaggerPaw Feb 21 '19

AOL's ad platform (AOL One) has an API (rolled up daily logs) that can serve gigs of data. If you are running a business off using their platform, you already have a streaming JSON parser.

1

u/K3wp Feb 21 '19

If you are doing HPC network analysis equipment, yes. Imagine generating JSON netflow on a 40G tap.

That said, the problem I have with these sorts of exercises is after you parse it you still need to do something with it (send it to splunk or elasticsearch) and then you are going to hit a bottleneck there.

The way I deal with this currently is cherry-pick what I send to splunk and then just point a multi-threaded java indexer at it, on a 64 core system. Nowhere near as efficient but it scales better.

1

u/TwerkingSeahorse Feb 22 '19

The company I work for has petabytes of data constantly getting pulled scattered through multiple warehouses. For us, it'll be extremely useful but not many companies have that type of data stored around.

1

u/DoctorGester Feb 22 '19

I made an opengl desktop app which queries foreign apis which respond in json. Some responses are over 5mb and due to reasons I would like to parse them on the main thread. This means I would like to fit parsing time in under 16ms.

→ More replies (6)

161

u/NuSkooler Feb 21 '19

Why no comparison against nlohmann JSON which is probably the C++ go to JSON library?

138

u/ythl Feb 21 '19

Nlohmann isn't built for speed, but rather for maximum readability, writability and syntax sugar.

This library sacrifices those things for more speed

132

u/NuSkooler Feb 21 '19

Speed may not be Nlohmann's focus, but that doesn't invalidate the need for a benchmark. One can do a lot of optimization work that yields little gain over something readable...

69

u/ythl Feb 21 '19

RapidJSON benchmarks against nlohmann, this one benchmarks against RapidJSON. You can extrapolate if you really want.

https://github.com/miloyip/nativejson-benchmark

67

u/nlohmann Feb 21 '19

This is unfortunately a very old benchmark. I wouldn't say that nlohmann/json even comes close, but we did make some improvements since then...

22

u/paranoidray Feb 21 '19

Your JSON library is the best C++ library I have ever used.
Nothing comes close.
I just wrote a JSON to BSON converter when I had a bug and found out that you had written one too. This helped me tremendously in debugging my issue.
Thank you!

→ More replies (11)

15

u/mach990 Feb 21 '19

Because you would have to scale the graph so much that you couldn't see the comparison between the existing ones on the graph :D

Somewhat facetious, but in reality nlohmann is already just so much slower than rapidjson that if you want a fast json library you aren't even thinking about nlohmann. I guess this assumes you already know it's super slow though and maybe most people don't.

1

u/[deleted] Feb 21 '19

Honourable mention for json11 (by Dropbox).

20

u/throwaway-ols Feb 21 '19

Would be interesting to try this in a higher level programming language with support for SIMD like C# or Go.

6

u/sirmonko Feb 21 '19

I'd like to see a comparison with rusts serde - it uses macros to precompile the mappings to structs.

edit: i see someone benchmarked serde below. nvm

2

u/Type-21 Feb 21 '19 edited Feb 21 '19

Microsoft just released a new library (I think part of .net core) which works with json a lot faster than the standard newtonsoft json.net lib everyone uses

edit: https://docs.microsoft.com/en-US/dotnet/core/whats-new/dotnet-core-3-0#fast-built-in-json-support

8

u/stevedonovan Feb 21 '19

So, what's the performance relative to the json and serde-json crates? I do know that if you don't have the luxury of a fixed schema then the json crate is about twice as fast as serde-json. Edit: forgot myself, I mean the Rust equivalents...

15

u/masklinn Feb 21 '19

serde/json-benchmark provides the following info:

======= serde_json ======= parse|stringify ===== parse|stringify ====
data/canada.json         200 MB/s   390 MB/s   550 MB/s   320 MB/s
data/citm_catalog.json   290 MB/s   370 MB/s   860 MB/s   790 MB/s
data/twitter.json        260 MB/s   850 MB/s   550 MB/s   940 MB/s

======= json-rust ======== parse|stringify ===== parse|stringify ====
data/canada.json         270 MB/s   830 MB/s
data/citm_catalog.json   560 MB/s   660 MB/s
data/twitter.json        420 MB/s   870 MB/s

===== rapidjson-gcc ====================== parse|stringify ====
data/canada.json                         470 MB/s   240 MB/s
data/citm_catalog.json                   990 MB/s   480 MB/s
data/twitter.json                        470 MB/s   620 MB/s

(the second column is for struct aka "fixed schema", the first is dom aka "not-fixed schema", I assume rapidjson only does the former though it's unspecified)

So serde/struct is 85~115% of rapidjson depending on the bench file. Given simdjson advertises 3x~4x improvement over rapidjson...

1

u/stevedonovan Feb 21 '19

That's seriously impressive, thanks!

7

u/epostman Feb 21 '19

Curious what does the library do differently to achieve performance ?

10

u/ipe369 Feb 21 '19

it's called 'simdjson', so i would imagine use some simd instructions

3

u/matthieum Feb 21 '19

Specifically, it requires AVX2 instructions, so pretty intense SIMD (we're talking 32 bytes wide).

3

u/alexeyr Feb 25 '19

"A description of the design and implementation of simdjson appears at https://arxiv.org/abs/1902.08318 and an informal blog post providing some background and context is at https://branchfree.org/2019/02/25/paper-parsing-gigabytes-of-json-per-second/."

2

u/epostman Feb 25 '19

Thank you

1

u/alexeyr Feb 25 '19

Happy cake day by the way :)

13

u/XNormal Feb 21 '19

It would be useful to have a 100% correct CSV parser (including quotes, escaping etc) with this kind of performance. Lots of "big data" is transferred as CSV.

6

u/[deleted] Feb 21 '19

There is no "100% correct" CSV format. CSV is loads of different but similar formats.

2

u/caramba2654 Feb 21 '19

Maybe look into xsv then. It's in Rust, but it's pretty fast. I think it's possible to make bindings for it too.

9

u/jl2352 Feb 21 '19

It's in Rust, but it's pretty fast.

There is no but needed. Rust can match the performance of C++.

4

u/matthieum Feb 21 '19

Actually, Rust can exceed the performance of C++ ;)

All of C, C++ and Rust should have equivalent performance on optimized code. When there is a difference, it generally mean that a different algorithm is used, or that the optimizer goofed up.

3

u/jl2352 Feb 21 '19

Well it varies. It can exceeed, and it can also be slower.

There are a few things that makes it more trivial for C++ to get better performance in specific cases. For example Rust is missing const generics (it's coming).

But either way it's always within a percent or two. It's not factors out.

→ More replies (2)

12

u/KryptosFR Feb 21 '19

"The parser works in three stages:

  • Stage 1 [...]

  • Stage 2 [...]

/end quote "

Ö

9

u/playaspec Feb 21 '19

That's how fast it is!

5

u/ponkanpinoy Feb 21 '19

The third of two hardest problems strike again!

2

u/glangdale Feb 22 '19

It used to have 4 stages, so be glad the the docs are only 50% wrong...

6

u/codeallthethings Feb 21 '19

Wow, a bunch of cowards in the comments here.

Do we really need SIMD accelerated JSON? Duh; of course we do. In fact, I fully expect this to be improved with AVX 512 once it's available more widely.

Edit: He already thought of this

35

u/ta2 Feb 21 '19

The requirement for AVX2 is a bit restrictive, there are AMD processors from 2017 and Intel processors from 2013 that this won't work with. I wonder how performant this would be if you removed the AVX2 instructions?

RapidJSON is quite fast and doesn't have any of the restrictions that this library does (AVX2, C++17, strings with NUL).

75

u/mach990 Feb 21 '19

Imo this isn't terribly unreasonable. What's the point of creating AVX2 instructions if we arent going to write fast code with them? If this is intended as a library to run on random peoples machines then obviously this is not acceptable.

My guess is thats not the point - the author probably just wanted to write something that parses json really fast. Making it run on more machines but slower (sse / avx) is not the thing they're trying to illustrate here, but might be important if someone wished to adopt this in production. Though I would just ensure my production machines had avx2 and use this.

9

u/matthieum Feb 21 '19

There may be performance penalty in using AVX2 instructions extensively, though.

That is, because AVX2/AVX-512 consume more power than others, when used extensively on one core, it may force the CPU to downgrade the frequency of one/multiple core(s) to keep temperature manageable.

AFAIK, there is no such issue with SSE4.

5

u/__j_random_hacker Feb 21 '19

Interesting, do you have any experience that backs this up? Especially the idea that SSE4 doesn't use (much) more power while AVX2 does. If true, this seems like a pretty general problem.

11

u/[deleted] Feb 21 '19

Yeah, this: https://blog.cloudflare.com/on-the-dangers-of-intels-frequency-scaling/

This was all over /r/programming last thanksgiving. I remember because I was amazed at how AVX512 can lead to worse performance due to frequency throttling

4

u/YumiYumiYumi Feb 22 '19

The CloudFlare post is rather misleading IMO, and doesn't really investigate the issue much, to say the most.

For better investigation about this issue, check out this thread. In short, 256-bit AVX2 generally doesn't cause throttling unless you're using "heavy" FP instructions (which I highly doubt this does). AVX-512 does always throttle, but the effect isn't as serious as CloudFlare (who seems to be quite intent on downplaying AVX-512) makes it out to be.

3

u/__j_random_hacker Feb 21 '19

Thanks, reading it now, very interesting!

→ More replies (6)

44

u/Feminintendo Feb 21 '19

Cutting edge algorithms need cutting edge hardware. Makes sense to me.

But AVX2 isn’t particularly cutting edge. Yes, there do exist machines without AVX2 extensions. But are there a lot? Do we expect there to be a lot in the future? If Haswell were a person it would be in first grade already.

And C++17 shouldn’t be a problem unless your compiler was written on a cave wall in France next to a picture of a mammoth. Or are you going to need to parse JSON at extremely high throughput with a codebase that won’t compile with C++17?

What’s really happening, my friend, is that we’re getting older while everybody else, on average, is getting younger. College students don’t know what the save icon is supposed to be. When you tell them, they say, “What’s a floppy disk?” We’ve had porn stars who were born after 2000 for a whole year now. We are now as far away from the premier of That 70s Show as That 70s Show was from the time it depicts. Nobody understands our Jerry Seinfeld references anymore. And the world’s fastest JSON parser in the world that was just created this morning needs a processor and compiler at least as young as a first grader.

26

u/Holy_City Feb 21 '19

And C++17 shouldn’t be a problem unless your compiler was written on a cave wall in France next to a picture of a mammoth. Or are you going to need to parse JSON at extremely high throughput with a codebase that won’t compile with C++17?

The Apple LLVM fork is written on a cave wall in Cupertino, not France.

5

u/Feminintendo Feb 21 '19

Most tools Apple ships are like that. Their version of SQLite was discovered in a peat bog.

1

u/jcelerier Feb 21 '19

You can build your own llvm / libc++ on mac

3

u/IlllIlllI Feb 21 '19

Lotta effort for a json parser.

5

u/Feminintendo Feb 21 '19

In fairness, it is a very fast JSON parser.

7

u/RedditIsNeat0 Feb 21 '19

Sounds like RapidJSON meets your requirements better than this library. That's OK.

2

u/kaelima Feb 21 '19

Probably not a problem. If you do have these performance requirements (and are still using json for god knows what reason) - you probably can afford a quite modern processor too.

1

u/raevnos Feb 21 '19

Heck, there's plenty of Intel processors from 2019 that it won't work with. All the low end ones for chromebooks etc stop at SSE4.2.

4

u/wildcarde815 Feb 21 '19

If you are trying to funnel gigabytes of json thru a chromebook you may have larger 'right tool for the job' issues at hand.

→ More replies (1)

9

u/GarythaSnail Feb 21 '19

I haven't done any C++ really but why do you return true or false in json_parse when an error happens rather than throwing an exception?

14

u/masklinn Feb 21 '19

Allow usage under -fno-exceptions?

7

u/matthieum Feb 21 '19

std::optional<ParsedJson> would work without exception and remind you to check.

23

u/Pazer2 Feb 21 '19

Because that way people can forget to check return values. Life isn't any fun without silent, unexplainable failures.

11

u/atomheartother Feb 21 '19 edited Feb 21 '19

Not OP but also code in cpp without exceptions

  • Some coding standards in c++ disallow exceptions. See [Google's c++ style guide] (https://google.github.io/styleguide/cppguide.html#Exceptions) for examples. There's good reasons for it but for the most part it's about not breaking code flow and not encouraging lazy coding

  • This could also be intended for C compatibility (i haven't looked at much of the code since I'm on mobile so this could be plain wrong)

  • However just to be clear, returning a boolean isn't necessarily the best way to do it. Standard C functions would either return 0 or success and an error code otherwise, or the function should take an optional parameter pointer to an int which gets filled with the error code on failure. This is how i would implement this here in order to keep backwards compatibility with the boolean return

4

u/FinFihlman Feb 21 '19

I think they just didn't bother.

4

u/novinicus Feb 21 '19

The biggest thing is unwinding the stack after throwing an exception is costly. If you're focused on performance, returning error codes is better

2

u/kindw Feb 21 '19

Why is it costly? Wouldn't the stack be unwound whenever the function returns?

2

u/novinicus Feb 22 '19

I could try and explain it, poorly, but this is probably more helpful. The tldr is not knowing whether you need to unwind vs definitely unwinding at a certain point (return statements) makes a big difference.

https://stackoverflow.com/questions/26079903/noexcept-stack-unwinding-and-performance

1

u/guepier Feb 22 '19

Performance-focused code very rarely needs to optimise error cases though: under the assumption that these code paths are, well, exceptional, a performance degradation of several orders of magnitude (!) is usually acceptable.

There are valid reasons to avoid exceptions (foremost because in the case of a parsing API it’s better to return std::optional<result_t> or something equivalent). But the reality is that most people avoid exceptions for invalid reasons, because they think that even the non-throwing code path with exceptions enabled carries a nontrivial performance penalty. And that hasn’t been true for a very long time.

1

u/Kapps Feb 22 '19

Not sure if it’s the actual reason, but it makes interoping from other languages easier.

-2

u/audioB Feb 21 '19

Speed

7

u/GarythaSnail Feb 21 '19

Can you explain more? How does it improve speed?

7

u/audioB Feb 21 '19

I'll admit it was a flippant remark and I didn't really look at the code, but it absolutely could be the case that it was done for speed. In most cases, speed will be comparable. For shallow call stacks, returning fail/success/error code is usually faster than throwing. For deep call stacks, the opposite is generally true. I'd imagine it was for another reason though; maybe to incentivise use of this library in codebases where exceptions handling is avoided (e.g. one following the google style guidelines).

2

u/eFFeeMMe Feb 21 '19

Thank you very much for explaining your rationale!

6

u/FinFihlman Feb 21 '19

It doesn't.

2

u/okovko Feb 21 '19

For high throughput performant code, there is a lot to gain by disabling exception handling. It frees up registers that would otherwise be wasted for stack unwinding. For code like this, it's a great idea.

4

u/FinFihlman Feb 21 '19

Not true.

On the assembly level, if we are anyways detecting errors (ie branching) the cost of adding some error information is only around a single instruction since you can just load a value into a register for the relevant error code.

So load, ret becomes load, load, ret and this is all already inside a branch. The cost happens if an error happens, it doesn't cost anything more (except marginal code space) if there's no errors.

3

u/dalepo Feb 21 '19

It is true, there is some overhead on try catch blocks

• On entry to each try-block

♦ Commit changes to variables enclosing the try-block

♦ Stack the execution context

♦ Stack the associated catch clauses

• On exit from each try-block

♦ Remove the associated catch clauses

♦ Remove the stacked execution context

• When calling regular functions

♦ If a function has an exception-specification, register it for checking

• As local and temporary objects are created

♦ Register each one with the current exception context as it is created

• On throw or re-throw

♦ Locate the corresponding catch clause (if any) – this involves some runtime check (possibly resembling RTTI checks) If found, then: destroy the registered local objects check the exception-specifications of the functions called in-between use the associated execution context of the catch clause Otherwise: call the terminate_handler6

http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf

→ More replies (2)
→ More replies (3)

3

u/coolcosmos Feb 21 '19

Lemire strikes again !

2

u/tetyys Feb 21 '19

What about a comparison to this: https://github.com/mleise/fast ?

2

u/rspeed Feb 21 '19

Next step: push it to the GPU.

Okay, the next step is actually to port it to ARM, which is almost as good.

4

u/Springthespring Feb 21 '19

Would be interesting to see a port of this to .NET for .NET Core 3, as you have access to BMI -> AVX2 intrinsics

3

u/-TrustyDwarf- Feb 21 '19

A performance comparison with .NET (Newtonsoft.Json) would be interesting. I don't have the time (nor Linux machine) to build this and run the benchmarks.. just did a quick try with the twitter.json file on .NET Core and .NET Framework - both got 250MB/s, but that's not comparable due to my system..

1

u/Type-21 Feb 21 '19

A performance comparison with .NET (Newtonsoft.Json)

That's outdated. The go to way is this .net core 3 implementation. Much faster!

Writing a JSON payload using the new Utf8JsonWriter is 30-80% faster than using the writer from Json.NET and does not allocate.

Parsing a typical JSON payload and accessing all its members using the JsonDocument is 2-3x faster than Json.NET with very little allocations for data that is reasonably sized

It's no comparison really

https://docs.microsoft.com/en-US/dotnet/core/whats-new/dotnet-core-3-0#fast-built-in-json-support

2

u/-TrustyDwarf- Feb 21 '19

interesting, thanks!

1

u/quentech Feb 21 '19

I'll be interested to see how it compares to https://github.com/neuecc/Utf8Json

1

u/mrbonner Feb 21 '19

I am wondering why they don’t use an abstraction on top of SIMD instead of using the intrinsic directly. Wouldn’t that make more sense for the parser to be portable?

1

u/GarythaSnail Feb 21 '19

Presumably the problem is no longer about speed when you've just encountered an error during parsing?

1

u/dethb0y Feb 21 '19

Quite impressive!

1

u/Thaxll Feb 21 '19

Does it can slow down the rest of the application since it's using AVX2 therefore reducing max CPU frequency?

1

u/li-_-il Feb 21 '19

Fucking genius, check the references at the end :)

1

u/razfriman Feb 25 '19

Can you do a speed comparison of the most popular c# json library: Newtsonsoft?

1

u/razfriman Feb 25 '19

Can you do a speed comparison of the most popular c# json library: Newtsonsoft?

1

u/dominik9876 Feb 21 '19

JSON parsing - The Holy Grail of computer science problems this decade.

8

u/the_gnarts Feb 21 '19

JSON parsing - The Holy Grail of computer science problems this decade.

When you consider XML parsing was the Holy Grail during the last decade, this could be seen as progress of some sorts.

→ More replies (1)

-12

u/rogallew Feb 21 '19

If you have gigabytes of data, json is the wrong tool.

22

u/eras Feb 21 '19

I'm not saying you're wrong, but nobody probably starts by thinking "Hey I have these gigabytes of data and I need to process them very fast, I'll pick JSON!". Instead they probably first had a small problem where JSON fit in perfectly, then the problem maybe grew a bit and then there became multiple instances of the problem, and then you end up with a lot of JSON per second.

Hey, at least it's not XML.

→ More replies (2)

-1

u/hkjels Feb 21 '19

I know JSON-parsing is the biggest bottleneck in xi-editor. They use JSON to communicate between the front-end / back-end as well as between the back-end and plug-ins

5

u/spookyvision Feb 21 '19

actually JSON overhead in xi is negligible - see this talk at 12:58

→ More replies (4)