Compact Garbage Collection Tables

David Tarditi

Published by Association for Computing Machinery, Inc.

View Publication

Garbage collection tables for finding pointers on the stack can be represented in 20-25% of the space previously reported. Live pointer information is often the same at many call sites because there are few pointers live across most call sites. This allows live pointer information to be represented compactly by a small index into a table of descriptions of pointer locations. The mapping from program counter values to those small indexes can be represented compactly using several techniques. The techniques all assign numbers to call sites and use those numbers to index an array of small indexes. One technique is to represent an array of return addresses by using a two-level table with 16-bit offsets. Another technique is to use a sparse array of return addresses and interpolate the exact number via disassembly of the executable code.