Hacker News Reader

> JSON is a text format and interning it into proper data structures is likely going to take _less_ space, not more.

That depends a lot on the language and the json library.

Lets take `{"ab": 22}` as an example.

That's 10 bytes.

In a language like Rust and using the serde library, this could be deserialized directly into a struct with one integer, let's pick a u32. So that would only be four bytes.

But if it was deserialized to serdes dynamic Value type, this would be : a HashMap<String, u32>, which has a constant size of 48 bytes, plus an allocation of I don't know how much (first allocation will cover more than one entry), plus 16 bytes overhead for the string, plus 2 bytes for the actual string contents, plus the 4 bytes for the u32. So that's already over ~90 bytes, a lot more than the JSON.

Dynamic languages like Python also have a lot of overhead for all the objects.

Keys can of course be interned, but not that many default JSON parser libraries do that afaik.

The key names of all the identically shaped objects are repeated and can all be interned into sharing the same strings, saving a huge amount of memory. That's why csv files can be much more compact that the equivalent json files: they only list the keys once in the first row.

"ab" is 4 bytes, while a 64 bit pointer to an interned string is 8 bytes. It would seem that the savings of CSV would be better analogized to static typing - the type is defined once, then each record only contains data.

I had the same intuition as the original comment. But no, the relative sizes of data formats aren't that straightforward. One could intern symbols to say 16 bit values, or one could infer structural types and compress the data that way. But those are both creating additional assumptions and processing that likely aren't done by commonly available tools.

You still have to pay for a 64 bit pointer to an un-interned string though. It's the fact that the keys are repeated for each record that overwhelms the size of the keys or pointers themselves, when you have millions of records. If you are using fixed structures, then the keys are implicit and don't need to be repeated or even represented as pointers, just known fixed offsets into the structures.

I wrote this about "Representing and Editing JSON with Spreadsheets":

https://news.ycombinator.com/item?id=21109798

https://medium.com/@donhopkins/representing-and-editing-json...

SpreadOn: Apply Directly to the Forehead.

https://www.youtube.com/watch?v=f_SwD7RveNE

The size of the keys isn't even the problem.

The numeric value 1 is 1 byte, but it's several bytes to be wrapped into a native numeric object instance in say Python. In C, it would be 8 bytes to get it to an int64, unless the parser does something fancy (and if there are values with 1 and 2 digits, it would at least make it a 2-bytes int holder).

The string "x" is one byte, but it'll take two bytes in C ("x\0").

And so on...

In the text representation of JSON, the string “x” is three characters. Short of using a statically-typed length, C’s system is about as efficient as it gets in terms of space overhead.

You'd also need to add the overhead of memory representation as jiggawatts says, so you'd need to start from 8 bytes just for the pointer alone (more than double that 3 byte textual representation)! And it's not gonna just allocate one byte (unless you go something fancy with your allocator), but 8 bytes for the string, 2 of which would be the "x" and the null terminator. So 3 -> 16 for a single 1 byte value.

And that's in C, where the length calculations and the type management is up to you! It gets worse soon...

There’s a weird sort of apples to oranges comparison going on here. Having pointers to separately allocated strings gives you much more functionality than an unindexed blob of JSON text. That obviously has a cost in terms of memory.

But if you need to, you can represent the same data as a contiguous block of C-style formatted structures, in which case the “x” wouldn’t need more than two or three bytes depending on the representation you choose. In fact, there are formats designed for this exact purpose. The idea that JSON is somehow surprisingly efficient for what it does is just silly.

You're all massively underestimating the memory requirements of a parsed data structure, which is very entertaining to watch. There's this rule-of-thumb that most programmers are wrong about performance costs by at least a couple of orders of magnitude, and it's on full display here.

In most languages, dynamically allocated variable-sized objects have a minimum overhead of two pointer-sized fields: a pointer and a length. On a 64-bit platform, that's 16 bytes before you actually start having any data.

Next, depending on the allocator used, the requested data size is probably rounded up, either to the next power of 2, or there may be a minimum allocation size of 1 pointer. That's the compatible safe approach, and also has some performance advantages on most platforms.

Last but not least, most heap-based allocators have some "bookkeeping" overheads. Similarly, interpreted languages also have their internal "object" metadata overheads. Typically this is 1 or 2 extra pointers (+8 or +16 bytes).

Assuming 24-48 bytes for all variable-length values is actually a pretty safe bet!

There are exceptions:

Unusually, C skips the 'length' value for strings by using null-termination, so C strings are often just 16 bytes (8 for the pointer, and 8 for the allocated object on the heap, assuming some sort of small-object optimisation is going on).

