When accessing elements from sets of data, it is often the case that some elements are accessed much more frequently than others. In these cases, it is possible to apply caching techniques to speed up access to these frequently accessed elements. This is best demonstrated with the following example.

Consider a CacheTest class that consists mainly of a Map populated with Integer objects. I use Integer objects for convenience to populate the Map with many elements, but the actual object type is of no significance since you use only the hashCode( ) and equals( ) methods, just as the Map does.

Basically, you provide two ways to access the elements of the Map. The first, plain_access(), just calls the Map.get( ) method as normal. The second method, cached_access( ), uses the lower bits of the hash code of the object to obtain an index value into an array. This index is then checked to see whether the object is there. If it is, the corresponding value in a parallel value array is returned. If it’s not, the object is placed there with the value in the corresponding value array.

This is about the simplest example of general cached access. It demonstrates the advantages and pitfalls of cached access. I have selected 10 integers that do not map to the same indexes for the example. Running the class gives a straightforward comparison between the two access methods, and I get the result that the cached access varies significantly depending on the VM used. The access speedups are illustrated in the following table of measurements. Times have been normalized to the JDK 1.2 case for using a HashMap. The first time of each entry is the measurement using a HashMap (not available in JDK 1.1.6), and the second is the measurement using a Hashtable. For any one VM, the cached access is significantly faster.

This test is artificial in that I chose integers where no two map to the same index. If there is more than one integer that maps to the same cache array index, this is called a collision. Clearly, with collisions, performance is not as good because you are constantly entering the code that puts the objects into the cache. Collisions are a general problem with cached data, and you need to minimize them for optimal performance. This can be done by choosing an appropriate mapping function to generate indexes that minimize your collisions:

package tuning.cache;

import java.util.HashMap;
import java.util.Hashtable;
import java.lang.Math;

public class CacheTest
{
  //The cache array for the keys
  static Object[] cache_keys = new Object[128];
  //The array for the values corresponding to cached keys
  static Object[] cache_values = new Object[128];
  //static Hashtable hash = new Hashtable( );
  static HashMap hash = new HashMap( );

  public static void main(String[] args)
  {
    try
    {
      System.out.println("started populating");
      populate( );
      System.out.println("started accessing");
      access_test( );
    }
    catch(Exception e){e.printStackTrace( );}
  }

  public static void populate( )
  {
    for (int i = 0; i < 100000; i++)
      hash.put(new Integer(i), new Integer(i+5));
  }

  public static Object plain_access(Integer i)
  {
    //simple get( ) call to the hash table
    return hash.get(i);
  }

  public static Object cached_access(Integer i)
  {
    //First get access index
    int access = Math.abs(i.hashCode( )) & 127;
    Object o;
    //if the access index has an object, and that object is equal to key
    //then return the corresponding value in the parallel values array.
    if ( (o = cache_keys[access]) == null || !o.equals(i))
    {
      //otherwise, we got a collision. We need to replace the
      //object at that access index with the new one that we
      //get from the hashtable using normal Hashtable.get( ),
      //and then return the value retrieved this way
      if (o != null)
        System.out.println("Collsion between " + o + " and " + i);
      o = hash.get(i);
      cache_keys[access] = i;
      cache_values[access] = o;
      return o;
    }
    else
    {
      return cache_values[access];
    }
  }

  public static void access_test( )
  {
    //Ten integers that do not collide under the mapping scheme
    //This gives best performance behavior for illustration purposes
    Integer a0 = new Integer(6767676);
    Integer a1 = new Integer(33);
    Integer a2 = new Integer(998);
    Integer a3 = new Integer(3333);
    Integer a4 = new Integer(12348765);
    Integer a5 = new Integer(9999);
    Integer a6 = new Integer(66665);
    Integer a7 = new Integer(1234);
    Integer a8 = new Integer(987654);
    Integer a9 = new Integer(3121219);
    Object o1,o2,o3,o4,o5,o6,o7,o8,o9,o0;
    long time = System.currentTimeMillis( );
    for (int i = 0; i < 1000000; i++)
    {
       o1 = plain_access(a0);
       o2 = plain_access(a1);
       o3 = plain_access(a2);
       o4 = plain_access(a3);
       o5 = plain_access(a4);
       o6 = plain_access(a5);
       o7 = plain_access(a6);
       o8 = plain_access(a7);
       o9 = plain_access(a8);
       o0 = plain_access(a9);
    }
    System.out.println("plain access took " +
        (System.currentTimeMillis( )-time));

    time = System.currentTimeMillis( );
    for (int i = 0; i < 1000000; i++)
    {
       o1 = cached_access(a0);
       o2 = cached_access(a1);
       o3 = cached_access(a2);
       o4 = cached_access(a3);
       o5 = cached_access(a4);
       o6 = cached_access(a5);
       o7 = cached_access(a6);
       o8 = cached_access(a7);
       o9 = cached_access(a8);
       o0 = cached_access(a9);
    }
    System.out.println("cached access took " +
        (System.currentTimeMillis( )-time));

  }
}