# US 10,769,063 B2 · Spin-less work-stealing for parallel copying garbage collection

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

- Number: US 10,769,063 B2
- Document ID: US10769063B2
- Status: Granted
- Kind: B2
- Application number: 15/986,299
- Filed: 2018-05-22
- Published: 2019-11-28
- Granted: 2020-09-08
- Earliest claimed: 2018-05-22
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Michihiro Horie; Hiroshi Horii; Kazunori Ogata
- Web page: https://patentgrep.com/patent/US10769063B2

## CPC

- G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory}
- G06F 9/45533: {Hypervisors; Virtual machine monitors}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 2212/1028: Power efficiency
- G06F 2212/1044: Space efficiency improvement
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Computer-implemented methods, program storage devices, and systems are provided for object copying in a computer performing parallel copying garbage collection on deques using work stealing. A method includes acquiring, for original objects in a source deque space, a destination deque space to copy the original objects to, and copying, from the source deque space to the destination deque space, any original objects in the source deque space having a reference to other ones of the original objects, or having a pre-known structure for estimating copy overhead. The method also includes registering, together with an address to copy to, any original objects in the source deque space lacking the reference to the other ones of the original objects, or lacking the pre-known structure for estimating copy overhead. The method additionally includes setting, in the source space, forwarding pointers to copied ones of the original objects in the destination deque place. The method may further include copying registered objects based on a copy cost or overhead and a spin count, waiting in a spin loop, and trying to steal a task after the spin loop. An upper limit may be imposed on the number of original objects that can be registered to prevent a load balance loss. The parallel copying garbage collection may be performed on a heap of the computer.

## Claims

### Claim 1

A computer-implemented method for object copying in a computer performing parallel copying garbage collection on deques using work-stealing, the method comprising:
acquiring, for original objects in a source deque space, a destination deque space to copy the original objects to;
copying, from the source deque space to the destination deque space, any of the original objects in the source deque space having a reference to other ones of the original objects;
registering, together with an address to copy to, any of the original objects in the source deque space lacking the reference to the other ones of the original objects; and
setting, in the source deque space, forwarding pointers to copied ones of the original objects in the destination deque space.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, further comprising finding other original objects in the source deque space that are referenced by any of the copied ones of the original objects in the destination deque space.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein responsive to an inability to steal work during the work-stealing, the method further comprises:
copying at least some of the registered objects, if any, wherein a number of copied ones of the registered objects is determined based on a copy cost therefor and a spin count;
waiting in a spin loop, responsive to a lack of any registered objects; and
trying to steal a task after the spin loop.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, further comprising:
determining whether remaining objects in the deques include only registered ones of the original objects;
copying all the remaining objects in the deques, responsive to the deques including only the registered ones of the original objects; and
terminating the parallel copying garbage collection responsive to all of the deques used for the parallel copying garbage collection being empty.

### Claim 5 (depends on 3)

The computer-implemented method of claim 3, further comprising determining a maximum limit on the number of copied ones of the registered objects as follows:
maximum limit=(spin count)*B/A,
wherein the variable A is a copying overhead, the variable B is a spin loop iteration overhead, and the variable spin count is determined as a variable max in a loop count equation (i=0;i<max;++i).

### Claim 6 (depends on 5)

The computer-implemented method of claim 5, further comprising executing the spin loop Y number of times, responsive to an actual number of copied ones of the original objects being less than the maximum limit, wherein the Y number of times is determined as follows:
Y=((spin count)−(the actual number of copied ones of the original objects)*A/B).

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein one of the deques is used to implement the source space to copy the original objects from, and another one of the deques is used to implement the destination space to copy the original object to.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, wherein the registering step imposes a delay on the copying of any of the registered ones of the original objects.

### Claim 9 (depends on 1)

The computer-implemented method of claim 1, further comprising imposing an upper limit on a number of the original objects that can be registered in order to prevent a load balance loss.

### Claim 10 (depends on 9)

The computer-implemented method of claim 9, wherein the upper limit is specified using a virtual machine argument.

### Claim 11 (depends on 1)

The computer-implemented method of claim 1, wherein the registering employs a size constraint such that any of the original objects exceeding a predetermined size limit are prevented from being registered.

### Claim 12 (depends on 11)

The computer-implemented method of claim 11, wherein the predetermined size limit is a based on a percentage of a size of a heap of the computer.

### Claim 13 (depends on 11)

The computer-implemented method of claim 11, wherein the predetermined size limit is specified using a virtual machine argument.

### Claim 14 (depends on 1)

The computer-implemented method of claim 1, wherein the deques are used to implement a heap of the computer.

### Claim 15 (depends on 1)

The computer-implemented method of claim 1, wherein the deques are used to perform the parallel copying garbage collection on a heap of the computer.

### Claim 16 (depends on 1)

A non-transitory article of manufacture tangibly embodying a computer readable program which when executed causes a computer to perform the method of claim 1.

### Claim 17

A computer-implemented method for object copying in a computer performing parallel copying garbage collection on deques using work-stealing, the method comprising:
acquiring, for original objects in a source deque space, a destination deque space to copy the original objects to;
copying, from the source deque space to the destination deque space, any of the original objects in the source deque space having a pre-known structure for estimating copy overhead;
registering, together with an address to copy to, any of the original objects in the source deque space lacking the pre-known structure for estimating the copy overhead; and
setting, in the source deque space, forwarding pointers to copied ones of the original objects in the destination deque space.

### Claim 18 (depends on 17)

The computer-implemented method of claim 17, further comprising imposing an upper limit on a number of the original objects that can be registered in order to prevent a load balance loss.

### Claim 19 (depends on 17)

A non-transitory article of manufacture tangibly embodying a computer readable program which when executed causes a computer to perform the method of claim 17.

### Claim 20

A system for object copying in a computer performing parallel copying garbage collection using work-stealing, the system comprising:
a set of deques;
a memory configured to store program code;
a processor, operatively coupled to the deques and the memory, configured to run the program code to
acquire, for original objects in a source deque space, a destination deque space to copy the original objects to;
copy, from the source deque space to the destination deque space, any of the original objects in the source deque space having a reference to other ones of the original objects;
register, together with an address to copy to, any of the original objects in the source deque space lacking the reference to the other ones of the original objects; and
set, in the source deque space, forwarding pointers to copied ones of the original objects in the destination deque space.

### Claim 21 (depends on 20)

The system of claim 20, wherein the processor is configured to run the program code to divide the set of deques into the source deque space and the destination deque space.

### Claim 22 (depends on 20)

The system of claim 20, wherein the deques are used to implement a heap of the computer.

### Claim 23 (depends on 20)

The system of claim 20, wherein the deques are used to perform the parallel copying garbage collection on a heap of the computer.

### Claim 24

A system for object copying in a computer performing parallel copying garbage collection using work-stealing, the system comprising:
a set of deques;
a memory configured to store program code;
a processor, operatively coupled to the deques and the memory, configured to run the program code to
acquire, for original objects in a source deque space, a destination deque space to copy the original objects to;
copy, from the source deque space to the destination deque space, any of the original objects in the source deque space having a pre-known structure for estimating copy overhead;
register, together with an address to copy to, any of the original objects in the source deque space lacking the pre-known structure for estimating the copy overhead; and
set, in the source deque space, forwarding pointers to copied ones of the original objects in the destination deque space.

### Claim 25 (depends on 24)

The system of claim 24, wherein the deques are used to implement a heap of the computer.