A Unified Theory of Garbage Collection
Blog Post by: Kaitlyn Khan, Hamza Rashid, Tom Reingold, Tong Chen Tracing garbage collection and reference counting have many parallels. Tracing starts at the roots and aims to find the live data. Reference counting starts from anti-roots, which are the objects whose reference counts are zero, and aims to find the dead data. In this sense reference counting is the complement of tracing. Tracing starts from a count of zero, and increments to the true count. Reference counting starts with an excessive count and decrements to the true count.(HR) As mentioned above, tracing will initialize the count to zero. A work-list, which is the set of objects to be processed, is used in the algorithm. While iterating through the list, if a new vertex is encountered, all of it's outer edges will be added to the work-list. Once the loop is finished all the live nodes will be discovered. A separate function is used to return the unused nodes to free the storage.(HR) Reference cou...