HashMaps, Immutable, and Mutable Objects in Java

The immutable vs mutable debate has a lot of muscle behind it.  On the mutable side of the world, people argue performance.  If you modify your data structures in place, then you are going to have a faster program.   You don’t have to create a new object every time you replace a value.   On the immutable side of the world,  folks argue correctness.  If you have an object that doesn’t change, then you can guarantee that any reference to it will remain valid forever.  No worries about some other sneaky thread coming along and messing with your data (a nightmare bug scenario if I’ve ever heard of one).

Java is a language in which the standard object wrappers are immutable.  No changing the characters of that string, instead you have to create a new string.  To get around this problem, the Hadoop echo-system has introduced Writable objects, for example Text or LongWritable.  These are mutable object containers for primitive types.  Inside of a Mapper or Reducer, you can’t keep references to these objects and expect them to stay around between function calls, as the underlying data will change.

But what is the big deal?  Lets look at a toy problem to explore the performance differences in Java of using Mutable vs. Immutable objects.  In our toy problem:

  • We have a random sequence of numerical IDs.
  • Those IDs come from a small unknown set
  • But the range of ID values is large
  • We would like to count the number of occurrences of each ID
  • To do this we will use a [long -> long] map, where the key is the ID, and the value is the count

Our TestHarness class:

  • We are going to bake in the loop to force the Java runtime to compile the loop code into machine code.
  • We are going to then run a sequence of operations to update the counters.
  • We are going to finally clear the map and do this a number of times, to sample the runtime a few times.