The approach in C++ is to use "small string optimisation" where the string values are inlined into the std::string structure itself. This works up to 23 bytes packed into the 24-byte string structure. There's an awesome CppCon presentation on how Andrei Alexandrescu did this optimisation at Facebook: https://www.youtube.com/watch?v=kPR8h4-qZdk

Interpreted or "VM" languages like JavaScript, C# or Java are far worse than this. For one, they convert UTF8 to UTF16, doubling the bytes required per character for typical "ASCII" identifiers. JavaScript converts integers into 64-bit floats. Java has weird overheads for all objects. Etc...

Update: I just did an experiment with .NET 6

    Allocating ~1 billion characters as 100M strings
        800,000,056 bytes (0.7 GB) for holding the strings.
     14,021,088,768 bytes (13.1 GB) for the strings themselves
     14,821,216,680 bytes (13.8 GB) total

Unsurprisingly, simply "referencing" (holding on to) the strings needs an 8-byte pointer per string. The actual strings hold 1-20 characters randomly, but require 140 bytes in memory on average. This bloats out the original 1 GB to just under 14 GB in memory.

I have been hit by this many times. Do you know of any good resources on how to reduce this overhead? (Choosing other data structures, choosing other string types etc)

There's a whole range of techniques! Many of them are language dependent, and won't be applicable elsewhere.

A blunt instrument is running your code in 32-bit mode, which halves pointer sizes. The downside is it also limits your maximum data size, and blocks the use of the 64-bit instruction sets that generally speed up data processing.

Java has an interesting hybrid mode where it uses 32-bit pointers but runs in 64-bit mode.

Not storing the entire decoded document all at once is usually the recommended approach, via "streaming" parsers that give you one element at a time. This then lets you immediately throw away data that you're done with processing.

The downside is that it makes certain common idioms impossible or difficult. For example, MVC web architectures generally assume that the controller produces a "complete" model object that then gets passed to the view.

Unfortunately, language-level support for efficient data processing is generally lacking. Rust and C++ are okay, but have annoying gaps in their capabilities.

A common trick with something like parsing is to keep the original encoded string to be decoded "as-is", and then simply reference into it using integer indexes. I.e.: don't copy the strings out individually, instead just use "slices" into the original document string.

Most commonly, unique strings are detected using a hash table and not stored separately. This works better with garbage-collecting languages like C#, Java, and JavaScript. With Rust or C++ you have to use reference counting or other tricks.

How about something like a Go interface which is essentially two pointers and the data itself.

That's the same thing they're describing, and equivalent to what Go does for map[string]int64 (plus or minus minor details about how strings are optimized).

The map has its two slices (pointer + length + capacity = 8*3 times two slices) and the string needs a separate allocation somewhere because it's essentially a pointer to a slice of bytes. All of which is true for almost all reasonably efficiency-focused languages, Rust and Go included - it's just how you make a compact hashmap.

Does Go perform interning of strings?

Compile-time strings, I think so? In that all identical strings simply point to the same data. Otherwise no.

Use of Go’s runtime reflection to produce a struct definition would result in one instance of the key string, many instances of the numeric value

This approach is available/implemented in the standard library, the whole story with JSON in Go is includes a few different approaches but this is definitely anticipated.

I would read "proper data structure" charitably, as a struct or record type, maybe a tuple. And if it must be a hashmap, then at least using symbols and not strings for keys.

I feel like many of the same principles from V8 (the engine for Chrome/Node.js) hidden classes would apply here. It's not just that you're interning keys; you're actually creating a set of optimized data classes that are transitioned to when you encounter a key that wasn't seen before. In such a mode, you're not even storing the keys, just a pointer to the type information tree. Only when you have a sub-object whose keys are truly unpredictable do you go into "dictionary mode (aka 'slow mode')" - which I think says it all!

https://v8.dev/docs/hidden-classes

i'm using bincode to serialize btrees and the files are smaller than i expected...it's pretty cool. must be storing my u32s as u16s or u8s sometimes.

Yes, bincode supports the varint zigzag encoding which helps with small enough values.

> Or write a custom little program that streams data from the JSON file without buffering it all in memory. JSON parsing libraries are plentiful so this should not take a lot of code in your favorite language.

Several years ago I wrote a paper [1] on representing the parse tree of a JSON document in a tiny fraction of the JSON size itself, using succinct data structures. The representation could be built with a single pass of the JSON, and basically constant additional memory.

The idea was to pre-process the JSON and then save the parse tree, so it could be kept in memory over several passes of the JSON data (which may not fit in memory), avoiding to re-do the parsing work on each pass.

I don't think I've seen this idea used anywhere, but I still wonder if it could have applications :)

