Reference counting: Difference between revisions

Revision as of 20:23, 24 February 2019

Revision as of 00:40, 4 April 2019

Line 1:

{{Use dmy dates|date=August 2012}}

{{More citations needed|date=October 2015}}

{{cleanup HTML|date=February 2019}}

In [[computer science]], '''reference counting''' is a technique of storing the number of [[Reference (computer science)|references]], [[Pointer (computer programming)|pointers]], or [[Handle (computing)|handles]] to a resource such as an object, block of memory, disk space or other resource.

Line 83 ⟶ 82:

| volume = 28

| citeseerx = 10.1.1.15.9106

}}</ref> They introduce the '''update coalescing method''' which coalesces many of the redundant reference count updates. Consider a pointer that in a given interval of the execution is updated several times. It first points to an object <ttcode>O1</ttcode>, then to an object <ttcode>O2</ttcode>, and so forth until at the end of the interval it points to some object <ttcode>On</ttcode>. A reference counting algorithm would typically execute <ttcode>rc(O1)--</ttcode>, <ttcode>rc(O2)++</ttcode>, <ttcode>rc(O2)--</ttcode>, <ttcode>rc(O3)++</ttcode>, <ttcode>rc(O3)--</ttcode>, ..., <ttcode>rc(On)++</ttcode>. But most of these updates are redundant. In order to have the reference count properly evaluated at the end of the interval it is enough to perform <ttcode>rc(O1)--</ttcode> and <ttcode>rc(On)++</ttcode>. The rest of the updates are redundant.

Levanoni and Petrank showed in 2001 how to use such update coalescing in a reference counting collector. When using update coalescing with an appropriate treatment of new objects, more than 99% of the counter updates are eliminated for typical Java benchmarks. In addition, the need for [[atomic operations]] during pointer updates on parallel processors is eliminated. Finally, they presented an enhanced algorithm that may run concurrently with multithreaded applications employing only fine synchronization.<ref>{{cite web|url=http://www.cs.technion.ac.il/%7Eerez/Papers/refcount.pdf |title=An On-the-Fly Reference-Counting Garbage Collector for Java |website=Cs.technion.ac.il |accessdate=2017-06-24}}</ref>