The relationships between objects in our directed graph were generally represented with
HashSetsof “to” objects were keyed by “from” objects.
This was a lot of objects and a lot of 64-bit pointers. In the new design:
Our data structure maintains two arrays. One is an integer array, and the other is a byte array. Each object’s connections are encoded into the byte array as delta-encoded variable-byte integers (more on this in the next paragraph). The integer array contains offsets into the byte array, such that the connections for the object represented by some ordinal are encoded starting at the byte indicated by offsetArray[ordinal].
This reduced the memory footprint by 90%.
Stay up-to-date by subscribing to the Comments RSS Feed for this post.