[1] http://groups.di.unipi.it/~ottavian/files/semi_index_cikm.pd...

Have you implemented this idea in code? Seems interesting and worth playing around with

Yes, the code is linked in the paper: https://github.com/ot/semi_index

> JSON is a text format and interning it into proper data structures is likely going to take _less_ space, not more.

If you're parsing to structs, yes. Otherwise, no. Each object key is going to be a short string, which is going to have some amount of overhead. You're probably storing the objects as hash tables, which will necessarily be larger than the two bytes needed to represent them as text (and probably far more than you expect, so they have enough free space for there to be sufficiently few hash collisions).

JSON numbers are also 64-bit floats, which will almost universally take up more bytes per number than their serialized format for most JSON data.

I think even structs have this problem because typically you heap allocate all the structs/arrays. You could try to arena allocate contiguous objects in place, but that sounds hard enough that I doubt that anyone bothers. Using a SAX parser is almost certainly the tool you want to use.

> JSON numbers are also 64-bit floats

In common implementations they are, but RFC 8259 and ECMA-404 do not specify the range, precision, or underlying implementation for the storage of numbers in JSON.

A implementation that guarantees interoperability between all implementations of JSON would use an arbitrary-sized number format, but they seldom do.

No idea what ISO/IEC 21778:2017 says because it's not free.

I mean, I suppose you could use a numeric format that takes more than 64 bits, but you certainly couldn't use one that uses fewer. You have no way to know whether a number should be an int or a float. And since JavaScript (the JS in JSON) encodes with 64 bits, you'd be losing precision if you choose to use any less. The point is that an integer written as one byte in the JSON will take up more space (at least seven bytes more) when decoded, all the way up to numbers that take seven characters.

(subsets of )ASN.1, LEB128, and of course UTF-8 are all examples of encoding binary integers with variable length.

Sure, and JSON is as well. 0 takes three fewer bytes to encode than 1234. But if I parse JSON and my numbers come back as a type backed by UTF-8, I'm going to be left confused and angry. Nobody expects their JSON parser to give them back numeric values that their CPU can't natively perform operations on.

After you have spent some time confused and angry you can then read the documentation of whatever library you are using and verify whether it overloads numerical operations for its special number type or it has a function to convert them to whatever numerical type you need.

In any case you wouldn't of course use UTF-8 to represent JSON numbers as it can only encode 21 bit intgers.

>JSON is a text format and interning it into proper data structures is likely going to take _less_ space, not more.

Wanna bet?

  >>> import sys
  >>> import json
  >>> data_as_json_string = '{"a": 5000, "b": 1000}'
  >>> len(data_as_json_string)
  22
  >>> data_as_native_structure = json.loads(data_as_json_string)
  >>> sys.getsizeof(data_as_native_structure)
  232

That's not even the whole story, as what's 232 bytes is not the contents of the dict, but just the Python object with the dict metadata. So the total for the struct inside is much bigger than 232 bytes.

A single int wrapped as a Python object can be quite a lot by itself:

>>> sys.getsizeof(1) 28

A binary int64 would be 8 bytes for comparison.

Maybe 2023 is the year people stop using python.

We can dream but I seriously doubt it. Not only are there very few nice alternatives (Dart is great but unpopular; Typescript is great but has a terrible standard library, etc.) but very few of them have a decent REPL which I think is probably Python's most underrated feature.

I mean... it's REPL is extremely basic, but anything you can do in Python you can do in the REPL. Very useful especially for beginners.

Python is my favorite language but you literally chose one of the least efficient. This would probably be different in Java or Rust.

I thought Java stores strings as 16-bit character arrays internally. Which means it's very inefficient when it comes to memory consumption.

Since version 9, Java uses ISO-8859 when possible. Most raw JSON should therefore take up very little space.

I'm pretty sure the GP intended the statement to be for statically typed languages with a struct-like type.

It doesn't get much better there:

https://news.ycombinator.com/item?id=35216761

Have you done much data analysis?

In my experience adding more steps to your pipeline (E.g. database, deserializing, etc) is a pain when you are figuring things out because nothing has solidified yet, so you're literally just adding overhead that requires even more work to remove/alter later on. If you're not careful you end up with something unmaintainable extremely quickly.

Only analyzing a subset of your data is usually not a magic bullet either. Unless your data is extremely well cleaned and standardized you're probably going to run into edge cases on the full dataset that were not in your subset.

Being able to run your full pipeline on the entire dataset in a short period of time is very useful for testing on the full dataset and seeing realistic analysis results. If you're doing any sort of aggregate analysis it becomes even more important, if not required.

