Scalable garbage collection
View Patent ↗Methods and systems for performing memory garbage collection include determining a size of N double-ended queues (“deques”) associated with N respective garbage collection threads, where N is three or greater. A task is popped from a deque out of the N deques having a largest size. Garbage collection is performed on the popped task.
1. A method for performing memory garbage collection, comprising:
determining a size of N double-ended queues (“deques”) associated with N respective garbage collection threads, where N is three or greater;
popping a task from a deque out of the N deques having a largest size; and
performing garbage collection on the popped task.
2. The method of claim 1 , wherein popping the task is unsuccessful and a size of N new deques is determined.
3. The method of claim 1 , wherein determining the size of the N deques comprises counting a number of tasks in each deque.
4. The method of claim 1 , further comprising determining a value N that is proportional to a number of garbage collection threads in a garbage collection system.
5. The method of claim 4 , wherein determining the value N comprises calculating a value according to:
N
=
N
G
C
·
t
estim
t
take
·
C
where N GC is the number of garbage collection threads in the garbage collection system, t estim is a time consumed by determining a size of a deque, t take is a time consumed by attempting to take a task from a deque, and C is a constant value determined by a computational environment.
6. The method of claim 4 , further comprising determining a new value for N based on garbage collection performance for a plurality of different test values.
7. The method of claim 6 , wherein determining the new value for N selects a value for N that results in a lowest garbage collection wait time.
8. The method of claim 6 , wherein determining the new value for N selects a value for N that results in a highest ratio of successful attempts to take work to unsuccessful attempts to take work.
9. The method of claim 1 , wherein determining the size of a deque has a lower computational burden as compared to popping a task from a deque and wherein popping a task from a deque comprises issuing a memory fence.
10. A non-transitory computer readable storage medium comprising a computer readable program for performing memory garbage collection, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
determining a size of N double-ended queues (“deques”) associated with N respective garbage collection threads, where N is three or greater;
popping a task from a deque out of the N deques having a largest size; and
performing garbage collection on the popped task.
11. A memory garbage collection system, comprising:
a hardware processor, configured to execute a first garbage collection thread, wherein the first garbage collection thread is configured to determine a size of N double-ended queues (“deques”) associated with N respective additional garbage collection threads, where N is three or greater, to pop a task from a deque out of the N deques having a largest size, and to perform garbage collection on the popped task.
12. The system of claim 11 , wherein the first garbage collection thread is further configured to determine a size of N new deques if popping the task is unsuccessful.
13. The system of claim 11 , wherein the first garbage collection thread is further configured to count a number of tasks in each deque to determine the size of each deque.
14. The system of claim 11 , wherein the first garbage collection thread is further configured to determine a value N that is proportional to a number of garbage collection threads in a garbage collection system.
15. The system of claim 14 , wherein the first garbage collection thread is further configured to calculate the value N according to:
N
=
N
G
C
·
t
estim
t
take
·
C
where N GC is the number of garbage collection threads in the garbage collection system, t estim is a time consumed by determining a size of a deque, t take is a time consumed by attempting to take a task from a deque, and C is a constant value determined by a computational environment.
16. The system of claim 14 , wherein the first garbage collection thread is further configured to determine a new value for N based on garbage collection performance for a plurality of different test values.
17. The system of claim 16 , wherein the first garbage collection thread is further configured to select a new value for N that results in a lowest garbage collection wait time.
18. The system of claim 16 , wherein the first garbage collection thread is further configured to select a new value for N that results in a highest ratio of successful attempts to take work to unsuccessful attempts to take work.
19. The system of claim 11 , wherein determining the size of a deque has a lower computational burden as compared to popping a task from a deque and wherein the first garbage collection queue is further configured to issue a memory fence when popping a task from a deque.