Hacker News new | past | comments | ask | show | jobs | submit login
The Inflatable Transpose Tree: a highly compact data structure (vena.io)
5 points by greenhathacker on May 9, 2016 | hide | past | favorite | 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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: