Home > java > Google Collections API

Google Collections API

November 24th, 2008 Leave a comment Go to comments

One aspect of the jsoar implementation that I wasn’t sure about in the beginning was the management of symbols. In the Soar kernel, a symbol represents an id, attribute or value in a working memory element. They boil down to either identifiers, or wrappers around atomic data types like string, double, or int.  The kernel caches symbols so that they can be compared quickly using pointer identity rather than the usual equals() and hashCode() approach.  These comparisons are the “inner loop” of the rete algorithm. The cache also helps with memory consumption where it’s not uncommon for a symbol, like input-link to appear in many rules.

In the C implementation of the Soar kernel, symbols are tediously reference counted. When the reference count goes to zero, the symbol is no longer in use and can be removed from the cache. In jsoar, I obviously didn’t want to do reference counting. We’re trying to make things easier here. But, if the symbols are cached, they’ll always be referenced and thus, never removed from the cache and garbage collected.

Before I go further, the symbol cache is basically a map from atomic value (like a string) to symbol, something like Map<String, StringSymbol> strings .

So, I started hunting around and quickly discovered Java’s support for weak references (I cheated a bit because I already knew they existed, just hadn’t used them before). A weak reference is a reference that does not stop the garbage collector from reclaiming an object. Nice.  Even better, Java includes WeakHashMap which sounds kind of like what I want, i.e. a map that will remove entries when a value is garbage collected. Unfortunately, WeakHashMap puts a weak reference on keys rather than values which is the opposite of what I want.

Next, I started looking into using a ReferenceQueue to implement what I wanted. This didn’t look that fun, but thankfully I stumbled upon the Google Collections API. It includes a Map implementation for all combinations of key/value reference types. Better yet, it even works.  Here’s what one of the map declarations looks like:

    private static <K, V> Map<K, V> newReferenceMap()
    {
        return new ReferenceMap<K, V>(ReferenceType.STRONG, ReferenceType.WEAK);
    }

    private Map<String, StringSymbolImpl> symConstants = newReferenceMap();

I used a static helper method to make the instantiation a little cleaner since I had to do it once for each type of symbol.

I mentioned that it even works. Here’s my unit test that I used to convince myself:

    @Test
    public void testGarbageCollectedSymbolsAreRemovedFromCache()
    {
        for(int i = 0; i < 1000; ++i)
        {
            assertNotNull(syms.createInteger(i));
            assertNotNull(syms.createString(Integer.toString(i)));
        }
        // Why do I believe this test works? Because it fails if I remove the
        // call to the garbage collector here :)
        System.gc();
        for(int i = 0; i < 1000; ++i)
        {
            assertNull(syms.findInteger(i));
            assertNull(syms.findString(Integer.toString(i)));
        }
    }

Anyway, that was a bunch of time saved. As a bonus, Google Collections includes a number of other useful functions and classes. All of the stuff you wish was in Java’s Collections class, but isn’t. Especially handy was the composite iterator implementation. You give it a list of iterators and it returns an iterator that will iterate over each in turn. This was great for creating a natural interface for some of Soar’s weirder iterable data structures, like working memory.

Categories: java Tags:
  1. No comments yet.
  1. No trackbacks yet.