The Inflatable Transpose Tree: a highly compact data structure(engineering.vena.io)
engineering.vena.io
The Inflatable Transpose Tree: a highly compact data structure
https://engineering.vena.io/2016/05/09/transpose-tree/
2 comments
The price you pay for this level of compression is the loss of locality of reference. Yes you fit all the data for your struct fields in the minimum amount of memory, but every field for a single object is going to live on a different cache line. This might be OK if you are only ever doing something to a single field at a time, but it might hurt if you are reading many fields of an object at once.
Locality depends on many factors. True, the fields for a given object are spread out; however, they are much smaller. If you're iterating through a consecutive sequence of items in your compressed tables, you end up using the cache quite efficiently.