4 ms·

A linked list is hard to compress in memory as the overhead is the metadata: pointers, malloc overhead, ... but when written on disk can be represented as prefi

by antirez 16y ago

A linked list is hard to compress in memory as the overhead is the metadata: pointers, malloc overhead, ... but when written on disk can be represented as prefixed length strings. With VM the live representation and serialization format are the same.

signa11 16y ago
just curious: is it not possible to have some form of unrolled-linked-list to mitigate this effects somewhat ? or perhaps you have already tried it, and it doesn't really fit the bill.
- nitrogen 16y ago
  It kind of sounds like you're describing a sparse array.
  - signa11 16y ago
    > It kind of sounds like you're describing a sparse array. hmm not really. this: [ http://en.wikipedia.org/wiki/Unrolled_linked_list http://en.wikipedia.org/wiki/Unrolled_linked_list ] is what i had in mind
wrs 16y ago
Paul Wilson worked on compressed paging at the turn of the century [1] and tried to address this by introducing specialized compression algorithms for different kinds of pages (e.g., x86 instructions, pointer-filled data structures). Interesting stuff, but I don't think I've ever seen it commercialized, except in Newton OS where we used compressed code pages in binaries (read-only, not swap). [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.7895 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.7...