transparent pointer compression for linked data structures
64-bit address spaces are increasingly important for modern applications, but they come at a price: pointers use twice as much memory, reducing the effective cache capacity and memory bandwidth of the system (compared to 32-bit address spaces). This paper presents a sophisticated, automatic transformation that shrinks pointers from 64-bits to 32-bits. The approach is "macroscopic," i.e., it operates on an entire logical data structure in the program at a time. It allows an individual data structure instance or even a subset thereof to grow up to 2 32 bytes in size, and can compress pointers to some data structures but not others. Together, these properties allow efficient usage of a large (64-bit) address space. We also describe (but have not implemented) a dynamic version of the technique that can transparently expand the pointers in an individual data structure if it exceeds the 4GB limit. For a collection of pointer-intensive benchmarks, we show that the transformation reduces peak heap sizes substantially by (20\% to 2x) for several of these benchmarks, and improves overall performance significantly in some cases.
transparency pointer compression pointers compression linked data data structures addressing space applications price use memorialized effect cache capacities bandwidth systems paper timing size efficiency dynamic version collect benchmark performance recursive data structure static analysis data layout