I now believe a relatively fast clean run is one of the most important things for performing data analysis. It increases your velocity tremendously.

> * "You might find out that the data doesn’t fit into RAM (which it well might, JSON is a human-readable format after all)" -- if I'm reading this right, the author is saying that the parsed data takes _more_ space than the JSON version? JSON is a text format and interning it into proper data structures is likely going to take _less_ space, not more.

Not to mention, even when using bad data structures (eg. hashmap of hashmaps..), One can just add a large enough swapfile and brute force their way through it no?

This will fail if the algorithm is not O(n). Even if only a bounded number of passes is required, there will be trouble.

If the JSON data has a regular structure, you probably want a database and/or a "data frame" library and Parquet as the storage file format. SQLite, DuckDB, Polars, plenty of options nowadays that are usable from several different programming languages.

> if I'm reading this right, the author is saying that the parsed data takes _more_ space than the JSON version? JSON is a text format and interning it into proper data structures is likely going to take _less_ space, not more.

Utf8 json strings will get converted to utf16 strings in some languages, doubling the size of strings in memory compared to the size on disk.

> A few GBs of data isn't really that much.

The entire FCC radio license database (the ULS) is about 14GB in text CSV format and can be imported into a sqlite or sql db and easily queried in RAM on a local workstation...

It still surprises me how many have the intuition that loading the data will take more space than the file.

Even more annoying when it is. (Compressed or binary formats not withstanding.)

Isn’t that almost always true unless the format is specifically designed to take the same amount on disk and in RAM? If that’s the case I think typically it means the file on disk is larger than it needs to be. That’s because you have to convert the file to some kind of in-memory representation that’s easier to work with to manipulate it and what not which requires structure that isn’t necessary at rest.

Can you give an example where the file on disk is going to be larger than what it is in memory? Provided you’re not just reading it and working with it as an opaque binary blob.

XML would probably fall into that category.

But I do agree with your point more generally speaking.

Depends on the data, obviously; but record format data should be compact in memory in ways that text isn't. My favorite example is the meg's of commas and quotes that just aren't needed in memory.

So, my examples are largely csv files. JSON and xml are the same, in many ways.

The big curve ball will be text heavy data. But all too often textual data is categorical, such that even that should be smaller in memory.

In large, this is why parquet files are a ridiculous win in space.

My favorite example is the meg's of commas and quotes that just aren't needed in memory.

Depending on the language and internal represenation, for any comma and quote not needed (which for a JSON document with, say, an object without nesting, is just 5 bytes per entry), you might get your strings doubled in size (because e.g. the language converted your fitting into 8bit utf-8 strings to its 16bit native string format), or have some huge constant boxing overhead (in say, Python), and several other fun things besides...

Right, is why I said strings can be a curve ball. But most of the data I see can avoid that fairly easily.

I think it comes more from the thought that human text readable format is usually more verbose than binary representations.

Coming back to this, I was curious and decided to challenge my assertion some. https://taeric.github.io/challenging-my-filesize-intuition.h... is a few examples where I was fishing around. I didn't find any where my assertion is not true.

Curious if you have any easy examples to look at that do show the opposite.

> JSON is a text format and interning it into proper data structures is likely going to take _less_ space, not more.

~~Yeah but parsing it can require ~2x the RAM available and push you into swap / make it not possible.~~

> Or write a custom little program that streams data from the JSON file without buffering it all in memory. JSON parsing libraries are plentiful so this should not take a lot of code in your favorite language.

What is the state of SAX JSON parsing? I used yajl a long time ago but not sure if that’s still the state of the art (and it’s C interface was not the easiest to work with).

EDIT: Actually, I think the reason is that you typically will have pointers (8 bytes) in place of 2 byte demarcations in the text version (eg “”, {}, [] become pointers). It’s very hard to avoid that (maybe impossible? Not sure) and no surprise that Python has a problem with this.

There's libraries like ijson. At my last job, i wrote a wrapper around this C++ library called rapidjson to parse streaming json. It worked quite well.

Here's the write up about it: https://dinesh.cloud/2022/streaming-json-for-fun-and-profit/ And here's the code: https://github.com/multiversal-ventures/json-buffet

The API isn't the best. I'd have preferred an iterator based solution as opposed to this callback based one. But we worked with what rapidjson gave us for the proof of concept. The reason for this specific implementation was we wanted to build an index to query the server directly about it's huge json files (compressed size of 20+GB per file) using http range queries.

so on this note, unless you have massive json lists... having a json object per line (jsonl) can really help this process... I use jq when necessary .. but I usually use `cat file.json | grep foo | grep bar | jq -r .thing` since it's a string, use string comparison tools rather than jq :)