Freeing memory safely with low performance overhead in a concurrent environment
Freeing memory safely with low performance overhead in a concurrent environment is described. An example method includes creating a reference count for each sub block in a global memory block, and each global memory block includes a plurality of sub blocks aged based on respective allocation time. A reference count for a first sub block is incremented when a thread operates a collection of data items and accesses the first sub block for a first time. Reference counts for the first sub block and a second sub block are lazily updated. Subsequently, the sub blocks are scanned through in the order of their age until a sub block with a non-zero reference count is encountered. Accordingly, one or more sub blocks whose corresponding reference counts are equal to zero are freed safely and with low performance overhead.
1. A computer-implemented method for memory management, comprising:
creating a reference count for each sub block in a global memory block, wherein the global memory block includes a plurality of sub blocks aged based on respective allocation time;
incrementing a reference count for a first sub block when a thread operates on a collection of data items and accesses the first sub block for a first time;
maintaining a reference count for a second sub block, wherein the reference count for the second sub block is not updated when the thread operates on the collection of data items when accessing, the second sub block, and wherein the second sub block has an allocation time after that of the first sub block;
lazily updating reference counts for the first sub block and a third sub block when the thread returns with a new collection of data items and accesses the third sub block, different from the first sub block, wherein the reference count for the first sub block is decremented and the reference count for the third sub block is incremented; and
freeing one or more sub blocks in the order of their age, wherein reference counts of the sub blocks to be freed are equal to zero.
2. The method of claim 1 , wherein freeing further comprises:
scanning through the one or more sub blocks in the order of their age until encountering a sub block with a non-zero reference count.
3. The method of claim 2 , further comprising:
scanning through the one or more sub blocks whose corresponding reference counts are equal to zero before the thread operates on the collection of data items.
4. The method of claim 2 , further comprising:
aborting the scanning and proceeding with operating on the collection of data items if a first thread finds a second thread is in the process of freeing the one or more sub blocks.
5. The method of claim 1 , farther comprising:
caching a reference to the first sub block in a local storage of the thread when the thread operates on the collection of data items and accesses the first sub block for the first time.
6. The method of claim 1 , wherein lazily updating further comprises:
decrementing the reference count for the first sub block when the thread is destroyed.
7. The method of claim 1 ,
wherein the reference count for the second sub block is not updated when the thread completes operating on the collection of data items and leaves the second sub block.
8. The method of claim 1 , wherein access to the reference number for each sub block is synchronized using a lock.
9. A system for memory management, comprising:
a reference count creator, configured to create a reference count for each sub block in a global memory block, wherein the global memory block includes a plurality of sub blocks aged based on respective allocation time;
a reference count updater, configured to:
increment a reference count for a first sub block when a thread operates on a collection of data items and accesses the first sub block for a first time;
maintain a reference count for a second sub block, wherein the reference count for the second sub block is not updated when the thread operates on the collection of data items when accessing the second sub block, and wherein the second sub block has an allocation time after that of the first sub block; and
lazily update reference counts for the first sub block and a second sub block when the thread returns with a new collection of data items and accesses the third sub block different from the first sub block, wherein the reference count for the first sub block is decremented and the reference count for the third sub block is incremented; and
a block freer, configured to free one or more sub blocks in the order of their age, wherein reference counts of the sub blocks to be freed are equal to zero.
10. The system of claim 9 , wherein the block freer is further configured to:
scan through the one or more sub blocks in the order of their age until encountering a sub block with a non-zero reference count.
11. The system of claim 10 , wherein the block freer is further configured to:
scan through the one or more sub blocks Whose corresponding reference counts are equal to zero before the thread operates on the collection of data items.
12. The system of claim 10 , wherein the block freer is further configured to:
abort the scanning and proceed with operating on the collection of data items if a first thread finds a second thread is in the process of freeing the one or more sub blocks.
13. The system of claim 9 , further comprising:
a reference cacher, configured to cache a reference to the first sub block in a local storage of the thread when the thread operates on the collection of data items and accesses the first sub block for the first time.
14. The system of claim 9 , wherein the reference count updater is further configured to:
decrement the reference count for the sub block which is cached in the local storage of the thread, when the thread is destroyed.
15. The system of claim 9 ,
wherein the reference count for the second sub block is not updated when the thread completes operating on the collection of data items and leaves the second sub block.
16. The system of claim 9 , wherein, access to the reference number for each sub block is synchronized using a lock.
17. A computer program product comprising a computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to perform operations comprising:
creating a reference count for each sub block in a global memory block, wherein the global memory block includes a plurality of sub blocks aged based on respective allocation time;
incrementing a reference count for a first sub block when a thread operates on a collection of data items and accesses the first sub block for a first time;
maintaining a reference count for a second sub block, wherein the reference count for the second sub block is not updated when the thread operates on the collection of data items when accessing the second sub block, and wherein the second sub block has an allocation time after that of the first sub block;
lazily updating reference counts for the first sub block and a third sub block when the thread returns with a new collection of data items and accesses a third sub block different from the first sub block, wherein the reference count for the first sub block is decremented and the reference count for the third sub block is incremented; and
freeing one or more sub blocks in the order of their age, wherein reference counts of the sub blocks to be freed are equal to zero.
18. The computer program product of claim 17 , the freeing further comprising:
scanning through the one or more sub blocks in the order of their age until encountering a sub block with a non-zero reference count.