6 ms·

> 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 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.

DonHopkins 4y ago
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.
- mindslight 4y ago
  "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.
  - DonHopkins 4y ago
    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://news.ycombinator.com/item?id=21109798 https://medium.com/@donhopkins/representing-and-editing-json-with-spreadsheets-8f8832db5239 https://medium.com/@donhopkins/representing-and-editing-json... SpreadOn: Apply Directly to the Forehead. https://www.youtube.com/watch?v=f_SwD7RveNE https://www.youtube.com/watch?v=f_SwD7RveNE
- coldtea 4y ago
  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...
  - antonvs 4y ago
    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.
    - coldtea 4y ago
      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...
      - antonvs 4y ago
        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.
  - jiggawatts 4y ago
    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 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.
pkaye 4y ago
How about something like a Go interface which is essentially two pointers and the data itself.
- Groxx 4y ago
  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.
  - Yoric 4y ago
    Does Go perform interning of strings?
    - Groxx 4y ago
      Compile-time strings, I think so? In that all identical strings simply point to the same data. Otherwise no.
      - xh-dude 4y ago
        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.
closeparen 4y ago
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.
- canadianfella 4y ago
  [dead]
btown 4y ago
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 https://v8.dev/docs/hidden-classes
rootw0rm 4y ago
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.
- fabrice_d 4y ago
  Yes, bincode supports the varint zigzag encoding which helps with small enough values.

DonHopkins 4y ago

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.

mindslight 4y ago
"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.
- DonHopkins 4y ago
  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://news.ycombinator.com/item?id=21109798 https://medium.com/@donhopkins/representing-and-editing-json-with-spreadsheets-8f8832db5239 https://medium.com/@donhopkins/representing-and-editing-json... SpreadOn: Apply Directly to the Forehead. https://www.youtube.com/watch?v=f_SwD7RveNE https://www.youtube.com/watch?v=f_SwD7RveNE
coldtea 4y ago
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...
- antonvs 4y ago
  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.
  - coldtea 4y ago
    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...
    - antonvs 4y ago
      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.
- jiggawatts 4y ago
  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 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.

pkaye 4y ago

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

Groxx 4y ago
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.
- Yoric 4y ago
  Does Go perform interning of strings?
  - Groxx 4y ago
    Compile-time strings, I think so? In that all identical strings simply point to the same data. Otherwise no.
    - xh-dude 4y ago
      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.

closeparen 4y ago

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.

canadianfella 4y ago
[dead]

btown 4y ago

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 https://v8.dev/docs/hidden-classes

rootw0rm 4y ago

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.

fabrice_d 4y ago
Yes, bincode supports the varint zigzag encoding which helps with small enough values.