Reference counting: practice and trouble Reference counting: practice and trouble

Reference counting is a well known strategy used to provide simple garbage collection. As automatic garbage collection, it has a lot of issues among which not correctly handling circular data-structures is the most obvious.
On the other hand, used for semi-automatic GC, it is pretty accurate, easy to implement and solves probably most of the use cases. People using C++11 shared_ptr probably see what I mean.


So, while ref-counting can be useful tool in a lot of cases (like in my simple C piece of code) using it in multithreaded environment may become expensive.

I started this article because I was, once again, trap by the false idea that we can use ref-count (in some specific cases) safely, but as you can see, removing constraints doesn’t solve the synchronization issue. While I’m speaking, there isn’t official implementation of real non-blocking memory reclamation techniques like hazard pointers. A userland RCU implementation is available (and I’m in the process of writing my own in C++ style) but it’s not really portable (at least, it works on most modern Unixes, but not all architectures.)

There exists other approaches, like tagged pointers, that solves ABA problems in lock-free data structures, but as it seems, deferred memory reclamations seems to be pretty efficient. I strongly encourage you to read RCU papers (both web articles about its uses in Linux and academics ones.) With working RCU, a lot of concurrent accesses problems can be solved easily with almost no specific code and almost no overhead on the reader side.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s