[HN Gopher] Parsing gigabytes of JSON per second
___________________________________________________________________
Parsing gigabytes of JSON per second
Author : signa11
Score : 101 points
Date : 2021-10-21 06:51 UTC (2 days ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| stkdump wrote:
| If your dataset is large enough to benefit from such a
| hyperoptimized parser you might not benefit from the human
| readability anymore, which is the main reason for the required
| CPU cycles on the first place. So you should probably use a
| feature-equivalent binary format that is optimized for parsing
| speed. The only reason to use json then is that it is the lingua
| franca. So we as an industry should figure out which of the 100s
| of binary variants of json-similar formats has the same
| capabilities and unite around it.
| ec109685 wrote:
| Why do you think human readable adds appreciable overhead? If
| you want to create a flexible interchange format, that is going
| to require some sort of parse step whether the format is text
| or binary.
|
| That said, probably FlatBuffer would be even an optimized json
| parser, but json is crazy fast if the parser takes advantage of
| all modern processor optimizations.
| koolba wrote:
| There's no way reading a series of text is going to beat a
| machine native byte representation, particularly for things
| like range limited integers. If you plan things right with
| proper word alignment, you don't even have to copy the data
| to process it as you can directly dereference the byte
| offsets as machine native ints.
| EwanToo wrote:
| I largely agree, but most modern binary formats are more rigid
| with schemas and types.
|
| If you want the flexibility of JSON, I'm not sure you'll end up
| with something massively different from gzipped JSON
| the8472 wrote:
| Converting a text format to a compact in-memory data
| structure takes extra CPU cycles. (de)compression takes extra
| cycles. The point of using a binary format is to achieve the
| same result while avoiding that overhead. For some data
| formats compression also has the downside that it prevents
| seeking.
| Waterluvian wrote:
| That's an interesting thought. I am now very fascinated by
| what kind of data would be gigs in size but would need the
| flexibility of JSON.
| maccard wrote:
| Datasets are not always provided by you; if your data
| source outputs json it doesn't matter why. Also just
| because your volume of data is measured in gigabytes, that
| doesn't mean it's a singular stream. As an example you
| could be handling tens of thousands of small requests.
| lifthrasiir wrote:
| JSON doesn't allow any custom type, so it is not "flexible"
| per se. Therefore you only need a format that supports the
| JSON data model and pretty much nothing else; CBOR [1] for
| example almost surely fits the bill.
|
| [1] https://cbor.io/
| asdfge4drg wrote:
| uh yes that would work perfectly. https://xkcd.com/927/
| SigmundA wrote:
| Text is a binary format that just happens to have decoders
| (ASCII, UTF8 etc) everywhere in order to parse and display it
| to humans along with more specific parsers for things like
| JSON.
|
| I wish we could all settle on a binary structured format thats
| not limited to text encoding and more like JSON (key value)
| that basically everyone uses with real data types (efficiently
| encoded numbers, dates, binary , etc).
|
| Text files would just be something like { contentType:
| "text/plain" content : "text here" } while an image could be {
| contentType: "image/jpeg", content: <real binary data not
| base64> } you could also add whatever other metadata you want
| and all of it is retained and easily parseable. Other more
| structured formats obviously wouldn't just be a blob for
| content and every system out there would have a structured
| binary format viewer/editor just like there are text viewers
| and editors now.
|
| Sqlite is kinda used this way and has some nice properties like
| indexes and transactions but is relational instead of
| hierarchal which can be good and bad, not as straight forward
| to just view or navigate. Protobuf is another used quite a bit
| now, honestly I don't care just something everyone agree upon
| that can encode more structure efficiently but still can be
| easily inspected everywhere.
|
| Doubt this will any time soon but it does seem inevitable in
| the long run that we figure out a way to send data between
| system and what a string, number, date etc is and stop having
| text encoding and escaping issues.
| pablodavila wrote:
| Something like UBF might be interesting to you:
| https://ubf.github.io/ubf/
| kortex wrote:
| I don't know why the ASCII characters for record and field
| separators don't get more love. That is what they are there
| for. My suspicion is because they aren't type-able, so people
| rarely encounter them.
| SigmundA wrote:
| Still have the issue of binary data encoding as well since
| the data will have those bytes in it so they need to be
| escaped vs a format that defines how to encoding binary as
| is efficiently (length delimited).
| legulere wrote:
| You mean like CBOR?
|
| https://en.wikipedia.org/wiki/CBOR
| SigmundA wrote:
| Sure, looks good, plenty to choose from, just need to get
| everyone to agree on one.
|
| Although I do like ones that have some concept of a schema
| to reduce repeated key size and allow validation.
| strictfp wrote:
| There's also Minecraft NBT. It's a bit obscure but quite
| nice. https://minecraft.fandom.com/wiki/NBT_format
| sitkack wrote:
| You should put your NBTs inside of a netstring,
| https://en.wikipedia.org/wiki/Netstring
| orasis wrote:
| protocols have two sides - a producer and a consumer. The
| consumer often doesn't have control of the producer, especially
| in the case of analytics.
| cogman10 wrote:
| I've gotta say, I don't really understand why the industry is
| so in love with human readability for computer to computer
| interaction.
|
| It seems like a notion that started in the early internet and
| just refuses to die.
|
| Everything on the internet is minified and compressed at this
| point, so the entire idea of "human readability" left the
| station years ago. Yet I'll still see a primary complaint
| against the likes of http2+ being "it's a binary format! On
| NO!".
|
| JSON seems like a similar relic. We use it not because it's
| fast, but because we like the idea that it's easy to decode
| (Even if in practice that almost never happens).
| NicoJuicy wrote:
| I regulary get requests from QA why something is not working.
| Just watching the dumped request and seeing what is wrong (
| eg. Configuration) is a bless.
| djbebs wrote:
| Makes it easier to troubleshoot.
| AYBABTME wrote:
| It's the same idea as designing hardware for repairability.
| Sure you can repair something that's welded on, but it's much
| easier if it's bolted through instead.
| cogman10 wrote:
| It's not the same.
|
| You are almost certainly passing these through tools (even
| built into the browser) that are doing extra processing to
| make it more readable.
|
| Let's assume, for example, CBOR ends up taking over JSON.
| Do you not think browsers wouldn't have a CBOR parser to
| make it more readable?
|
| This isn't bolt vs welding, this is bolt vs bolt with a
| washer. Yes there's a small extra step, but not some sort
| of insurmountable hurdle.
| secondcoming wrote:
| Indeed, out of all the trillions of HTTP requests that are
| communicated every day how many get read by a human. Not a
| lot, yet that's the use-case it's optimised for.
|
| Those on the cloud should compute how much HTTP headers count
| towards their traffic egress bill.
|
| Everyone is fine with human-readable as long as it's in
| English.
|
| Binary should be the default. If writing a binary to human
| decoder is too much for you, you're in the wrong job.
| yardstick wrote:
| HTTP/2 uses a binary encoding instead of text for
| performance reasons. I prefer the text version myself as
| it's easier to write simple tools for (quick clients,
| telnet based queries, etc).
| nyanpasu64 wrote:
| A binary format you understand is easier to parse than a text
| format, but a binary format you don't understand is harder to
| learn (from reverse-engineering files) than a text format
| following certain conventions (HTML/JSON is more familiar to
| readers than PDF or Punycode). And text formats are easier to
| extract information out of fragmentary or corrupted documents
| than binary (or worse yet compressed) formats.
| dan-robertson wrote:
| Well json is everywhere so I think it's mostly too late for
| companies to change all their internal protocols and apis to
| not use it. And note that a big advantage of json is that many
| applications can process it without a schema--you don't need to
| know that the username field is a certain length, type and at a
| particular place. It is also easier to know if json is valid
| than a random binary format. The advantage of something like
| the algorithm here is that you can put it into your shared
| libraries[1] to get a speed up for free. If you spend (making
| up numbers) 1% of your cpu time parsing json and this speeds
| things up 4x (note: possibly more because other parsers get
| more of an advantage in micro-benchmarks from the branch
| predictor) then if you have sufficiently many servers you can
| cut your server bill by 0.75% which can be a large amount of
| money for the largest companies.
|
| [1] this won't work for all languages as the OP parses json
| into a flattish object where fields may be looked up rather
| than some language-specific data structures (like js objects or
| python dicts or whatever)
| m_mueller wrote:
| yep. once you've had to deal with XMLs that come in _without_
| a schema alongside, you start appreciating getting a JSON. at
| least that properly distinguishes strings, nulls, integers
| and decimals.
| agent327 wrote:
| Your dataset could, instead of gigabytes in a single request,
| also be a very large number of small requests all sent to a
| server to handle. Each message might be easily human-readable,
| yet the whole system would benefit from expedient processing.
| Zababa wrote:
| > If your dataset is large enough to benefit from such a
| hyperoptimized parser
|
| I don't understand that point. Is there an overhead in starting
| the parsing, which makes regular parsing faster unless you have
| a large JSON file? If not, why wouldn't you want faster JSON
| parsing?
| lumost wrote:
| Most languages have a built in parser these days, pulling in
| a c dep can be painful in many build tools and languages. The
| csimdjson api is sufficiently different to not as idiomatic.
| Most language json parsers are very fast already.
|
| Personally I'm using csimdjson in a project with 100s of TB
| of json to burn through. This data should not be json
| formatted, but migrating away from json would require
| modifications to hundreds of different systems.
| Zababa wrote:
| That's a fair point. Though this could probably be used in
| interpreters/JIT/C++ projects, which is already a lot. And
| this gives a good template on how to optimize JSON parsing
| for other projects.
| pickledish wrote:
| I guess an example would be along the lines of protobufs, e.g.
| Cap'n Proto
|
| https://capnproto.org/
|
| (which I have never used but really enjoy just for its charming
| website design alone)
| Epa095 wrote:
| If the improvements scale, you can still get benefit for
| smaller use cases. And even if each json is small, if you have
| millions of them the tiny improvements add up. We parse quite a
| bit of json, we fetch and store json regularly from external
| api's. We can't ask for a different format, and for each of the
| individual requests json makes sense, the response is only a
| few hundred kbs. But over time there is a lot of data. We
| convert them to parquet, but each json needs to be read at
| least once.
| secondcoming wrote:
| You could also potentially use plain CSV or TSV files. Not
| sexy, but they work.
| kozziollek wrote:
| Oh yes, CSV! Sure! Separated with commas or semicolons? With
| quotes or without? What decimal separator?
|
| No thanks.
|
| Use Protobufs, Parquet, Avro, etc.
| tfsh wrote:
| Protobufs would be a good contender here
| ec109685 wrote:
| Protobuf parsing is slower than an optimized json library,
| e.g. https://jsoniter.com/
| audray wrote:
| I've been hacking with rust & wasm lately and am seeing
| positive results. Flat buffers are also promising if you
| are working with larger data.
| kabber wrote:
| Fast JSON parsers are all fine and good, but take such benchmarks
| with a grain of salt. JSON, like any format, is useless unless
| you do something meaningful with it - populate a database, verify
| the result, or transform it in some useful way for the task at
| hand. Many of these faster JSON DOM-style parsing libraries store
| key/value pairs in lists or arrays because it's the most
| efficient way to do so. But they aren't great at lookup speed. If
| the JSON parse library is event based, i.e. SAX-style, you have
| to store it somewhere, and this takes CPU as well.
| throwawaygal7 wrote:
| This is pretty great.
|
| Some folks in the thread are suggesting using a binary format,
| and that's certainly a good idea for some.
|
| My business sells software that collects moderately sized
| (10-100TB/day) , and this data is collected as PROTOBUF. The
| format is great, and coordinating the backend and client side
| stuff with protobuf is bliss.
|
| However, we store the data in various relational and document
| databases. Neither of those use protobuf...
|
| Most importantly, it's business critical to be able to stream
| this data to data lakes where it can be read by humans. None of
| the options are going to support protocol buffers, you're either
| going to have to write a parser (impossible for some) or
| transform to JSON before ingest (fairly expensive due to some
| poor choices in how to represent various fields).
|
| It was a sound technical decision to use protoc , and a terrible
| choice for the business.
|
| I think it would have been much better to use avro, still benefit
| from schemas but push the work of marshaling JSON back to
| clients...
| wodenokoto wrote:
| I know it's utopia, but I still can't help but ask, why can't
| we have protobuffs or some other binary format with readers
| integrated into normal systems the way everything has a Json
| reader.
|
| I mean, stuff like "double click on .protobuff file and it
| opens in notepad and looks like json or whatever. When you
| click save it gets serialized back to protobuff.
| MayeulC wrote:
| IIRC (I could be wrong on this one) protobuf isn't really a
| specification, it's a single implementation, and is quite
| hard to reimplement.
|
| Here's a short comparison of serializing formats:
| https://drewdevault.com/2020/06/21/BARE-message-
| encoding.htm...
| morelisp wrote:
| Regarding the wire format specifically, it's not fully
| formalized but there's dozen implementations, not all of
| them from Google. You could hack together a basic serde for
| a particular language in an afternoon, in some respects
| much more easily than you could JSON. Most of the
| engineering work is in the schema compilers.
| heavenlyblue wrote:
| But in order to semantically read protocol buffer files
| one needs to compile the schema files...
| morelisp wrote:
| The degree you "need" to support the full schema format
| depends entirely on the language you're using. In Go you
| only need the annotated structures, or in Java you only
| need a mapping between field number and name, and the
| languages' own reflection capabilities can handle the
| rest.
|
| Yes, strings, bytes, and substructures all appear in the
| same in the wire format. Just like strings, bytes, and
| dates all appear the same in JSON. If you're trying to
| write a generic protobuf viewer like wodenokoto suggests,
| you can make reasonable assumptions about the contents
| 99% of the time based on the data, and show the user
| multiple options if you're not sure. There are already
| lots of tools that do this, but none very well integrated
| into mainstream development workflows.
| matja wrote:
| Tricky part about implementing that is that the protobuf
| wire-format alone doesn't contain enough information to
| unambiguously represent the real data types, it also needs
| the schema (.proto file) to do that.
|
| For example, in the wire-format, a string and a sub-message
| are encoded as the same type (a blob - varint + sequence of
| bytes), but using the schema they are clearly interpreted
| differently.
|
| Sure, it is possible to make a self-describing protobuf
| message which includes the schema in protobuf representation,
| but that is a special-case.
| uDontKnowMe wrote:
| What about Avro then?
| gravypod wrote:
| I've written translation layers for such systems and it's not
| too bad. See this project from $job - 1:
| https://github.com/CaperAi/pronto
|
| It allowed us to have a single model for storage in the DB, for
| sending between services, and syncing to edge devices.
| implying wrote:
| (2019)
| otrahuevada wrote:
| Having some trouble figuring out how to benefit from this.
|
| I can't think of a scenario where JSON handling is our
| bottleneck; almost all of the massive-data-handling tasks in my
| entire career have usually been handled by our database of
| choice.
|
| Largest individual JSONs we've had to handle like on import tasks
| and such were about 300mb, which proved extremely easy to manage
| with stuff like JSONStream -I think we used a hand-rolled
| analogue back then but JSONStream is actually pretty cool, check
| it out-
|
| What is the use case here? data lakes?
| sethev wrote:
| The use-case for a more efficient JSON parser is exactly the
| same as the use-case for a less efficient one. They're doing
| the same thing.
|
| Daniel Lemire does a ton of performance research like this.
| He's an unusual case of a professor who publishes fully working
| source code.
|
| There's a good chance that your database of choice uses some of
| his stuff or was influenced by his research.
| Zababa wrote:
| If you're at a very large scale, maybe the reduced server cost
| by parsing JSON this way can "finance" an engineer? If you're
| starting to reach the limits of JSON, maybe it could also help
| you avoid a transition for a while longer? At least those are
| the obvious cases for me.
|
| If it's a drop-in replacement for other JSON parsers, I think
| this could have a huge impact. There is a lot of value to gain
| by optimizing the fundamentals
| llamajams wrote:
| I'm working on an embedded vision/navigation system. The core
| app itself generates about 50mb a minute of metadata alone in
| the simplest scenario. It's supposed to be long running system.
| There is one case that generates just over a TB.
|
| Now you may say we should optimize this or that but I'm not an
| architect and I have no say, and it's just what I gotta deal
| with:(
| estebarb wrote:
| I worked on a database engine that uses JSON as communication
| protocol. Sure, most messages are small, but for a system
| processing JSONs 24/7 it quickly sums a lot.
|
| The main issues see had with our codec was memory allocation
| and the big number of "if" in the code.
|
| I tried to use simdjson, but there were concerns at that time
| about portability and long term support. It's nice to see that
| in retrospective we were wrong.
| IshKebab wrote:
| Yeah if you have a situation where JSON gets into the megabytes
| you should definitely stop using JSON! I recommend SQLite for
| large datasets that you need to put in a file.
|
| I guess if you don't have a choice then it might become a
| bottleneck. Parsing 300 MB of data can be very slow.
|
| But even with small JSON messages it can become a bottleneck,
| e.g. check out the Xi editor's issues. They thought it wouldn't
| be a bottleneck and then found that sound languages don't have
| insanely optimised JSON parsers like this. Boom. Bottleneck.
| suction wrote:
| I worked for small(ish) music supplier of Spotify, not a major
| label like Universal etc. at all - they were receiving a daily
| 3-4 Gb JSON file (uncompressed) of yesterday's activity. Things
| get big, fast, nowadays.
| jamal-kumar wrote:
| I've dealt with hundreds of gigabytes of JSON data like that in
| the fintech world
|
| And yeah I just streamed the data thru the processor and avoid
| malloc at all costs and it works in seconds
|
| I bet this method works even faster though somehow if they felt
| compelled to throw research money at all at it
| anonymoushn wrote:
| We receive market data formatted as JSON and use it to make
| trading decisions. So we would like to make those decisions
| quickly.
| loloquwowndueo wrote:
| The project described in the paper is https://simdjson.org/.
| pickledish wrote:
| Thank you for the link! Much nicer to browse this than an arxiv
| paper
| westurner wrote:
| Source: https://github.com/simdjson/simdjson
|
| PyPI: https://pypi.org/project/pysimdjson/
|
| There's a rust port: https://github.com/simd-lite/simd-json
|
| ... From ijson https://pypi.org/project/ijson/#id3 which
| supports streaming JSON:
|
| > _Ijson provides several implementations of the actual parsing
| in the form of backends located in ijson /backends:_ [yajl2_c,
| yajl2_cffi, yajl2, yajl, python]
| Ginden wrote:
| I think there is some room for "object predictor" optimization.
| In real world cases, 99% of objects in array will have the same
| keys over and over. Smart parser can potentially exploit that.
___________________________________________________________________
(page generated 2021-10-23 23:01 UTC)