# US 2012/0254267 A1 · Numa-aware garbage collection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254267 A1
- Document ID: US20120254267A1
- Status: Published application
- Kind: A1
- Application number: 13/077,678
- Filed: 2011-03-31
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: Oracle International Corporation
- Inventors: Antonios Printezis; Igor Veresov; Paul Henry Hohensee; John Coomes
- Web page: https://patentgrep.com/patent/US20120254267A1

## CPC

- G06F 12/0269: {Incremental or concurrent garbage collection, e.g. in real-time systems (G06F12/0261 takes precedence)}
- G06F 12/0276: {Generational garbage collection}
- G06F 2212/2542: Non-uniform memory access [NUMA] architecture
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

System and Methods for non-uniform memory (NUMA) garbage collection are provided. Multiple memories and processors are categorized into local groups. A heap space is divided into multiple pools and stored in each of the memories. Garbage collection threads are assigned to each of the local groups. Garbage collection is performed using the garbage collection threads for objects contained in the pools using the garbage collector threads, memory, and processor assigned to each local group, minimizing remote memory accesses.

## Claims

### Claim 1

A method for non-uniform memory access aware garbage collector thread processing, comprising:
assigning a plurality of processing units and a plurality of memories to a plurality of lgroups, utilizing at least one processing unit of the plurality of processing units, based on access latency between each of the plurality of processing units and each of the plurality of memories;
dividing, utilizing the at least one processing unit, a heap space into a plurality of pools, each of the plurality of pools stored in one of the plurality of memories, each of the plurality of pools assigned to one of the plurality of lgroups according to the lgroup of the memory the respective pool is stored in;
providing, utilizing the at least one processing unit, a plurality of garbage collector threads with a plurality of queues, each of the plurality of garbage collector threads including at least a first queue of the plurality of queues for objects contained in one of the plurality of pools assigned to a same lgroup as the respective garbage collector thread and at least a second queue of the plurality of queues for objects contained in one of the plurality of pools assigned to a different lgroup from the respective garbage collector thread; and
executing the plurality of garbage collector threads, utilizing the at least one processing unit, such that each garbage collector thread:
first processes the at least the first queue,
second processes queues of other garbage collector threads of the plurality of garbage collector threads that are for objects contained in one of the plurality of pools assigned to the same lgroup as the respective garbage collector thread,
third processes the at least the second queue, and
fourth processes queues of other garbage collector threads of the plurality of garbage collector threads that are for objects contained in one of the plurality of pools assigned to the different lgroup from the respective garbage collector thread.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
queuing an object utilizing a garbage collector thread of the plurality of garbage collector threads by:
determining the lgroup of the pool of the plurality of pools that contains the object;
adding the object to the at least the first queue if the lgroup of the pool is the same lgroup as the lgroup of the garbage collector thread; and
adding the object to the at least the second queue if the lgroup of the pool is the different lgroup from the lgroup of the garbage collector thread.

### Claim 3 (depends on 2)

The method of claim 2, wherein said determining the lgroup of the pool of the plurality of pools that contains the object comprises:
constructing an lgroup table that includes entries for each of the plurality of pools;
computing an index to the lgroup table from an address of the object; and
mapping the index to an entry in the lgroup table.

### Claim 4 (depends on 1)

The method of claim 1, wherein each of the plurality of garbage collector threads scans root stacks of threads executing on processing units of the plurality of processing units assigned to the same lgroup as the respective garbage collector thread when queuing objects before scanning root stacks of threads executing on processing units of the plurality of processing units assigned to the different lgroup from the respective garbage collector thread.

### Claim 5 (depends on 1)

The method of claim 1, wherein the at least one second queue comprises a separate queue for each of the plurality of lgroups other than the lgroup of the respective garbage collector thread.

### Claim 6 (depends on 1)

The method of claim 1, wherein said executing the plurality of garbage collector threads comprises executing the plurality of garbage collector threads to perform at least a portion of a marking cycle.

### Claim 7 (depends on 1)

