Member-only story
Pragmatic Promises of Tiny Pointers
Tiny pointer is a new data structure proposed by Michael A. Bender, Alex Conway, Martín Farach-Colton, William Kuszmaul, and Guido Tagliavini. It was published in the ACM Transactions on Algorithms in October 2024. It was submitted to Arxiv for peer review as early as November 2021 itself.
The authors of tiny pointers observe that these data structures can replace the traditional log (n)— bit pointers with o(log (n))-bit tiny pointers at the cost of only a constant factor time overhead and a small probability of failure. This is achieved by leveraging information about the “owner” of the pointer and using techniques like hashing and probabilistic methods.
Tiny pointers essentially focuses on reducing the size of pointers in memory. The core idea is to use contextual information to represent pointers with fewer bits than traditional pointers. The algorithm involves the methods for allocating and deallocating memory through tables.
The dereferencing tables are designed to reconstruct the actual memory from the tiny pointer and its context. This table acts as a translation layer, converting the compressed tiny pointer back into full memory address. Hashing plays a vital role in efficiently managing and accessing this dereference table. Tiny pointers leverage contextual information (e.g., the “owner” of the pointer) to enhance hashing…
