Funny ConcurrentModificationException while playing with Google's Multimap

(Disclaimer: Google's Multimap surely work fine and as advertised - this post describes a potentially confusing code interaction which can result in unintuitive ConcurrentModificationExceptions)

First, lets create a multimap:

Multimap multimap = HashMultimap.create();

Put somehow some values to it:

putSomeValues(multimap);

Now lets iterate its key set, and potentially filter some elements of each key's collection:

for (Key key : multimap.keySet()) {
  Collection values = multimap.get(key);

  ...
  if (something) {
    Value someValue = ...;
    values.remove(someValue);
  }
}

(We could iterate its entries() as well, which is supposedly faster, but for now, I won't bother).

This seems safe. I iterate the keys, and don't perform any structural modification in the multimap, I might only make a collection inside it shorter.

Well, no. It can blow if "values" becomes empty, since then the multimap will remove the respective entry from the map (this is a very desirable behavior, to be sure), thus structurally modifying the map, thus ConcurrentModificationException when the iterator will try to fetch the next key.

This may be quite nasty if only rarely the "values" collection goes empty and triggers this behavior, so it's good to know.

My solution is this:

Iterator keyIterator = multimap.keySet().iterator();
while (keyIterator.hasNext()) {
Key key = keyIterator.next();
Collection values = multimap.get(key);

...
if (something) {
  Value someValue = ...;
  if (values.size() == 1 && values.contains(someValue)) {
    keyIterator.remove();
    continue; //this is not really needed
  }
  values.remove(someValue);
}
}

Quite simpler would be to simply change this:

for (Key key : multimap.keySet()) {

To this:

for (Key key : Lists.newArrayList(multimap.keySet())) {

If you don't mind creating a copy of the entire key set up-front.

Double-checked locking idiom, sweet in Scala!

In Java, this is what you have to write when you want a lazily, thread-safe constructed value, which isn't static (otherwise you would use Initialization On Demand Holder idiom).

private volatile Object field;

public Object get() {

  Object o = field;

  if (o == null) {

    synchronize(this) {

       o = field = create();

    }

  }

  return o;

}

private Object create() { ... }

Over, and over again, as many times as you need it. Or you could make a light abstraction over it, like this:

public class LazyHolder {

  private volatile T field;

  

  public T get() {

    T o = field;

    if (o == null) {

      synchronize(this) {

         o = field = create();

      }

    }

    return o;

  }

  protected abstract T create();

}

So the user would have to do this:

private final LazyHolder holder = new LazyHolder() {

  protected T create() { ... }

};

A very tiny caveat here (in both versions): if your computation happens to return null, the computation will be repeated the next time, since we used null as an indicator of missing initialization.

Enough about Java. How would you go about doing this in Scala?

Turns out, it is supported directly by the compiler, so you only have to write this:

lazy val myLazyField = create();

This is all it takes! It's thread-safe, it's computed only the first time if it's needed, and amazingly easy.

This is translated to a variant of the double-checked locking idiom. I decompiled a lazy val declaration and this is what I got:

   public volatile int bitmap$0;

   private Object myLazyField;

   public String myLazyField() {

        if((bitmap$0 & 1) == 0)

        {

            synchronized(this)

            {

                if((bitmap$0 & 1) == 0)

                {

                    myLazyField = ...

    bitmap$0 = bitmap$0 | 1;

                }

            }

        }

        return myLazyField;

    }

Note the bitmap field, which can support the lazy initialization of up to 32 fields (even if some are initialized merely to null).

Nice and easy!

A Wonderful Programming Exercise

Yesterday, while reading the famous and excellent Introduction to Algorithms ("CLRS") book, I bumped on a seemingly innocuous problem on Appendix B (page 1092). The problem statement reads:

Show that by removing a single edge, we can partition the vertices of any n-vertex

binary tree into two sets A and B such that |A| <= 3n/4 and |B| <= 3n/4.

My first reaction was, "wow". If you are like me, you tend to consider binary trees as something very, very basic. Something a computer-science student gets to learn and love by second semester, and then move on to more fancy and complex stuff. Yet, this is the first time I came across to this very peculiar property of binary trees (even in the form of an exercise), which states that "you can always split any binary tree by removing some edge and have both components less or equal to 3/4 of the initial size, and equivalently greater or equal to 1/2 of the initial size". Why nature specially picked 3/4 and 1/4? I don't know.  (You may google it, I did, and didn't find the answer/proof).

Here is a simple image of a binary tree, courtesy of Wikipedia: 

Anyway, on to the point. My problem was that I couldn't even find a binary tree which I could not cut more evenly than 3/4 and 1/4 (because, the exercise implies that there are some binary trees that you cannot reduce the greater split component any less than 3/4). So how am I supposed to build some basic intuition to be guided to a formal proof? I didn't fancy drawing and redrawing lots of trees, trying to find the "right" example. So, being a programmer, that's where I thought I could use some help from the computer in front of me: why not let the computer find the example and show it to me?

So this was my new problem statement: enumerate *all* binary trees of a given size N. How about trying this problem yourself and leaving a comment with your solution? (I would be quite interested in a nice solution in Scala by the way).

Assuming you now go to your favorite editor and see if you can hack this, let me describe here what happened on my side. My first attempt was ugly. Real ugly. I felt bad doing it, even bad about myself as a programmer. "A real programmer would be able to hack through it in few minutes". Well, mine was ugly, and I didn't even finish it, perhaps it couldn't work that way at all. For history, I tried building all trees in a top-down fashion (by the way, some months ago I was curious about "how many binary trees are there with a given size", and did that top-down approach to find out how many, but that was a simpler problem, and I ended up rediscovering the Catalan numbers).

I gave up, did not bother with it for another few hours, and then it hit me: why not build the trees bottom-up? In a dynamic programming fashion. Knowing all trees of size (N-1), one can pretty easily find the trees with size N. 

Enough description, lets have some code:

public class Main {
public static void main(String[] args) {
    int count = 0;

    for (Node tree : TreeEnumerator.findTrees(5)) {
        System.out.println(tree);
        count++;
    }
    System.out.println(count);
}
}

class TreeEnumerator {
public static Collection<Node> findTrees(int n) {
    List<Collection<Node>> knownTrees = new ArrayList<Collection<Node>>(n);
    knownTrees.add(Collections.<Node>singleton(Nil.instance));
    knownTrees.add(Collections.<Node>singleton(new InternalNode(Nil.instance, Nil.instance)));
    for (int i = 2; i <= n; i++) {
        final int kids = i - 1;
        Collection<Node> trees = new LinkedList<Node>();
        for (int leftKids = kids; leftKids >= 0; leftKids--) {
            int rightKids = kids - leftKids;
            Collection<Node> leftTrees = knownTrees.get(leftKids);
            Collection<Node> rightTrees = knownTrees.get(rightKids);
            for (Node left : leftTrees) {
                for (Node right : rightTrees) {
                    trees.add(new InternalNode(left, right));
                }
            }
        }
        knownTrees.add(trees);
    }
    return knownTrees.get(n);
}
}

interface Node {
}

class Nil implements Node {
static final Nil instance = new Nil();

private Nil() { }

@Override
public String toString() {
    return ".";
}
}

class InternalNode implements Node {
final Node left, right;

InternalNode(Node left, Node right) {
    this.left = left;
    this.right = right;
}

@Override
public String toString() {
    return "(" + left + right + ")";
}
}

I was very, very happy with the end result and the easiness that new trees are generated, always reusing some existing lower-rank tree. I suppose one might only appreciate this if he had already tried and realized how easily a "simple" problem, thought just a little bit wrongly, may end up in something so complicated and unmanageable - then one really appreciates simplicity! This algorithm is very efficient (probably optimal), and only creates as many nodes as trees (of size N or less), no more. Also noteworthy is that no tree copying takes place anywhere, only tree sharing. (This is facilitated by the fact that nodes do not ren eference their parents).

All this is nice, but this is not the complete solution. We still have to find which tree of those cannot be broken more evenly than 1/4 and 3/4. An obvious approach is to take every tree, and break it in every place possible, and keep the most even cut of those, and check whether it is 3/4. But then, how would one actually cut the trees? Nulling references in nodes? But that would destroy all other trees sharing those nodes! Node copying? It would seem that we should after all fall back to copying every tree, then try all breaks, so the original trees are kept intact.

Since this gets quite a big post, I'm not going to show the code of my solution, just sketch it. It is just a simple neat trick really. You don't have to actually break the tree! Just define a recursive "int count()" method on Node, and for every tree, do a couple of actions:

• Perform count() on the root, store it to "treeSize"
• Perform count() on every other node, store it to "subTreeSize"

Then you automatically have the sizes of the two components "assuming" they were actually disconnected (while they are not; they are still the same tree). "subTreeSize" is the size of the tree component below the point we would cut it. "treeSize - subTreeSize" is the size of everything else, i.e. the second component. Voila!

Hopefully you would find this interesting enough and tried it out before reading this. 

Cheers!

PS: This blog post is a kind offer from the CoCo coffee-bar (wifi-enabled), located on Cowley St., at the beautiful city of Oxford. 

PS2: SyntaxHighlighter just won't work for me. :-( Sorry. I am no CSS expert, and would need something pre-integrated in the blogging software.

Crazy Java Puzzler

Here is a puzzle for you. As the title promises, yes, it's quite crazy. It is assumed that you already are a die-hard Java programmer that knows the language better than the skin of his very palm. Ok, maybe not that much, but anyway.

As a little history, I had posted this on the Hellenic (i.e. Greek) Java User Group, which used to have an online forum, now defunct (too bad). So if you happen to be on those few who happened to see the solution there, just restrain yourself, I don't want any stinkin' spoilers!

Enough of intro. Here is the code:

interface id {
  <id> Void read(List<id> list);
  <id> Void read(List<id> list);
  <id> Void read(List<id>... list); //*
}

The puzzle: What is the shortest edit (measured in inserted/deleted characters) that makes this program compilable? (While keeping the read methods overloaded).

(We're not talking any kind of cheat like compiling with some arbitrary compiler, just the plain Java compiler. Oh, and commenting out lines of code is the wrong answer too).

The problem, obviously, is that the two methods produce a name clash.Well, it's all yours! Hit it hard! Can you nail it?

* [10-Mar-10] As Sureth below points, a solution would be appending "[]" to a list, a 2-character ending. Indeed. Sloppy of me. That basically ruins the fun, so I have to this third overloading to avoid [] and varargs solutions. Now (hopefully) only the intended solution is there, hopefully in not too artificial a puzzle. Oh, by the way, trying this problem is not a waste of time: it reveals a deeper knowledge about the java platform and gives a new (for those unaware of it) technique that can be used in API design. It's already the "magic sauce" of the nice API of a popular testing-related framework.

A DSL to output XML, in Java

Yesterday, I had to output some simple XML in Java. I couldn't find any decent way of doing this out there. Writing with SAX sucks, and DOM didn't look much better either. I just println'ed the thing out and went on my way.

Today I revisited the problem. I wanted to easily express the XML tree structure and evaluate it as something, a String for instance. I came up with a neat solution heavily based on generics.

Here is a usage example of it:

XmlBuilder xmlBuilder = new XmlBuilder();
String s = Xml.newDocument(new XmlBuilder())
.kid("start")
.kid("kid")
  .kid("subkid").attr("key", "value")
  .close()
.close()
.close();

System.out.println(s);

Note that calling close() sometimes returns a node (that can also close()), but the last time returns directly a String!

This is the output:

<?xml version="1.0"?>
<root>
<child>
  <sub_child key="value">
  </sub_child>
</child>
</root>

Here is the simplified crux of the idea:

public class Node<T> {
private final String name;
private final T returnValue;
private final XmlHandler handler;

Node(String name, T returnValue, XmlHandler handler) {
  this.name = name;
  this.returnValue = returnValue;
  this.handler = handler;
}
//...

Node<Node<T>> child(String label) {
  return new Node<Node<T>>(label, this, handler);
}

T close() {
  //...
  handler.endNode(name);
  return returnValue;
}
}

The magic part is methods child() and close(). Node<T> means "when close() is called, return T". Imagine we want to output an XML as a string. We want the root node to be of type Node<String>, so when that closes, we get a String back. Right. Now pay attention to method to the child() method. It returns a Node<Node<T>>, meaning "here is a node that when it closes, you return back to this node" (and we give "this" as a returnValue of the new node).

This means that the compiler can figure out the nesting level of each Node. The root Node is just Node<String>. All children of that are of type Node<Node<String>>. Children of those children are Node<Node<Node<String>>>, and so on. When a close() is invoked, a nesting goes away, like pealing an onion kind of way, till we get back to the result we want.

XmlBuilder is similar to ContentHandler, but simplified. Here it is:

public interface XmlHandler<T> {
void startNode(String name, Map attributes);
void endNode(String name);

T result();
}

The above library can be used with any implementation of XmlHandler - producing a String is only a viable use-case. One could easily create a DOM as well, simply by creating another XmlHandler implementation. XmlBuilder in the example above is XmlHandler, and this is why the root node is of type Node. We could implement an XmlHandler and get back the root node as Node.

To conclude, this is a nice DSL for expressing XML trees, combined with an abstract handler to process the tree. A point to highlight is that this modelling allows the compiler to know the nesting of each node, so it knows how many consequtive "close()" I can call for example. I must call the right amound of close() to get back to the result I want, or else a type error will occur.

Still, this kind of type-safety doesn't automatically translate to valid XML, because the user could store a node somewhere and close it twice - we would only find that at runtime.

All in all, that was a good exercise in Java generics. I would give the complete source if there was an easy way to attach it here, but I guess the margin is too narrow. :-)

The Subtleties of PhantomReference and finalization

A common misconception regarding PhantomReference is that it is designed to "fix" the dead object resurrection problem that finalizers have. For example, this old java.net blog says about phantom references:

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.

Well, yeah. Except for the fact that even PhantomReference can let their referred objects be resurrected. This is even how it can be done:

Reference ref = referenceQueue.remove();
//ref is our PhantomReference instance
Field f = Reference.class.getDeclaredField("referent");
f.setAccessible(true);
System.out.println("I see dead objects! --> " + f.get(ref));
//This is obviously a very bad practice

Yes, unreachable objects are really referenced from the Reference#referent field, seemingly strongly, but no, the garbage collector makes an exception for that particular field. This fact also contradicts what the previous blog declares:

PhantomReferences are enqueued only when the object is physically removed from memory.

Which is not true, as we just saw. Javadocs also say:

Phantom references are most often used for scheduling pre-mortem cleanup

So if PhantomReference was not meant to fix the resurrection problem (which indeed is serious, as pointedly proven by Lazarus, Jesus and many others), what is it useful for?

The main advantage of using a PhantomReference over finalize() is that finalize() is called by a garbage-collector thread, meaning it introduces concurrency even in a single-threaded program, with all the potential issues (like correctly synchronizing shared state). With a PhantomReference, you choose the thread that dequeues references from your queue (in a single-threaded program, that thread could periodically do this job).

What about using WeakReference? It seems to also fit the bill for pre-mortem clean-up. The difference lies in when exactly the reference is enqueued. A PhantomReference is enqueued after finalization of the object. A WeakReference is enqueued before. This doesn't matter for objects with no non-trivial finalize() method.

And how exactly are you supposed to clean-up a dead object you don't even know? (PhantomReference's get() method always returns null). Well, you should store as much state as needed to perform the clean-up. If cleaning up an object means nulling an element of a global array, then you have to keep track of the element index, for example. This can be easily done by extending the PhantomReference and adding the fields you want, and then create PhantomReference instances from that subclass.

Now lets talk about even darker corners than these.

Lets say that it is even darker relating finalization than this. If you are about to write a clean-up hook for an object (by finalize() or with a [Weak|Phantom]Reference), and you happen to call a method on it while there is it is strongly-referenced only from the thread stack (i.e. a local variable), and you happen to invoke a method to that object, bad things can happen.

This is very unfortunate. For performance reasons, the VM is permitted if it can to reuse the register that holds the object reference, thus making the object unreachable. So, during the method invocation on an object, finalization might be executed concurrently, leading to unpredictable results (finalize() could modify state that is needed by the other method execution). This should be extremely rare though. Currently, this can be fixed by:

Object method() {
 //do work here
 synchronized (this) { }
 return result;
}

public void finalize() {
synchronized (this) { }
//do work here
}

This will only affect you if you have an object referenced only from the thread stack and either one holds:

• it has a non-trivial finalize() method
• there is a [Weak|Soft|PhantomReference] to it, enlisted to a ReferenceQueue, and there is a different thread that dequeues references from ReferenceQueue

To conclude, the safest clean-up for objects is to have a ReferenceQueue and a PhantomReference, and you use the same thread that uses the object to do the clean-up. (If this the clean-up is performed from another thread, synchronization will probably be needed, and the above issue might be relevant).

You may check these JavaOne slides too.

Beware of hidden contention of Math.random()

Did you know that Math.random() uses a single java.util.Random instance, which itself is thread-safe*? What this means is that if you have a benchmark with multiple threads that are supposed to run in parallel, and all of them constantly generate random numbers through Math.random(), they will all compete for its lock and can deteriorate into running serially.

So, beware of this pitfall. It is preferrable to share instead a ThreadLocal, as for example in:

static final ThreadLocal localRandom = new ThreadLocal() {

    @Override protected Random initialValue() {

        return new Random();

    }

};

...

Random random = localRandom.get();

This is already quite a common practice when using SimpleDateFormat in web applications, where it is more efficient to have a separate instance per thread rather than have all threads contend for a single instance (which tends to be quite computationally intensive).

A better alternative is slated for inclusion in Java 7: ThreadLocalRandom. This is like a thread local Random, only it is not thread-safe, so some unnecessary overhead is avoided. There is a slight inconvenience that you can't control the initial seed - I could be wrong though (the javadoc says that setSeed throws UnsupportedOperationException, but the implementation seems to be that exactly one call of this method is allowed).

* Using volatile reads and compare-and-swaps, which makes it lock-free