Collaborative Research: CSR: Medium: Pointer Compression: Bridging Theory and Practice for High-Performance Computing Systems

Rutgers University New Brunswick, New Brunswick NJ

Investigators

Abstract

One of the foundational challenges in computer science is designing data structures that are both space- and time-efficient. Efficient data structures directly impact the performance, energy use, and cost of computing systems that underlie national-scale infrastructure—from supercomputers to cloud services to embedded systems in defense and transportation. In recent theoretical work, the PIs introduced a new technique, the tiny pointer, with the potential to substantially reduce the memory footprint of pointer-based data structures, enabling performance and efficiency gains across a wide range of systems. This project aims to translate tiny pointers from a theoretical insight into a deployable, foundational systems tool. By making tiny pointers broadly applicable, this research supports the national interest in advancing high-performance, resource-efficient computing critical to economic competitiveness, technological leadership, and secure infrastructure. At a high level, tiny pointers are compressed representations of memory addresses that retain compatibility with modern hardware and software systems. This project aims to develop foundational techniques for implementing tiny pointers, and the project has three primary goals: (1) to establish principles for building practical, scalable, and safe tiny-pointer abstractions; (2) to design and implement a high-performance library and OS module that expose these abstractions to both kernel and user-level applications; and (3) to demonstrate space and performance gains across a broad range of systems. Key applications include classical data structures (e.g., hash tables and trees), OS primitives such as page tables and page cache indexes, and flash translation layers (FTLs) in SSDs. For instance, by compressing pointers in x86-64 page tables, the project aims to increase fanout and reduce walk latency, potentially enabling a shift from 4-level to 3-level page tables. Similar benefits are expected for DRAM-resident mapping tables in SSDs. The project will also explore the impact of tiny pointers on systems such as IOMMUs, key-value stores, file systems, and large language models. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.