Programmers routinely trade space for time to increase performance, often in the
form of caching or memoization. In managed languages like Java or JavaScript,
however, this space-time tradeoff is complex. Using more space translates into
higher garbage collection costs, especially at the limit of available
memory. Existing runtime systems provide limited support for
space-sensitive algorithms, forcing programmers into difficult and often brittle
choices about provisioning.

This paper presents \emph{prioritized garbage collection}, a cooperative
programming language and runtime solution to this problem. Prioritized GC
provides an interface similar to soft references, called \emph{priority
references}, which identify objects that the collector can reclaim eagerly if
necessary. The key difference is an API for defining the policy that governs
when priority references are cleared and in what order. Application code
specifies a priority value for each reference and a target memory bound. The
collector reclaims references, lowest priority first, until the total memory
footprint of the cache fits within the bound. We use this API to implement a
space-aware least-recently-used (LRU) cache, called a \emph{Sache}, that is a
drop-in replacement for existing caches, such as Google's Guava library. The
garbage collector automatically grows and shrinks the Sache in response to
available memory and workload with minimal provisioning information from the
programmer. Using a Sache, it is almost impossible for an application to
experience a memory leak, memory pressure, or an out-of-memory crash caused by
software caching.