Optimizing heap memory usage
View Patent ↗This disclosure provides a computing system and method to profile a program for finding potential optimization in heap usage by reducing lag and drag in lifetimes of heap memory blocks. The process consists of three steps. First, an instrumentation engine analyzes a given program, and inserts additional code at interesting locations to collect needed information. Second, when the instrumented program is executed on a set of test cases, runtime data is collected. Third, since this data could be relatively large for a complex and long running program, data is processed to present it to a user in useful ways so that the programmer can improve the heap utilization in the program.
1. A computer implemented method for optimizing usage of heap memory, the method comprising
inserting additional program code instructions at predefined locations into existing program code of a computer program, the additional instructions configured to search a header of a heap memory block to identify, data associated with lag and drag lifetimes of the heap memory block;
executing the computer program with the inserted additional program code;
creating during execution of the computer program a header for a heap memory block allocated in heap memory, collecting runtime data comprising timestamps associated with lag and drag lifetimes of the heap memory and storing the runtime data in the header of the heap memory block;
identifying subsequent to the execution of the computer program from the collected runtime data the lag and drag lifetimes associated with the heap memory block;
creating a bit map table comprising two bits for all allocated heap memory;
wherein for every use of the heap memory:
if a first use bit in the bit map table is not set, searching for the header of the corresponding heap memory block and recording the current timestamp as the first use timestamp;
updating the first use bit for all addresses associated with that heap memory block in the bit map table for that memory as 1; and
setting a last use bit in the table for that memory to 1.
2. The method of claim 1 , wherein the header is configured to record a size and allocation time for each of the heap memory blocks when the heap memory block is allocated.
3. The method of claim 1 , wherein collecting runtime data further comprises
recording a de-allocation time in the header; and
dumping the header into a file when the heap memory block is freed.
4. The method of claim 1 , wherein the first bit indicates first use of the heap memory and the second bit indicates last use of the heap memory.
5. The method of claim 1 , wherein the last use bit is always set regardless of whether the first use bit is set.
6. The method of claim 1 , further comprises:
performing a census after a user defined duration comprising sequentially sweeping through the heap memory wherein if a header is found for the heap memory block; reading the size of the heap memory block in the header; checking the bit map table for all addresses associated with the heap memory block; and,
recording a current timestamp as a last used timestamp in the header if any last use bit has a value 1 for a memory in that heap memory block; and
setting the last use bit for all memory in that heap memory block to a value zero.
7. A method for optimizing heap memory usage, the method comprising
inserting additional program code instructions at predefined locations into existing program code of a computer program, the additional instructions configured to search a header of a heap memory block to identify, data associated with lag and drag lifetimes of the heap memory block;
executing the computer program with the inserted additional program code;
creating during execution of the computer program a header for a memory block allocated in heap memory, the header configured to record a size and allocation time for each of the heap memory blocks when the heap memory block is allocated, collecting runtime data, comprising timestamps associated with lag and drag lifetimes of the heap memory, and storing the runtime data in the header of the heap memory block and, in response to a freeing of the heap memory block, recording a de-allocation time in the header, dumping the header into a file;
identifying subsequent to the execution of the computer program lag and drag lifetimes associated with the heap memory block from a bit map table comprising two bits the first bit indicates first use of the heap memory and the second bit indicates last use of the heap memory wherein for every use of the heap memory; and,
if the first use bit in the bit map table is not set, searching for a header of a corresponding heap memory block and recording a current timestamp as first use timestamp; updating the first use bit for all addresses associated with that heap memory block in the bit map table for that memory as 1; and setting the last use bit in the table for the corresponding heap memory block to 1.
8. The method of claim 7 , further comprises:
performing a census after a user defined duration comprising sequentially sweeping through the heap memory, wherein if a header is found for the heap memory block during the census, reading the size of the heap memory block in the header, checking the bit map table for all addresses associated with the heap memory block, recording a current timestamp as a last used timestamp in the header if any last use bit has a value 1 for a memory in that heap memory block, and setting the last use bit for all memory in that heap memory block to a value zero.
9. A computing system comprising a processor, a memory, a computer readable medium coupled to the processor; and computer instruction encoded in the computer readable medium and executable by the processor causing the processor to perform the steps of:
inserting additional program code instructions at predefined locations into existing program code of a computer program, the additional instructions configured to search a header of a heap memory block to identify, data associated with lag and drag lifetimes of the heap memory block;
executing the computer program with the inserted additional program code;
creating during execution of the computer program a header for a heap memory block allocated in heap memory, collecting runtime data comprising timestamps associated with lag and drag lifetimes of the heap memory and storing the runtime data in the header of the heap memory block; and
identifying subsequent to the execution of the computer program from the collected runtime data the lag and drag lifetimes associated with the heap memory block;
wherein a bit map table is created comprising two bits for all allocated heap memory;
wherein for every use of heap memory:
if a first use bit in the bit map table is not set, searching for the header of the corresponding heap memory block and recording the current timestamp as the first use timestamp;
updating the first use bit for all addresses associated with that heap memory block in the bit map table for that memory as 1; and,
setting a last use bit in the table for that memory to 1.
10. The system of claim 9 , wherein the header is configured to record a size and allocation time for each of the heap memory blocks.
11. The system of claim 9 , wherein collecting runtime data further comprises recording a de-allocation time in the header; and dumping the header into a file when the heap memory block is freed.
12. The system of claim 9 , wherein the first bit indicates first use of the heap memory and the second bit indicates last use of the heap memory.
13. The system of claim 9 , further comprises:
performing a census after a user defined duration comprising sequentially sweeping through the heap memory wherein if a header is found for the heap memory block; reading the size of the heap memory block in the header; checking the bit map table for all addresses associated with the heap memory block; and,
recording a current timestamp as a last used timestamp in the header if any last use bit has a value 1 for a memory in that heap memory block; and
setting the last use bit for all memory in that heap memory block to a value zero.