Software Development

If you're a C++ programmer, then you should be well aware of smart pointers or reference counting. Instead of dealing directly with a pointer, you use a container that also has a shared reference counter. When the counter reaches zero, then it deletes the object that the pointer is referencing.

So far, so good. One problem that comes up is that sometimes you need to use third party software or whatnot where they take raw pointers. There are some cases where they allow callbacks as well and you no longer have a shared pointer when this is really what you need. Whatever the situation, what I'm trying to get at is that sometimes you are given the raw pointer when you really need the shared pointer. Sometimes you can leave the object itself with a reference to an existing shared pointer. This way, you can always copy the shared pointer. But what if you can't do that either? Also, what if you only ever want one copy of a certain object, but you don't know if it already exists?

Enter interning. This is where you have a repository of shared objects that are associated with their reference counters. Interning involves more than just keeping unique references to pointers. It actually makes sure that only one copy of any given object exists. So if you create a new object and pass it to an interned pointer, that object will get deleted and replaced with a different pointer if the object in question already exists in the repository (IOW, if the objects' equality operator returns true). So any time you want to share an object, you can look it up in a collection. If it's there, the counter is incremented, otherwise the object is added to the collection. I ended up writing an interned_pointer class that did all of this automatically including the creation of the shared collection. The class works exactly like a shared pointer except that when you use a raw pointer, it looks up the object in the repository. It is wise to copy from an existing interned pointer whenever possible because it can update the reference count right directly without searching.

The great thing about interning is that you can obtain a reference count to any pointer anywhere anytime. The problem with this is that it requires searching every time unless you copy from a pre-existing interned pointer. That searching can be VERY costly if you do it too often (ie. use raw pointers to create an interned pointer).

Binary search is logn. That's not bad. But there's gotta be something that can make it faster. With cheaper and faster memory, I'm wondering if we won't find ourselves one day using interned pointers instead of shared pointers. The only roadblock that I can see at the present is search time in two specific cases. Searching for an object when we think it may already be shared. And when we create a new interned pointer. In both cases, searches must be done to make sure it doesn't already exist. The first case can be alleviated by making sure to copy interned pointers from other pre-existing interned pointers when possible. But when creating a new interned pointer, there is no choice. A search must happen if only to store the pointer in the repository. And that can be costly when used with temporary objects.

Interning seems like an underused, yet extremely powerful technique. One specific advantage of interning over other techniques is that you can compare pointers for equality or inequality once they've been created. For example, when comparing strings, you can compare their pointers if they match instead of doing a character by character comparison since uniqueness is guaranteed by the interning process. I suppose another kind of weak interning could be done on pointers only where the pointer is guaranteed to be unique instead of the object itself.

If anyone has ideas about this, specifically about speeding up searches and inserts, please post them here.