Understanding Strong & Weak References and Caches

http://weblogs.java.net/blog/enicholas/archive/2006/05/understanding_w.html

Some time ago I was interviewing candidates for a Senior Java Engineer position. Among the many questions I asked was "What can you tell me about weak references?" I wasn't expecting a detailed technical treatise on the subject. I would probably have been satisfied with "Umm... don't they have something to do with garbage collection?" I was instead surprised to find that out of twenty-odd engineers, all of whom had at least five years of Java experience and good qualifications, only two of them even knew that weak references existed, and only one of those two had actual useful knowledge about them. I even explained a bit about them, to see if I got an "Oh yeah" from anybody -- nope. I'm not sure why this knowledge is (evidently) uncommon, as weak references are a massively useful feature which have been around since Java 1.2 was released, over seven years ago.

Now, I'm not suggesting you need to be a weak reference expert to qualify as a decent Java engineer. But I humbly submit that you should at least know what they are -- otherwise how will you know when you should be using them? Since they seem to be a little-known feature, here is a brief overview of what weak references are, how to use them, and when to use them.

Strong references

First I need to start with a refresher on strong references. A strong reference is an ordinary Java reference, the kind you use every day. For example, the code:

StringBuffer buffer = new StringBuffer();

creates a new StringBuffer() and stores a strong reference to it in the variable buffer. Yes, yes, this is kiddie stuff, but bear with me. The important part about strong references -- the part that makes them "strong" -- is how they interact with the garbage collector. Specifically, if an object is reachable via a chain of strong references (strongly reachable), it is not eligible for garbage collection. As you don't want the garbage collector destroying objects you're working on, this is normally exactly what you want.

When strong references are too strong

It's not uncommon for an application to use classes that it can't reasonably extend. The class might simply be marked final, or it could be something more complicated, such as an interface returned by a factory method backed by an unknown (and possibly even unknowable) number of concrete implementations. Suppose you have to use a class Widget and, for whatever reason, it isn't possible or practical to extend Widget to add new functionality.

What happens when you need to keep track of extra information about the object? In this case, suppose we find ourselves needing to keep track of each Widget's serial number, but the Widget class doesn't actually have a serial number property -- and because Widget isn't extensible, we can't add one. No problem at all, that's what HashMaps are for:

serialNumberMap.put(widget, widgetSerialNumber);