import java.util.HashMap;
class TestPerformance
{
  static final int SAMPLES = 10;
  static final int ITERATIONS = 1000000;
  static final int NUMKEYS = 1000;
//
  static class MutableLong
  {
    public long val;
    public MutableLong(long val) { this.val = val; }
    public int hashCode() { return (int)this.val; }
    public boolean equals(Object other)
    {
      return other instanceof MutableLong ? this.val == ((MutableLong)other).val : false;
    }
  };
//
  // Uses the building java.lang.Long class
  static HashMap<Long,Long> dataMap = new HashMap<Long,Long>();
  static HashMap<Long, MutableLong> mixedDataMap = new HashMap<Long, MutableLong>();
  static HashMap<MutableLong, MutableLong> mutableDataMap = new HashMap<MutableLong, MutableLong>();
  static long[] sequence = new long[ITERATIONS];
//
  static void init()
  {
    long[] keys = new long[NUMKEYS];
    for (int i = 0; i < NUMKEYS; i++)
      keys&#91;i&#93; = (long)(Math.random() * Long.MAX_VALUE);

    for (int i = 0; i < ITERATIONS; i++)
      sequence&#91;i&#93; = keys&#91;(int)(Math.random() * NUMKEYS)&#93;;
  }
//  
  static void runLoop()
  {
    for ( int iteration = 0; iteration < ITERATIONS; iteration++)
    {
      //TODO: LOOP CODE GOES HERE!!!  
    }  
  }
//
  public static void main(String&#91;&#93; args)
  {
    init();
//
    // Allow the just in time compiler to kick in first
    runLoop();
//    
    for (int sample = 0; sample < SAMPLES; sample++)
    {

      long start = System.nanoTime();
      runLoop();
      long end = System.nanoTime();
      System.out.println(end - start);
    }
  }
}
&#91;/prettify&#93;

So lets think about the code to put in the hole above.  Here is <strong>Immutable Baseline</strong> code:
[prettify class="java"]
long nextKey = sequence[iteration];
if(dataMap.containsKey(nextKey))
{
  dataMap.put(nextKey, dataMap.get(nextKey) + 1);
}
else
{
  dataMap.put(nextKey, 1L);
}

This code uses the Immutable Long object (the Java compiler automatically boxes and unboxes the Long object around the Long constants in order to do this). However, it is really, really inefficient. It queries the hashmap for the object twice, when once would be sufficient.

We see a better version of this loop, still using the Immutable Object HashMap in the Immutable Optimized code:


long nextKey = sequence[iteration];
Long currentVal = dataMap.get(nextKey);
if(currentVal != null)
{
  dataMap.put(nextKey, currentVal + 1);
}
else
{
  dataMap.put(nextKey, 1L);
}

This code is much better because we only use one get and one put for each item in the sequence.

However, we can do even better with a mutable value for our counter: Mutable Counter code:


long nextKey = sequence[iteration];
MutableLong currentVal = mixedDataMap.get(nextKey);
if(currentVal != null)
{
  currentVal.val += 1;
}
else
{
  mixedDataMap.put(nextKey, new MutableLong(1));
}

Here we are only using a mutable object for the counter. This gives a huge boost, because now we only put an object in the map when we first see that key.

What if we use a mutable object for the key as well? This should hypothetically gain us time because we don’t have to allocate a key object for most items in the sequence: Then we have the Mutable Key code:


MutableLong mutableKey = new MutableLong(0);
for (int iteration = 0; iteration < ITERATIONS; iteration++) { long nextKey = sequence[iteration]; mutableKey.val = nextKey; MutableLong currentVal = mutableDataMap.get(mutableKey); if(currentVal != null) { currentVal.val += 1; } else { mutableDataMap.put(new MutableLong(nextKey), new MutableLong(1)); } } [/prettify] So how do these code snippets compare? Here are the timing results using Java 1.7.0_25 on a 64-bit Linux machine: [easychart title="Performance Results" type="vertbar" hidechartdata="false" groupnames="Immutable Baseline, Immutable Optimized, Mutable Count, Mutable Key" groupcolors="FFAC33,A66910,337DC5,114980" valuenames="Run 1,Run 2,Run 3,Run 4,Run 5,Run 6,Run 7,Run 8,Run 9,Run 10" group1values="506031594,436691479,420306159,467199091,438349669,453756721,424360485,421675078,429053958,423774564" group2values="407915419,340436813,335873554,342810446,349873204,330582166,336349432,342039560,335636152,343609158" group3values="134051463,137137727,135402168,136319060,139233354,134855137,133633784,147397971,133631057,133470026" group4values="129802277,127841920,124263920,124169285,123770994,125532172,123137606,126542914,124350646,123146428" minaxis=0]

Cocos2d-x a great framework…but idiomatic C++ it is not.

I am not a C++ expert.  But I do know the language reasonably well.  I have some experience with it.  I once upon a time as a young yeoman programmer wrote a scan line rendering system in C++.  I wrote some windows C++ code (MFC yeah!) during an internship at Intel that focused on image processing and sported a pretty nifty UI.  For my Ph.D., I wrote a templated custom MapReduce inspired framework for managing parallel software development on an IBM Blue Gene.  I’ve Valgrinded (or is that Valground?).  That is a reasonable amount of experience, but it is not years of recent professional experience, which I think is needed to consider yourself a C++ expert.

Recently (four months ago) I came back to the C++ world after many years of mostly Java, and was surprised to discover a brand new world called C++11.  This was a world of auto, comprehensionsvariadic templates, and lambda functions the C++ way.  Most importantly, we suddenly have move semantics, which, in addition to giving you a real way to implement a unique_ptr, allow you to finally implement a natural functional model where your functions actually return things rather than modify the pointers to the “output parameters.”

Add to this the flexibility of the C++ template*, and I’m suddenly an excited C++ programmer again.

I brought this new excitement for C++ to a new project I’ve been thinking of embarking on, which is to explore the world of game development frameworks, to the game framework Cocos2d-x. So I’m looking at the Cocos2d code-base, and the first thing I see is the following code:


CCScene* HelloWorld::scene()
{
  CCScene * scene = NULL;
  do
  {
    // scene is an autorelease object
    scene = CCScene::create();
    CC_BREAK_IF(! scene);
    // layer is an autorelease object
    HelloWorld *layer = HelloWorld::create();
    CC_BREAK_IF(! layer);
    // add layer as a child to scene
    scene->addChild(layer);
  } while (0);
  // return the scene
  return scene;
}

And I’m thinking… “An autorelease object, what the hell is that?” Oh the joys of do it yourself memory management. Part of the excitement of coming back to C++ was the standardization of memory management to smart pointers like shared_ptr, weak_ptr, and unique_ptr. It turns out that an autorelease object within the context of Cosos2d-x comes from its history as an Objective-C library, and if I knew the Objective-C memory management model, I might have had a better clue. After a little research, an autorelease object is just an object that gets added to a pool of things that will be released on the framework’s time. The memory management system in the framework has three concepts:

