In a computer system with a garbage-collected heap memory, a cache of modified reference locations is associated with each application thread. The cache comprises a plurality of reference cache entries that are encoded in one of a plurality of ways. Using a write barrier that operates during a store operation, each application thread records modified references in its associated reference cache. Only when an entry must be evicted to make room for new information or when the thread is suspended is further processing of the reference cache required.