This might look okay on the surface, but the strong reference to widget will almost certainly cause problems. We have to know (with 100% certainty) when a particular Widget's serial number is no longer needed, so we can remove its entry from the map. Otherwise we're going to have a memory leak (if we don't remove Widgets when we should) or we're going to inexplicably find ourselves missing serial numbers (if we remove Widgets that we're still using). If these problems sound familiar, they should: they are exactly the problems that users of non-garbage-collected languages face when trying to manage memory, and we're not supposed to have to worry about this in a more civilized language like Java.

Another common problem with strong references is caching, particular with very large structures like images. Suppose you have an application which has to work with user-supplied images, like the web site design tool I work on. Naturally you want to cache these images, because loading them from disk is very expensive and you want to avoid the possibility of having two copies of the (potentially gigantic) image in memory at once.

Because an image cache is supposed to prevent us from reloading images when we don't absolutely need to, you will quickly realize that the cache should always contain a reference to any image which is already in memory. With ordinary strong references, though, that reference itself will force the image to remain in memory, which requires you (just as above) to somehow determine when the image is no longer needed in memory and remove it from the cache, so that it becomes eligible for garbage collection. Once again you are forced to duplicate the behavior of the garbage collector and manually determine whether or not an object should be in memory.

Weak references

A weak reference, simply put, is a reference that isn't strong enough to force an object to remain in memory. Weak references allow you to leverage the garbage collector's ability to determine reachability for you, so you don't have to do it yourself. You create a weak reference like this:

WeakReference weakWidget = new WeakReference(widget);

and then elsewhere in the code you can use weakWidget.get() to get the actual Widget object. Of course the weak reference isn't strong enough to prevent garbage collection, so you may find (if there are no strong references to the widget) that weakWidget.get() suddenly starts returning null.

To solve the "widget serial number" problem above, the easiest thing to do is use the built-in WeakHashMap class. WeakHashMap works exactly like HashMap, except that the keys (not the values!) are referred to using weak references. If a WeakHashMap key becomes garbage, its entry is removed automatically. This avoids the pitfalls I described and requires no changes other than the switch from HashMap to a WeakHashMap. If you're following the standard convention of referring to your maps via the Map interface, no other code needs to even be aware of the change.

Reference queues

Once a WeakReference starts returning null, the object it pointed to has become garbage and the WeakReference object is pretty much useless. This generally means that some sort of cleanup is required; WeakHashMap, for example, has to remove such defunct entries to avoid holding onto an ever-increasing number of dead WeakReferences.

The ReferenceQueue class makes it easy to keep track of dead references. If you pass a ReferenceQueue into a weak reference's constructor, the reference object will be automatically inserted into the reference queue when the object to which it pointed becomes garbage. You can then, at some regular interval, process the ReferenceQueue and perform whatever cleanup is needed for dead references.

Different degrees of weakness

Up to this point I've just been referring to "weak references", but there are actually four different degrees of reference strength: strong, soft, weak, and phantom, in order from strongest to weakest. We've already discussed strong and weak references, so let's take a look at the other two.

Soft references

A soft reference is exactly like a weak reference, except that it is less eager to throw away the object to which it refers. An object which is only weakly reachable (the strongest references to it are WeakReferences) will be discarded at the next garbage collection cycle, but an object which is softly reachable will generally stick around for a while.

SoftReferences aren't required to behave any differently than WeakReferences, but in practice softly reachable objects are generally retained as long as memory is in plentiful supply. This makes them an excellent foundation for a cache, such as the image cache described above, since you can let the garbage collector worry about both how reachable the objects are (a strongly reachable object will never be removed from the cache) and how badly it needs the memory they are consuming.

Phantom references

A phantom reference is quite different than either SoftReference or WeakReference. Its grip on its object is so tenuous that you can't even retrieve the object -- its get() method always returns null. The only use for such a reference is keeping track of when it gets enqueued into a ReferenceQueue, as at that point you know the object to which it pointed is dead. How is that different from WeakReference, though?

The difference is in exactly when the enqueuing happens. WeakReferences are enqueued as soon as the object to which they point becomes weakly reachable. This is before finalization or garbage collection has actually happened; in theory the object could even be "resurrected" by an unorthodox finalize() method, but the WeakReference would remain dead. PhantomReferences are enqueued only when the object is physically removed from memory, and the get() method always returns null specifically to prevent you from being able to "resurrect" an almost-dead object.

What good are PhantomReferences? I'm only aware of two serious cases for them: first, they allow you to determine exactly when an object was removed from memory. They are in fact the only way to determine that. This isn't generally that useful, but might come in handy in certain very specific circumstances like manipulating large images: if you know for sure that an image should be garbage collected, you can wait until it actually is before attempting to load the next image, and therefore make the dreaded OutOfMemoryError less likely.

Second, PhantomReferences avoid a fundamental problem with finalization: finalize() methods can "resurrect" objects by creating new strong references to them. So what, you say? Well, the problem is that an object which overrides finalize() must now be determined to be garbage in at least two separate garbage collection cycles in order to be collected. When the first cycle determines that it is garbage, it becomes eligible for finalization. Because of the (slim, but unfortunately real) possibility that the object was "resurrected" during finalization, the garbage collector has to run again before the object can actually be removed. And because finalization might not have happened in a timely fashion, an arbitrary number of garbage collection cycles might have happened while the object was waiting for finalization. This can mean serious delays in actually cleaning up garbage objects, and is why you can get OutOfMemoryErrors even when most of the heap is garbage.

With PhantomReference, this situation is impossible -- when a PhantomReference is enqueued, there is absolutely no way to get a pointer to the now-dead object (which is good, because it isn't in memory any longer). Because PhantomReference cannot be used to resurrect an object, the object can be instantly cleaned up during the first garbage collection cycle in which it is found to be phantomly reachable. You can then dispose whatever resources you need to at your convenience.

Arguably, the finalize() method should never have been provided in the first place. PhantomReferences are definitely safer and more efficient to use, and eliminating finalize() would have made parts of the VM considerably simpler. But, they're also more work to implement, so I confess to still using finalize() most of the time. The good news is that at least you have a choice.

Conclusion

I'm sure some of you are grumbling by now, as I'm talking about an API which is nearly a decade old and haven't said anything which hasn't been said before. While that's certainly true, in my experience many Java programmers really don't know very much (if anything) about weak references, and I felt that a refresher course was needed. Hopefully you at least learned a little something from this review.


Comments
Comments are listed in date ascending order (oldest first) | Post Comment

*

In reply to the implicit question from richunger: The Sun JRE does treat SoftReferences differently from WeakReferences. We attempt to hold on to object referenced by a SoftReference if there isn't pressure on the available memory. One detail: the policy for the "-client" and "-server" JRE's are different: the -client JRE tries to keep your footprint small by preferring to clear SoftReferences rather than expand the heap, whereas the -server JRE tries to keep your performance high by preferring to expand the heap (if possible) rather than clear SoftReferences. One size does not fit all.

A nit: since JDK-1.5.0, the java.lang.ref.Reference class has been generified. So, to create one you use

WeakReference weakWidget = new WeakReference(widget);

and weakWidget.get() returns a Widget, just you'd expect.

There are are some details about what the remove() method on a ReferenceQueue returns, but I'll save that for my next job interview.

Posted by: peterkessler on May 06, 2006 at 03:04 PM

*
I never really learned the difference between weak & soft until this guy ran into it: http://weblog.ikvm.net/PermaLink.aspx?guid=ec45dec2-ec22-4079-9b78-d06e15ddabe7 Thanks for bringing up Phantom References, I don't think I'd ever heard of them.

Posted by: ronaldyang on May 05, 2006 at 01:56 PM

*
Very nice writeup indeed. I must admit I was unaware of phantom references. I heard somewhere that sun's jre does indeed treat soft references as weak references. Don't know if that's still (or ever really was) the case, but I remember reading it somewhere.

One other common use of weak references is the WeakListener, which prevents an object from hanging around simply because another object is listening on it.

Posted by: richunger on May 05, 2006 at 01:03 PM

*
A very important use of PhantomReferences is in DGC (Distributed GC like in RMI). You most certainly do not want to perform remote notification in the GC thread.

Posted by: ianschneider on May 05, 2006 at 08:56 AM

*
Good blog. I have also found LinkedHashMap very useful for caching.

Posted by: abhijit_jadeja on May 05, 2006 at 06:46 AM

*
Nice entry about a not too well known feature of Java that come quite handy.

I fortunately discovered them long ago thanks to an article at java.com (when it was still called like that) and I've since used Soft References in a few occasions, like creating smart caches of pre-compiled objects (XSLT sheets in my case) that are able to be garbage collected if a sudden peak in memory usage occurs.

You simply re-create them the next time you need them and if the memory usage has gone down, you go back to normal.

I actually wrote an article about using Soft References for such purpose, but it's in spanish ;).

Implementación de Caches Inteligentes Mediante "Soft References"

Thanks again for spreading the knowledge!
D.

Posted by: greeneyed on May 05, 2006 at 04:57 AM

*
Good article. I must confess to being hazy as to the difference between Soft, Weak and Phantom - the API docs aren't terribly descriptive. It's also good to finally get some justification for why on earth anyone would want to use a PhantomReference.

Posted by: skaffman on May 05, 2006 at 12:04 AM

*
Very nice blog entry. I was talking with the development manager of a large all-Java shop one time and I asked him about his need for profiling tools to track down memory leaks. He replied, "We seem to not have a problem with memory leaks since we started using weak references."

Posted by: gsporar on May 04, 2006 at 06:57 PM

*
weak references are essential, alot of associative memory leaks can be removed just by using those babies. I also use them in simple test cases to show that leaks have been removed.

leouser

Posted by: leouser on May 04, 2006 at 05:24 PM

OpenSource Website Composing Tools

OpenSource Website Composing Tools:

Drupal
http://drupal.org

WordPress
http://wordpress.org/

Visitor Pattern Vs. Double Dispatch

http://java.sys-con.com/read/140105.htm

Deriving the Visitor Pattern: A Review and Discussion

Like most other self-respecting developers I had also read the GoF book, including the section on the visitor pattern. However, when a colleague came over to me with a question, I could not initially justify the complexity of the example code I saw in the book. What follows is a discussion of why the visitor pattern is the way it is.

Brief Review of the Pattern
The definitive description of the pattern is in the GoF book Design Patterns, Chapter 5 (pp 331-344)(see References section). The Wikipedia has a concise and good description, which formed the basis for my brief review here. The visitor pattern is classified as a Behavioral pattern, so the thing to notice is the way in which the classes and objects interact and distribute responsibility. A typical application of this pattern occurs in the following scenario: we have a number of elements in an object structure (common structures include trees & lists) and we want to perform a bunch of disparate operations (e.g. printing or cloning each element) on the elements of the structure.

The visitor pattern is a way of separating the operation from the object structure and a way of collecting together the different implementations of an operation for different kinds of elements in the object structure. A Visitor class is created which knows how to perform a particular operation on the different kinds of elements in the object structure. Each type of element in the structure defines an accept() method that can accept any kind of Visitor. The visitor is passed to each element in the structure in turn, by calling its accept() method and the Visitor then performs the operation on the visited element. One important consequence of this separation of object structure and operation is that we can later add a new operation (a new kind of Visitor) without having to modify the element classes of the object structure.

Each type of Visitor defines several visit()methods, one for each kind of element. The basic insight is that the precise set of instructions to execute (i.e. the method or function to call) depends on the run-time types of both the Visitor & the visited element. Java only lets us call different methods based on the run-time type of one object (via virtual functions), so the pattern advocates a clever solution: The second dependency on the type of element visited is first resolved by polymorphically calling the accept() method of the visited element. accept() then resolves the first dependency by turning around and polymorphically calling the visit()method for its class.

An Example
Before this description gets too confusing, let us study the pattern in the context of a concrete problem: Let us say we need to traverse a list collecting node-specific information. The list has two kinds of nodes, say, Red and Black, which needed to be processed differently. It seems like an ideal application for the visitor pattern. Listing 1 shows the code. (All code samples in this article use a J2SE 5.0 compatible compiler.)

To me and my colleague, this initially seemed like an overly complex solution for a simple problem. NodeVisitor.doVisit() calls into the Node's accept methods, which simply delegates back into NodeVisitor. Furthermore, the accept() methods of RedNode and BlackNode are almost identical. Finally, notice that if we now add a GreenNode class, we need to add a new visitGreen() method to the NodeVisitor class and re-compile it (not to speak of the almost redundant implementation of accept() in the GreenNode class). Ugh! This does not seem kosher by any OO standard.

The Need for the accept() Methods
Novice armchair Java developers might ask why we can't do something simpler, like Listing 2, for example, without touching the Node interface, or the classes RedNode and BlackNode which implement it.

Listing 2 has two significant differences from the previous. First, there is no redundant method (namely accept()) for each node type to implement. Second, we use function name overloading for the visit() implementations, thus enabling the "clever" foreach loop, which iterates over each node and calls the appropriate overloaded version of visit() depending on the type of the current element. With this, we hope to contain all the visiting logic within NodeVisitor.

Alas, real developers have a more difficult job than arm-chair developers! If you are using a language like Java or C++, an overloaded function name like visit() has to get resolved at compile time. Thus line 6.iii will not compile because none of the visit() methods provided in NodeVisitor know how to accept a generic "Node" as argument.

For line 6.iii to work the way we want it to, the decision on what operation needs to be performed has to be delayed until we can determine at runtime the type of the node n being examined in the current iteration of the for-each loop.

Traditional OO languages (Java, C++ etc) provide us with one standard tool for delaying function resolution until run-time: virtual functions. Thus, in Listing 1, 6.iii is modified to a virtual function call n.accept(nv). So the actual function that gets called is decided at run-time. The version called then delegates work by invoking the right version of NodeVisitor.visit().

So Why Not Just Use Plain Vanilla Inheritance?
The explanation I just gave is good, but not good enough. I can almost hear you ask: why doesn't accept() do the work itself? Why does it have to delegate back to NodeVisitor? There are three reasons:

1. Accumulating state: If you read the problem I presented closely, you will notice that I specified a need to collect node-specific information. Since the doVisit passes the same NodeVisitor instance to each accept(), the visitor can be used to accumulate state across the different Node objects. For example, say you have an Employee HR application where the Red nodes represent employees, the Black nodes represent managers, visitRed() calculates the pay raises for programmers, and visitBlack the pay raises for managers. The NodeVisitor nv could print a report of the total increase in salary expense at the end of the for loop.

2. Supporting more than one visitor (the need for double dispatch): Say the next version of your Employee HR application needs to add a new HRPolicyVisitor that checks for compliance with some HR policy and the implementation is different for managers and programmers.

To accommodate both the types of Visitors, we introduce an additional layer of indirection - an abstract EmployeeNodeVisitor interface with virtual visitXXX() functions for each type of element to visit, namely visitProgrammer() & visitManager(). The old PayRaiseVisitor and the new HRPolicyVisitor both implement EmployeeNodeVisitor. The decision on which version of visit() gets called now gets determined by a two-step process. The first step is as before. The node type of the visited element n in the foreach loop determines which version of the virtual function accept() gets called. In the second step, the type of the EmployeeVisitor passed in to accept() determines the (virtual function) version of visitXXX() called. The source files that come with this article show the skeleton of this implementation. Figure 1 illustrates the sequence of calls from both doPayHike(), which uses a PayRaiseVisitor to raise the pay of each employee, and doEnforcePolicy() which uses a HRPolicyVisitor to check HR policy compliance.

This technique, where the types of two objects are used to select the operation invoked is known as double dispatch. By contrast, single dispatch uses the type of one object to select the operation invoked. One known implementation of single dispatch is virtual functions. Since Java and C++ support only this form of single dispatch, the pattern simulates double dispatch by using single dispatch twice!

3. Separation of concerns: A concern is any focus of interest in a program. A classic tenet of good software design is that the different concerns of a program must be broken down into separate modules that have little or no overlap. In the Employee HR program , visitProgrammer and visitManager of a particular visitor have more commonality than the two visitProgrammers of the different visitors or the two visitManagers of the different visitors. In fact, the methods in a given visitor may even share state information as described in 1 above. This makes the Visitor pattern a good way to organize code by separation of concerns.

Notice also that as a consequence of this way of organizing code, it is extremely easy to add a new visitor operation, but adding a new kind of node requires adding a new visitXXX method to all the Visitors.

If none of the above three reasons apply, you would be better off not delegating the work of accept() back to a separate visitXXX() method.i.e. plain vanilla inheritance would be more appropriate than an application of the Visitor pattern. On the other hand, if any of the above reasons apply, the Visitor pattern would be a good solution for you.

But This Still Does Not Preclude Overloading the visit() Methods...
You might still have one lingering question about Listing 1: Why can't we use function name overloading instead of the different visit<>() methods (as in Listing 3)?

The short answer is that nothing prevents you from doing this; Listing 3 is just as correct as Listing 1 For the last word, however, I will have to defer to the GoF, who write the following in a footnote:

We could use function overloading to give these operations the simple name, like Visit, since the operations are already differentiated by the parameter they're passed. There are pros and cons to such overloading. On the one hand, it reinforces the fact that each operation involves the same analysis, albeit on a different argument. On the other hand, that might make what's going on at the call site less obvious tosomeone reading the code. It really boils down to whether you believe function overloading is good or not [in this situation].

Conclusion
In this article we reviewed the Visitor pattern and "derived" it from an armchair sketch of the functionality we wanted: the ability to accumulate state over elements of an object structure, the separation of the operations from the object structure, and the ability to add new operations without recompiling the element types. These requirements called for a "double dispatch"; i.e. the precise method to call for "visiting" each element in the structure depended on two runtime types: the type of Visitor and the type of the visited element. The Visitor pattern was shown to be a way to simulate double dispatch using virtual functions, a form of single dispatch.

References

* Gamma, et al. Design Patterns: Elements of Reusable Object-Oriented Software, 1995, Addison-Wesley, Reading, MA.
* Wikipedia contributors, "Visitor pattern," Wikipedia: The Free Encyclopedia, http://en.wikipedia.org/wiki/Visitor_pattern (accessed Aug 19, 2005)

© 2008 SYS-CON Media Inc.