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 (and potentially less). 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 232 bytes in size. Furthermore, the transformation can choose to compress some data structures in a program but not others (e.g. if only part of the program is type-safe). 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 improves performance substantially (20% to 2x) for several of these benchmarks, and also reduces peak heap size by a similar factor.
"Transparent Pointer Compression for Linked Data Structures"
Chris Lattner and Vikram Adve.
Proceedings of the ACM Workshop on Memory System Performance (MSP'05), Chicago, Illinois, June, 2005.
Note, animations do not work in PDF version. Please use PPT version if possible.
The full context for this work is available in Chris Lattner's Ph.D. Thesis.
@InProceedings{PointerComp:MSP05,
author = {Chris Lattner and Vikram Adve},
title = "{Transparent Pointer Compression for Linked Data Structures}",
booktitle = "{Proceedings of the ACM Workshop on Memory System Performance (MSP'05)}",
address = {Chigago, Illinois},
month = {June},
year = {2005}
}