The method of claim 1, wherein said executing the plurality of garbage collector threads comprises executing the plurality of garbage collector threads to perform at least one garbage collection cycle.

### Claim 8 (depends on 7)

The method of claim 7, wherein the heap space includes a plurality of regions for containing objects, each of the plurality of regions contained in at least one of the plurality of pools, the plurality of regions including a plurality of young regions for storing young objects and a plurality of old regions when storing old objects, further comprising:
if copying an object to a young region of the plurality of young regions utilizing a garbage collector thread of the plurality of garbage collector threads, determining the lgroup of the pool of the plurality of pools that contains the object; and
copying the object to a pool of the plurality of pools assigned to the same lgroup as the pool of the plurality of pools that contained the object.

### Claim 9 (depends on 8)

The method of claim 8, further comprising:
if copying an object to an old region of the plurality of old regions utilizing the garbage collector thread of the plurality of garbage collector threads, copying the object to a pool of the plurality of pools assigned to the same lgroup as the garbage collector thread of the plurality of garbage collector threads.

### Claim 10 (depends on 8)

The method of claim 8, further comprising:
determining objects in the heap space are not evenly spread across lgroups; and
when copying objects to old regions of the plurality of old regions, copying the objects to pools of the plurality of pools according to a round-robin lgroup ordering.

### Claim 11 (depends on 10)

The method of claim 10, wherein determining objects in the heap space are not spread across lgroups comprises:
monitoring copying of objects during the garbage collection cycle.

### Claim 12

A system for non-uniform memory access aware garbage collector thread processing, comprising:
a plurality of processing units coupled to a plurality of memories, each of the plurality of processing units and each of the plurality of memories assigned to one of a plurality of lgroups based on access latency;
a heap space divided into a plurality of pools, each pool of the plurality of pools stored in one of the plurality of memories and assigned to one of the plurality of lgroups according to the lgroup of the memory the respective pool is stored in; and
a plurality of garbage collector threads, each garbage collector thread assigned to one of the plurality of lgroups according to the lgroup of one of the plurality of processing units that executes the respective garbage collector thread, each garbage collector thread including at least a first queue for objects contained in one of the plurality of pools assigned to a same lgroup as the respective garbage collector thread and at least a second queue for objects contained in one of the plurality of pools assigned to a different lgroup from the respective garbage collector thread;
wherein each of the plurality of garbage collector threads is executed by the respective one of the plurality of processing units to first process the at least the first queue, second process queues of other garbage collector threads of the plurality of garbage collector threads that are for objects contained in one of the plurality of pools assigned to the same lgroup as the respective garbage collector thread, third process the at least the second queue, and fourth process queues of other garbage collector threads of the plurality of garbage collector threads that are for objects contained in one of the plurality of pools assigned to the different lgroup from the respective garbage collector thread.

### Claim 13 (depends on 12)

The system of claim 12, wherein each of the plurality of garbage collector threads are operable to queue an object by:
determining the lgroup of the pool of the plurality of pools that contains the object; and
adding the object to the at least the first queue if the lgroup of the pool is the same lgroup as the lgroup of the respective garbage collector thread and to the at least the second queue if the lgroup of the pool is the different lgroup from the lgroup of the respective garbage collector thread;
wherein the respective garbage collector thread determines the lgroup of the pool by computing an index to an lgroup table from an address of the object, the lgroup table including entries for each of the plurality of pools, and mapping the index to an entry in the lgroup table.

### Claim 14 (depends on 12)

The system of claim 12, wherein each of the plurality of garbage collector threads is operable to queue objects by scanning root stacks of threads executing on processing units of the plurality of processing units assigned to the same lgroup as the respective garbage collector thread before scanning root stacks of threads executing on processing units of the plurality of processing units assigned to the different lgroup from the respective garbage collector thread.

### Claim 15 (depends on 12)

The system of claim 12, wherein the at least one second queue comprises a separate queue for each of the plurality of lgroups other than the lgroup of the respective garbage collector thread.

### Claim 16 (depends on 12)

The system of claim 12, wherein each of the plurality of garbage collector threads is executed by the respective one of the plurality of processing units to perform at least one of at least a portion of a marking cycle or at least one garbage collection cycle.

