Adaptive triggering of garbage collection
Methods and apparatus are provided for adaptively triggering garbage collection. During relatively steady or decreasing rates of allocation of free memory, a threshold for triggering garbage collection is dynamically and adaptively determined on the basis of memory drops (i.e., decreases in free memory) during garbage collection. If a significant increase in the rate of allocation of memory is observed (e.g., two consecutive measurements that exceed a mean rate plus two standard deviations), the threshold is modified based on a memory drop previously observed in conjunction with the current memory allocation rate, or a memory drop estimated to be possible for the current allocation rate.
1. A method of adaptively triggering garbage collection within a computer system, the method comprising:
initializing a data structure to comprise N empty buckets (N>0), wherein each bucket represents an amount of free memory;
periodically recording a rate of allocation of free memory;
for each of multiple iterations of garbage collection:
calculating a mean rate of allocation of free memory prior to the iteration;
observing a drop in the free memory during the iteration;
reading the data structure to examine a bucket corresponding to the observed memory drop;
if the bucket is empty, storing in the bucket the calculated mean rate of allocation of free memory; and
if the bucket stores a rate of allocation higher than the calculated mean rate of allocation of free memory, replacing the stored rate of allocation with a new rate of allocation; and
if an increase in the rate of allocation of free memory is observed during said periodic recording, adjusting a free memory threshold at which the garbage collection is initiated.
2. The method of claim 1 , wherein each bucket B=1 to N in the data structure represents a portion of the free memory M calculated as B×(M÷N).
3. The method of claim 1 , wherein said periodically recording comprises:
periodically measuring an amount of free memory available for allocation; and
from the measurements of available free memory, calculating the rate of allocation of free memory.
4. The method of claim 3 , wherein said calculating a mean rate of allocation of free memory prior to the iteration comprises:
calculating an average of multiple calculated rates of allocation of free memory.
5. The method of claim 1 , wherein said drop in free memory during an iteration of garbage comprises an amount of free memory available for allocation prior to the iteration minus a lowest amount of free memory available for allocation during the iteration.
6. The method of claim 1 , wherein said reading the data structure to examine a bucket corresponding to the observed memory drop comprises:
identifying a bucket corresponding to the amount of the observed memory drop; and
reading an entry in the bucket.
7. The method of claim 1 , further comprising if the bucket stores a rate of allocation higher than the calculated mean rate of allocation of free memory:
reading an adjacent bucket corresponding to a next lower amount of free memory, if such a bucket exists; and
if the adjacent bucket stores a rate of allocation that is not lower than the calculated mean rate of allocation, decreasing the rate of allocation stored in the adjacent bucket.
8. The method of claim 7 , wherein said decreasing the rate of allocation comprises:
calculating an average of the rate of allocation stored in the adjacent bucket and a rate of allocation stored in the next adjacent bucket; and
storing said average in the adjacent bucket.
9. The method of claim 1 , wherein the new rate of allocation stored in the bucket is the calculated mean rate of allocation of free memory.
10. The method of claim 1 , wherein the new rate of allocation stored in the bucket is an average of the stored rate of allocation and the calculated mean rate of allocation of free memory.
11. A computer-readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of adaptively triggering garbage collection within the computer, the method comprising:
initializing a data structure to comprise N empty buckets (N>0), wherein each bucket represents an amount of free memory;
periodically recording a rate of allocation of free memory;
for each of multiple iterations of garbage collection:
calculating a mean rate of allocation of free memory prior to the iteration;
observing a drop in the free memory during the iteration;
reading the data structure to examine a bucket corresponding to the observed memory drop;
if the bucket is empty, storing in the bucket the calculated mean rate of allocation of free memory; and
if the bucket stores a rate of allocation higher than the calculated mean rate of allocation of free memory, replacing the stored rate of allocation with a new rate of allocation; and
if an increase in the rate of allocation of free memory is observed during said periodic recording, adjusting a free memory threshold at which the garbage collection is initiated.
12. A computer-implemented method of adaptively triggering garbage collection within the computer, the method comprising:
setting a starting free memory threshold at which the garbage collection is to be initiated;
for each of multiple garbage collection iterations initiated when an amount of free memory falls to the starting free memory threshold:
calculating an average drop in free memory over the completed iterations;
calculating a standard deviation of the drops in free memory over the completed iterations;
calculating a first candidate threshold as a portion of the starting free memory threshold;
calculating a second candidate threshold from the average drop in free memory and the standard deviation; and
resetting the starting free memory to the larger of the first candidate threshold and the second candidate threshold.
13. The method of claim 12 , wherein the drop in free memory during a given iteration of the garbage collection equals an amount of free memory of the application at the start of the iteration minus a lowest amount of free memory during the iteration.
14. The method of claim 12 , wherein the first candidate threshold is a fraction of the starting free memory threshold.
15. The method of claim 12 , wherein the second candidate threshold comprises a critical free memory threshold plus a function of the average drop in free memory and the standard deviation.
16. The method of claim 15 , wherein said critical memory threshold is a memory threshold at which one or more non-critical processor threads are blocked.
17. The method of claim 12 , wherein the second candidate threshold is calculated as a critical free memory threshold plus a sum of the average drop in free memory and the standard deviation, multiplied by a margin factor.
18. The method of claim 12 , wherein the garbage collection comprises concurrent, real-time garbage collection.
19. The method of claim 12 , further comprising:
periodically recording a memory allocation rate indicating a rate at which the free memory is being allocated; and
configuring a data structure to associate memory drops during the garbage collection iterations with average memory allocation rates observed before the iterations.
20. The method of claim 19 , further comprising:
for each of the multiple iterations of garbage collection:
calculating a mean rate of allocation of free memory prior to the iteration;
observing a drop in the free memory during the iteration;
reading the data structure to examine an entry corresponding to the observed memory drop;
if the bucket is empty, storing in the bucket the calculated mean rate of allocation of free memory; and
if the bucket stores a rate of allocation higher than the calculated mean rate of allocation of free memory, replacing the stored rate of allocation with a lower of allocation; and
if an increase in the rate of allocation of free memory is observed during said periodic recording, adjusting the starting free memory threshold.