System and method for performance tuning of garbage collection algorithms

• US 10,430,332 B2
• Filed: 03/25/2014
• Issued: 10/01/2019
• Est. Priority Date: 03/25/2013
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Gusak, Oleg
• Primary Examiner(s): Ellis, Matthew J
• Application Number:
  US14/224,293
• Publication Number:
  US 20140289286A1
• Time in Patent Office: 2,016 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466

Abstract

Methods and apparatus are provided for tuning a garbage collection algorithm. The apparatus includes a request generator configured to generate a transaction request including parameters Ta, Te, and M, where Ta represents a transaction request inter-arrival time, Te represents a transaction request execution time, and M represents a transaction request memory allocation amount. The apparatus also includes a memory allocation module, an active request queue, and a garbage collection (GC) module. The memory allocation module is configured to admit the formatted transaction request to the queue if at least M heap memory is available, and to initiate a GC routine if M heap memory is not available.

Claims

1. A garbage collection simulation model executed on a computer system having heap memory and a central processing unit (CPU), wherein the garbage collection simulation module performs an automated process comprising:

generating a plurality of transaction requests by the garbage collection simulation model, each of the plurality of transaction requests including randomly generated parameters representing a randomly generated transaction request inter-arrival time, a randomly generated transaction request execution time, and a randomly generated transaction request memory allocation amount;

allocating portions of the heap memory for use in an active request queue of the garbage collection simulation model to maintain one or more active transaction requests while the active transaction requests are awaiting processing by the CPU module,

wherein, for each of the plurality of transaction requests, the garbage collection simulation model applies the transaction request to the active request queue if an amount of available heap memory is greater than the transaction request memory allocation amount;

in response to the garbage collection simulation model determining that the amount of available heap memory is less than the transaction request memory allocation amount, the garbage collection simulation model initiating a garbage collection routine that interrupts processing of the active transaction requests for a duration of the garbage collection routine, records a time to complete the garbage collection routine, and adds the time to complete the garbage collection routine to the randomly generated transaction request execution times for each of the active transaction requests in the active request queue to create modified transaction request execution times; and

tracking, by the garbage collection simulation model, an average of the modified transaction request execution times to process the plurality of transaction requests in the heap memory, wherein the average of the transaction request execution times evaluates a performance of the garbage collection routine, wherein the garbage collection routine is tuned based upon the average of the modified transaction request execution times tracked by the garbage collection simulation module to thereby improve the performance of the garbage collection routine.

2. The simulation model of claim 1, wherein the central processing unit (CPU) is configured to process the active transaction requests received from the queue.

3. The simulation model of claim 2, wherein the CPU contains a plurality of processing cores, each configured to serially process a respective transaction request thread.

4. The simulation model of claim 1, wherein the transaction requests are generated at periodic rate equal to the inverse of the transaction request inter-arrival time.

5. The simulation model of claim 1, wherein the garbage collection module resumes processing of the interrupted transaction request upon completion of a garbage collection routine.

6. The simulation model of claim 1, wherein the transaction request inter-arrival time, the transaction request execution time, and the transaction request memory allocation amount are random variables modeled using probability distributions.

7. The simulation model of claim 1, wherein the transaction request inter-arrival time, the transaction request execution time, and the transaction request memory allocation amount are based on historical data.

8. The simulation model of claim 1, wherein the simulation model is further configured to mark as garbage the memory associated with a transaction request upon completion of processing the transaction request.

9. The simulation model of claim 1 configured for use in an on-demand, multitenant computing environment.

10. The simulation model of claim 1 implemented using computer code embodied in a non-transitory computer readable medium.

11. A process executed on a physical device having a processor and heap memory in the context of a virtual machine that models operation of a garbage collection routine, the process comprising the steps of:

generating, by the virtual machine, a plurality of requests each having randomly generated parameters comprising a randomly generated execution time of the request and a randomly generated memory allocation amount of the request;

for each of the generated requests, the virtual machine determining an amount of available heap memory and, in response to a determination that the amount of available heap memory is not less than the memory allocation amount, allocating a portion of the heap memory equal to the memory allocation amount to the request and adding the request to an active request pool, and otherwise interrupting each of the requests in the active request pool and initiating the garbage collection routine that frees allocated portions of the heap memory;

completing, by the virtual machine, each of the requests in the active request pool in the execution time of the active request while the garbage collection routine remains inactive; and

in response to the garbage collection routine being initiated, the virtual machine;

identifying a garbage collection time associated with the interrupting garbage collection routine; and

adding the garbage collection time to the times to complete each of the requests in the active request pool; and

tracking an average of the execution times to process each of the plurality of transaction requests in the active request pool to thereby evaluate a performance of the garbage collection routine, and wherein the garbage collection routine is tuned based upon the average of the modified transaction request execution times tracked by the garbage collection simulation module to thereby improve the performance of the garbage collection routine.

12. The process of claim 11, further comprising:

checking, in response to receiving and prior to determining, the state of a garbage collection (GC) routine.

13. The process of claim 12, further comprising:

waiting, if the garbage collection routine is active, until the active garbage collection routine is completed before determining; and

if the garbage collection routine is not active, determining the amount of available heap memory.

14. The process of claim 11, wherein adding the request to the active request pool comprises starting an execution clock associated with the request.

15. The process of claim 14, further comprising:

setting an execution clock for the request to the execution time if the request processing is not interrupted by the garbage collection; and

if processing the request is interrupted by the garbage collection routine, identifying a garbage collection time associated with the interrupting garbage collection routine; and

setting the execution clock for the request to a second time equal to the execution time plus the garbage collection time if the request processing is interrupted by the garbage collection routine.

16. The process of claim 11, further comprising:

interrupting all active transaction request processing upon triggering a garbage collection routine.