### Claim 17 (depends on 12)

The system of claim 12, wherein the heap space is divided up into at least a plurality of young regions for storing young objects and a plurality of old regions for storing old objects and each of the garbage collector threads copies an object during a garbage collection cycle by:
if copying the object to one of the plurality of young regions, determining the lgroup of pool of the plurality of pools that contains the object and copying the object to a pool of the plurality of pools assigned to the same lgroup as pool of the plurality of pools that contained the object; and
if copying the object to one of the plurality of old regions, copying the object to a pool of the plurality of pools assigned to the same lgroup as the respective garbage collector thread.

### Claim 18 (depends on 17)

The system of claim 17, wherein each of the garbage collector threads copies an object during a garbage collection cycle by:
determining objects in the heap space are not evenly spread across lgroups by monitoring copying of objects during the garbage collection cycle; and
when copying objects to old regions of the plurality of old regions, copying the objects to pools of the plurality of pools according to a round-robin lgroup ordering.

### Claim 19

A method for non-uniform memory access aware garbage collector thread garbage collection, comprising:
assigning a plurality of processing units and a plurality of memories to a plurality of lgroups, utilizing at least one processing unit of the plurality of processing units, based on access latency between each of the plurality of processing units and each of the plurality of memories;
dividing, utilizing the at least one processing unit, a heap space into a plurality of pools, each pool of the plurality of pools assigned to one of the plurality of lgroups according to the lgroup of the memory the respective pool is stored in, the plurality of pools including at least a plurality of young regions each operable to store at least one young object and a plurality of old regions each operable to store at least one old object;
copying, utilizing one of a plurality of garbage collector threads executed by the at least one processing unit, a young object during at least one garbage collection cycle, by:
determining the lgroup of the pool of the plurality of pools that contains the young object; and
copying the young object to a pool of the plurality of pools assigned to a same lgroup as the pool that contained the young object; and
copying, utilizing the one of the plurality of garbage collector threads executed by the at least one processing unit, an old object during the at least one garbage collection cycle by copying the old object to a pool of the plurality of old regions assigned to a same lgroup as the one of the plurality of garbage collector threads, the one of the plurality of garbage collector threads assigned to the lgroup of the at least one processing unit.

### Claim 20 (depends on 19)

The method of claim 19, wherein each of the plurality of garbage collector threads includes at least one pointer into the heap space for each of the plurality of lgroups specifying where a next young object will be copied to and at least one pointer into the heap space specifying where a next old object will be copied to.

### Claim 21 (depends on 19)

The method of claim 19, further comprising:
determining objects in the heap space are not evenly spread across lgroups; and
when copying old objects, copying the old objects to pools of the plurality of pools according to a round-robin lgroup ordering.

### Claim 22 (depends on 21)

The method of claim 21, wherein determining objects in the heap space are not spread across (groups comprises:
monitoring copying of objects during the garbage collection cycle.

### Claim 23

A system for non-uniform memory access aware garbage collector thread copying, comprising:
a plurality of processing units coupled to a plurality of memories, each of the plurality of processing units and each of the plurality of memories assigned to one of a plurality of lgroups based on access latency;
a heap space divided into a plurality of pools, each of the plurality of pools assigned to one of the plurality of lgroups according to the lgroup of the memory the respective pool is stored in, the plurality of pools including at least a plurality of young regions each operable to store at least one young object and a plurality of old regions each operable to store at least one old object;
a plurality of garbage collector threads, each of the plurality of garbage collector threads assigned to the lgroup of one of the plurality of processing units that executes the respective garbage collector thread;
wherein each of the garbage collector threads is operable to copy an old object during at least one garbage collection cycle by copying the old object to a pool of the plurality of pools assigned to a same lgroup as the respective garbage collector thread and to copy a young object during the garbage collection cycle by determining the lgroup of the pool of the plurality of pools that contains the young object and copying the young object to a pool of the plurality of pools assigned to a same lgroup as the pool that contained the young object.
