Tuesday, May 12, 2009

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!

4 comments:

  1. Very cool observation! I'm doing a quick Scala presentation to my team tomorrow and were looking for something like this...

    ReplyDelete
  2. Funnily enough, bitmap$0 is OK for 16 fields, after which is starts using a bitmap$1 for the next 16 fields. The reason as to why this may be, I'll leave for another time. (Should 've asked Mr. Odersky when he gave that talk in London, oh well.)
    Fun night using VIM macros and JAD :-P

    ReplyDelete
  3. 16?? Really? Heh. Probably they thought to spread the bits a bit, so they don't overdue with CASs a small piece of memory, but if they create bitmap$0, bitmap$1, etc, consecutively, these will probably end up in the same cache line anyway, so CASing them would be no different. But if you have *many* bits, then in the end, you will end up with cache lines for half the bits than you would normally have.

    Slightly arbitrary, but I see their (perhaps overdone) attempt at good citizenship.

    ReplyDelete
  4. So, basically, this means that accessing a lazy value for the first time is much slower than a direct value (an might even create deadlocks in weird cases), but the subsequent accesses are hardly slower than non-lazy values. It seems this is not to be taken lightly, only for really expensive initializations.

    ReplyDelete