  • create – Create an object
  • release – Release an object
  • autorelease – Don’t free the object now, but put it in the list of things that will be freed when it is safe.

Now, I was immediately disappointed by this development and yet another custom memory model to learn… and one that is not exception and thread safe at that. So I immediately did two things. First, I went out on the internet to see if anyone else complained about this issue (yes, it turns out). In fact, someone had created an extension to the Cocos2d system to make it behave in a smart pointer like way. Another person had created some C++11 syntactic sugar using variadic templates to make Cocos2D object references look and behave like smart pointers. That code is some great stuff to grok.

And the Cocos2D team themselves have recognized the issue and there is a 7 page thread devoted to the topic of whether to port the whole memory system to the C++ standard for the next major (v3) release of cocos2d-x. This thread is an interesting read in an of itself, as it goes over the pitfalls of performance testing and comparing these two fundamentally different methods.

If we look at the preceding code, we also see a second strangeness. What is this?


CC_BREAK_IF(! scene);

It sure looks like something fancy is going on here, doesn’t it. What is this craziness of putting your code inside of a fake loop…do…while(0) and calling this fancy CC_BREAK_IF() macro? Finding the declaration in platform/CCPlatformMacros.h, we see the definition:


#define CC_BREAK_IF(cond)            if(cond) break

Is that really all it is? An if(cond) break? Then why have a macro at all?…it seems to be obfuscating the code for no benefit and providing a barrier to learning. A quick google search indicates a stack overflow question on the same. It sure seems like back programming practice to me.

These things set me off a bit, so I do a quick search for that other great 2d-game framework I will flock to instead…and it turns out that it probably doesn’t exist. Cocos2d-x allows you to write a game once, and then run it across many platforms, all in a fancy open-source package. And its actual feature set is quite rich, including particle systems, easy parallax effects, splines, easing, and 2-D skeletal animation.

The cocos2d-x team is working on version 3 with a more C++ flavor. This presents a choice…do I try for the bleeding edge, and help them test as they go, or do I learn off of the tried and true 2.x? I’ll probable check out the dev branch and see how stable it seems and decide from there.

In the meantime, imagine the previous example as:


std::shared_ptr<Scene> HelloWorld::scene()
{
  auto scene = Scene::create();
  if (scene == nullptr) return nullptr;
  auto layer = HelloWorld::create();
  if (layer == nullptr) return nullptr;
  // add layer as a child to scene
  scene->addChild(layer);
  return scene;
}

Or maybe:


std::shared_ptr<Scene> HelloWorld::scene()
{
  auto scene = Scene::create();
  if (scene == nullptr) throw . . .;
  auto layer = HelloWorld::create();
  if (layer == nullptr) throw . . .;
  // add layer as a child to scene
  scene->addChild(layer);
  return scene;
}

*And reintroduced to the joys of the GNU C++ compiler’s ridiculously cryptic template compilation errors, but that is a topic for another day.

Hello, World.

Hi, this blog is about coding.  It is about algorithms.  It is about exploration.  I like to do it, and I thought I’d start sharing what I find.  Maybe I will occasionally post something useful to someone in the process.  Who am I?  I have a Ph.D. I am professional Engineer and Architect.  I live in San Francisco, CA.

Linked in Profile