Thread-local hash table based write barrier buffers
A write barrier is implemented using thread-local hash table based write barrier buffers. The write barrier, executed by mutator threads, stores addresses of written memory locations or objects in the thread-local hash tables, and during garbage collection, an explicit or implicit union of the addresses in each hash table is used in a manner that is tolerant to an address appearing in more than one hash table.
1 . A computer usable medium having computer usable program code means embodied therein for causing a computer to perform garbage collection, the computer usable program code means comprising:
a computer readable program code means for allocating a thread-local write barrier buffer hash table for a thread;
a computer readable program code means for inserting an address into the thread-local write barrier buffer hash table of the thread executing a write barrier; and
a computer readable program code means for using the union of the sets of addresses in at least two thread-local write barrier buffer hash tables in a manner that is tolerant to the same address appearing in more than one hash table.
2 . The computer program product of claim 1 , wherein the addresses are addresses of written memory locations.
3 . The computer program product of claim 1 , wherein the addresses are derived from old values of written memory locations.
4 . The computer program product of claim 1 , wherein using the union comprises computing the union of the sets.
5 . The computer program product of claim 1 , wherein using the union comprises iterating over at least two of the sets, and performing a garbage collection related action for each address therein, said action being tolerant to being invoked for the same address more than once.
6 . The computer program product of claim 1 , wherein at least one computer readable program code means is configured to implement at least one thread-local write barrier buffer hash table using multiplicative hashing and linear probing.
7 . An apparatus comprising:
one or more processors;
a control logic, including an application control logic and a garbage collector control logic;
more than one thread, threads being executable by at least some of the processors and operating at least in part as specified by the control logic; and
a heap comprising objects, at least some of which are modified by the threads;
wherein the improvement comprises:
at least two threads comprising a thread-local write barrier buffer hash table in which at least some writes to the heap by the respective threads are tracked; and
the garbage collector control logic comprising a union logic configured to use the union of the sets of addresses in the thread-local write barrier buffer hash tables of the threads, wherein the union logic is tolerant to the same address appearing in more than one thread-local write barrier buffer hash table.
8 . The apparatus of claim 7 , wherein the union logic is configured to explicitly compute the union of the sets.
9 . The apparatus of claim 7 , wherein the union logic is configured to iterate over at least two said write barrier buffer hash tables, performing a garbage collection related action for each address therein, said action being tolerant to being invoked for the same address more than once.
10 . The apparatus of claim 7 , wherein values derived from the addresses of written memory locations are used as keys in at least one of the thread-local write barrier buffer hash tables.
11 . The apparatus of claim 7 , wherein values derived from old values of written memory locations are used as keys in at least one of the thread-local write barrier buffer hash tables.
12 . The apparatus of claim 7 , wherein at least one thread-local write barrier buffer hash table uses multiplicative hashing and linear probing.
13 . A method of tracking addresses in a garbage collector, comprising:
allocating a thread-local write barrier buffer hash table for at least two threads;
for at least two threads, inserting, by a write barrier, an address into the thread-local write barrier buffer hash table of the thread executing the write barrier; and
using, by a garbage collector, the union of the sets of addresses in the write barrier buffer hash tables in a manner that is tolerant to the same address appearing in more than one hash table.
14 . The method of claim 13 , wherein using the union of the sets comprises:
computing a set representing the union of the sets of addresses in the write barrier buffer hash tables; and
using that set by the garbage collector.
15 . The method of claim 13 , wherein using the union of the sets comprises:
iterating over each of the write barrier buffer hash tables and performing a garbage collection related action for each address therein, said action being tolerant to being invoked for the same address more than once.
16 . The method of claim 15 , wherein values derived from the addresses of written memory locations are used as keys for at least one of the thread-local write barrier buffer hash tables.
17 . The method of claim 15 , wherein values derived from old values of written memory locations are used as keys for at least one of the thread-local write barrier buffer hash tables.
18 . The method of claim 13 , wherein the computation of a hash value for at least one thread-local write barrier buffer hash table comprises multiplication by a constant modulo a power of two and using high-order bits of the result as the hash value, and using linear probing for resolving hash conflicts.