Hacker News Reader

Comment by jacquesm | Hacker News Reader

There is a huge difference between what the GP proposes and your interpretation: the GP talks about a structure that is not just a memory backed copy of the data in the file (which still requires an in memory structure pointing to the bits and pieces to make sense of it, or a painful parse step for every access and an impossibility to write back to it).

So the whole structure in its native form rather than the contents of the json file, for instance a graph would reside in memory and could be operated on directly.

Hence the 'serialized' in the part that you quoted. Once you serialize it the whole thing becomes hamburger and needs to be parsed again before you can operate on it.

View on HN

wongarsu is talking about actually mmaping the C structs in memory out to disk. There's no serialization involved: the format on disk is exactly the same as the bytes in RAM, and you rely on the OS to page them in on demand (notably, parts of the file that are never touched by the CPU are never paged in). You get around the invalidation of pointers by never using them: all data is stored as flattened arrays, and if you need to reference another object, you store an array index instead of a pointer.

This is a more common technique than most people suspect. It's taught in most operating system courses [1]. It's the basis for how SSTables (the primary read-only file format at Google, and the basis for BigTable/LevelDB) work, as well as for indexing shards. It was how the original version of MS Word's .doc files worked, and was also why it was so difficult to write a .doc file parser until Microsoft switched to a versioned serialized file format sometime in the 90s. I think it's how Postgres pages work (the DB allocates a disk page at a time and then overlays a C structure on top of it to structure the bytes), but I'm not familiar enough with that codebase to know for sure. It's how zero-copy serialization formats like Cap'n Proto & FlatBuffers work, except they've been specifically engineered to handle the backwards-compatibility aspects transparently.

It has all the problems that wongarsu mentions, but also huge advantages in speed and simplicity: you basically let the compiler and the OS do all the work and frequently don't need to touch disk blocks at all.

[1] https://www-users.cs.umn.edu/~kauffman/4061/lab06.html

I think we already covered that:

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

Couldn't you just mmap a binary final with the same in-memory structure rather than a text file?

Pointers in your memmapped file would be invalid after the second load. So it can't be the exact same structure that you would normalize use in a memory structure.

You could do it with relative offsets if you wanted, that's getting pretty close to pre-heating a cache from a snapshot. That way the file would not contain pointers but you could still traverse it relatively quickly by adding the offsets to the base address of the whole file.

Pointers could be valid if each file in this new OS resided at a specific location say in a 64-bit address space. You could allocate for example 4GB of virtual memory to each file and guarantee that a file will always be found at the same location with all the pointers intact and valid.

That sounds pretty hacky but it could work. Better to do it right and make the whole thing relocatable and the software addressing it aware of that. If you don't do it that way you may end up with some very interesting bugs, such as when your code also gets loaded into a 4GB segment (not all machines are 64 bits), and now all those pointers are valid throughout your memory image. That's bound to lead to confusion. Most CPUs can do base+offset with very little overhead anyway so there would be no or very little gain.

I don't think relocations are necessary at all. Within one system each file has a fixed place. Relocation and resolving happens only when files are copied across systems, where serialization should happen anyway. So e.g. once you receive a binary from the network, you resolve it and place it somewhere in the 64-bit space and then just execute it from there every time. The inode number becomes the file's physical address essentially.

Base+offset segmentation does have an overhead since you'd need some extra CPU registers for that if I understand it correctly.

Reply on news.ycombinator.com