{ tinou bao }

Scala's Dirty Little Scalability Secret

The other week, while shooting the shit about programming languages, a colleague mentioned the Twitter Ruby v. Scala debate, how Twitter had switched to Scala to meet their scaling needs. I wasn't following the ruckus that closely (no dog in the fight), but that sounded really odd, to say that one language is more scalable than the another.

For one, different people give different meanings to scalability so any discussion on scalability is bound to be problematic unless the participants all agree on a single definition. I personally like to use Amazon CTO Werner Vogel's description.  Haven't given much more thought to the debate since then; until yesterday, when an article on Twitter's evolving architecture appeared on InfoQ.   Most of the commotion stems from Twitters messaging queue problem:

The first implementation of the MQ was using Starling, written in Ruby, and did not scale well especially because Ruby’s GC which is not generational. That lead to MQ crashes because at some point the entire queue processing stopped for the GC to finish its job. A decision was made to port the MQ to Scala which is using the more mature JVM GC. The current MQ is only 1,200 lines and it runs on 3 servers.

Now I see the problem. We're muddling the language with the platform.  The sentence "a decision was made to port the MQ to Scala which is using the more mature JVM GC" should have read "a decision was made to move to the more mature JVM GC and Scala was chosen as the language".  The move to Scala was dictated by the performance and reliability of the Java VM and its garbage collector, not Scala the programming language.  Twitter is giving Scala the programming language too much credit.  I don't think they are doing this intentionally and they do always note the JVM aspect, but with slides like this

 

and focusing more on Scala the programming language than the VM platform it's not entirely surprising that some folks took issue and were confused by Scala's magical scaling abilities.  And the bit about only 1,200 lines of code omits their dependency on Apache Mina (plain old Java).  In essence Twitter moved to Java and the Java platform--it just so happens that Scala is a cool language that can co-exist on the platform.

And that's Scala's dirty little secret. Scala is only scalable in the sense that it runs on the reliable, high-performing JVM platform. This is why people say that Java the programming language is dead, but long live the virtual machine. Rich Hickey has a good, succinct take on languages and platforms in his rationale for Clojure.  In this sense Ruby is doing it the "old way" whereas languages like Clojure and Scala are doing it the "new way" by leveraging the platform.  If Scala only ran on the 1.4 JVM no one probably would even be talking about Scala, because while some of the language constructs are neat, lets face it, they are not revolutionary or entirely novel.  What's the saying, everything interesting in computer science was between 1950-1980. 

So, in addition to

• languages don't scale, architecture scale
• frameworks don't scale, solutions scale

I will add the following

• languages don't scale, platforms scale  

Incidentally, it should be noted that the creator of Scala refers to Scala's scalability not with respect to the platform but because Scala can be applied to a "wide range of programming tasks, from writing small scripts to building large systems." But since scalability means different things to different people we're bound for disconnect.

Lock Coarsening, Biased Locking, Escape Analysis for Dummies

The other day I saw that Sun released JDK 1.6 Update 14 that includes version 14 of their HotSpot Virtual Machine.  I think for the first time they included in the release notes a section mentioning the VM now accepts a DoEscapeAnalysis flag.  Escape analysis has been a much talked about optimization technique, but while it's been around for a while this was the first time I've seen Sun officially document it. 

My coworker then pointed me to an article that questioned whether escape analysis actually did anything (bing "did escape analysis escape Java").  The article is quite informative, but I was skeptical of the benchmark test and its conclusions.  I mean, there are really smart people at Sun (not just guys like me with a blog who tries to sound smart) and I found it hard to believe that -XX:+DoEscapeAnalysis did nothing.  In fairness, there's a second part to the blog, also quite informative, that digs a little deeper into benchmarks and clarifies some things.

Uneducated Guesses

Playing around a bit (with Java scientific benchmark) I think -XX:+DoEscapeAnalysis does offer a performance gain, but it's not as much as some of us had hoped (some of us are always hoping the next "breakthrough" will solve all our problems).  Also, it seems that escape analysis is not as predictable as the other concurrency optimization techniques.  One runs saw little gains, the next saw more substantial gains;  whereas biased locking and lock coarsening predictably, consistently saw big performance improvements.  Escape analysis doesn't seem to kick it sometimes.  This is all guessing on my part.  I have no idea on a low level how these techniques are implemented. 

At this point some might be asking, what is escape analysis, biased locking and lock coarsening, anyway?  I wrote a little bit about biased locking here last year.  But now that I have OmniGraffle Pro I'll explain things better with diagrams.

Lock Coarsening

Let's start with lock coarsening.  You enable lock coarsening with -XX:+EliminateLocks.  This does not mean locks are completely removed/eliminated.  Rather, instead of a thread repeatedly acquiring and releasing the same lock the VM will combine these calls.

  In figure 1 you can see two critical sections guarded by the same lock.  Lock coarsening will merge the two critical sections, along with the non-critical section, into a larger synchronized block.  Instead of two acquire/release calls there's only one.  Moreover, with a larger block of code to work with other optimizations can be better applied.  While this reduces the locking overhead it should be noted larger critical sections may cause the application to be less responsive.  Some may notice the irony that we often try to break up large synchronized blocks. 

Biased Locking

Up next is biased locking.  Biased locking stems from real world observations that most locks are uncontended and at most one thread tries to acquire the lock.  Here's how two threads locking two different objects work without biased locking.

As each thread enters the critical section it tries to acquire the (different, uncontended) lock.  This involves expensive operations: operating system mutexes, conditional variables, compare and swaps, etc.  Given real word observations we can optimize by biasing objects to threads base on some heuristics (e.g., which thread created the object).  The threads can then lock/unlock without expensive operations.

  The downside is if there's another thread that comes along and attempts to acquire the same lock  the lock bias has to be revoked then.  If I remember correctly the VM does some sort of bulk rebiasing to amortize the overhead.

Escape Analysis

Finally, escape analysis.  First, the virtual machine analyzes execution to see which objects escapes into the unknown and which are confined to the thread/stack frame.  Objects that are confined can be optimized.  The VM does two kinds of optimization on these confined objects.  First, since the objects are confined to the thread it is safe to remove locking (no other thread can possibly come along and use the the confined objects).  The fancy term is lock elision.  The most basic example is with a local StringBuffer, but there are actually some really interesting examples that aren't so obvious, i.e., examples that can't be optimized statically at compile time. 

The second optimization that can be done after escape analysis is allocation optimization.  In Java when you do a new FooBar() the object is allocated on the heap.  Heap allocation is actually really faster, contrary to what many might say, but then you have to deal with garbage collection (the de-allocation part).  There's also an interesting issue with latency from cache misses due to the fact that memory is hierarchical. (google Brian Goetz, he explains it better). 

However, since the VM knows that these objects won't escape it can allocate them on the stack or put them in the registers, known as stack allocation and scalar replacement, respectively.  For example, if FooBar was a simple class that contained just a single int it could avoid allocation and the int field could be place in the register.  This avoids allocation, garbage collection and cache misses.

Just as with lock coarsening, escape analysis leads to further optimization opportunities.

But as I've said before, my dream is to one day never have to deal with locks.  I'm still waiting transactional memory, which might be coming soon hardware transactional memory.

Java Class and Object Size

A couple of months ago I was curious how much memory a new class I wrote would take.  I lost my notes with the specifics but here's a high level overview of estimating class memory size.

First, a brief word of the Java Virtual Machine, in particular the Sun HotSpot VM.  The HotSpot VM has three heap spaces for the three generations it manages: the young, old (tenured) and permanent.  Yes, the permanent generation is part of the total heap the virtual machine manages.  Many tools refer to the perm gen as non-heap, and while the -Xmx and -Xms don't affect the perm gen heap, it's nevertheless part of the total heap the virtual machine manages.  You can control the permanent generation's heap size with the -XX:MaxPermSize option.  Running the jmap utility lets you see the various heaps the virtual machine is managing.

So how does a class use up the heap spaces in the VM?  When the virtual machine loads a class it create a klass (or is it klazz?) to define the class.   This class definition eats into the permanent generation.  A class with constants and lots of methods (more bytecode) will require more memory in the perm gen.  The good news is there's only a single copy of the class definition.  For the most part, unless you're generating classes at runtime and doing other advance things, you can largely ignore your class' s impact on the perm gen until you see those PermGen out of memory exceptions. But it's still important to understand how a class affects the perm gen.  Incidentally, I think there's some work about an "invoke dynamic" instruction that'll allow you to execute arbitrary code without the need to define a class and use up the perm gen.

Most developers are more interested in how their classes affect the young and old generations.  Here, we're really talking about objects and not classes.  And here, application behavior is really important, because application behavior will largely dictate how much memory your objects take up.

Each object eats up a minimal amount of memory (overhead).  Beyond this, instance member variables increase an object's size.  For example,

SmallClass {
   private String s1;
   private void doNothing() {
       // no-op
   }
}
BigClass {
  private String s1;
  private String s2;

  private void doSomething() {
     // a bunch of bytecode that eats up the perm gen heap
     int i = 10;
     for (int j =0 ; j < i; j++) {
          // a bunch of code
     }
  }
}

BigClass requires 4 more bytes than SmallClass befcause of the s2 String.  A reference is 4 bytes on my Linux 32-bit box running Java 5.  If you run a "size of" on SmallClass and BigClass you might see that they are the same size, but that's because the VM has 8 byte alignment.  Add another reference to BigClass (String s3, for example) and you'll see the size jump 8 bytes. 

So far we've discussed the the "static" aspects of class and object memory sizes.  Presumably, your strings will not be null and hold some value.  Your object size will then depend on how big your strings are, i.e., how big the char arrays are (ignore string interning for the moment).  Likewise, a reference to a HashMap is 4 bytes, but if the HashMap contains a million entries...This "deep" size obviously depends on the behavior of your application. 

In Summary, the following is how a class eats up memory

• class definition ---> perm gen heap space
• object overhead + references ---> young/old gen heap space, multiply by how many objects
• object "deep size" ---> memory required by object beyond just the references (how long are the strings, how many entries in the map, how big are the arrays, etc.)

Performance Optimization in ConcurrentHashMap

The other day I asked an interviewee to implement a standard hash table. Pretty basic question, but you'd be surprised how many software engineers get stuck. I'm of the belief that if you're going to be using the HashMap class you should be somewhat familiar with its implementation. Wanting to not just "talk the talk" but "walk the walk" I figured I better look at how ConcurrentHashMap is implemented.

ConcurrentHashMap in Java 5 is your run of the mill hash table "supporting full concurrency of retrievals and adjustable expected concurrency for updates." Throughput scales well as the number of threads increase, much better than synchronized HashMap and Hashtable. Three things in ConcurrentHashMap caught my attention.

Lock Striping

Instead of using a single lock for the shared data, the shared data is partitioned with each partition having its own lock. Uncontended lock acquisition is very cheap; it's the contented locks that cause scalability issues. By Little's Law, the two factors influencing lock contention are: (1) how often the lock is requested; and (2) how long the lock is held.

With a different lock for each partition, ConcurrentHashMap effectively reduces how often a lock is requested by the number of partitions. You can think of ConcurrentHashMap has made up of n separate hash tables.  The obvious challenge is that for some operations you now have to deal with n separate locks.

Use of Volatile Instead of Locks

Read operations in ConcurrentHashMap do not require lock acquisition (for the most part). With the improved Java Memory Model, ConcurrentHashMap makes use of volatile instead of synchronization and locking to ensure that the hash table is always in a consistent state. If you recall, a write to a volatile happens-before every subsequent read of that volatile (see Java Memory Model in 500 Words). Moreover, the visibility of other variables can piggyback on the volatile variable.

So if you look at the ConcurrentHashMap source you will see many comments on reading a volatile, because that volatile read allows the hash table to always be in a consistent state without the use of locks and synchronization.

V get(Object key, int hash) {
  if (count != 0) { // read-volatile
    HashEntry
 e = getFirst(hash);
    while (e != null) {
      if (e.hash == hash && key.equals(e.key)) {
        V v = e.value;
        if (v != null)
          return v;
        return readValueUnderLock(e); // recheck
      }
      e = e.next;
    }
  }
  return null;
}

Power-of-Two Hash Table Size

Any data structures 101 book will say choose a prime for the number of buckets, so that the bucket's index can easily be computed by h(k) = k mod m, where k is the key value and m is the bucket size. While this approach is straight-forward, there are a number of issues with it, including slow modulo performance. ConcurrentHashMap instead uses a power-of-two rule for the number of buckets. This allows the use of bit masking to quickly determine the bucket.

final Segment
 segmentFor(int hash) {
  return segments[(hash >>> segmentShift) & segmentMask];
}

Power-of-two sizing is not exclusive to ConcurrentHashMap and has been in place since Java 1.4. Incidentally, before the the bit masking is applied to the hash, an additional hash is applied to guard against bad hash functions.

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions. This is critical
 * because ConcurrentHashMap uses power-of-two length hash tables,
 * that otherwise encounter collisions for hashCodes that do not
 * differ in lower or upper bits.
 */
private static int hash(int h) {
  // Spread bits to regularize both segment and index locations,
  // using variant of single-word Wang/Jenkins hash.
  h += (h << 15) ^ 0xffffcd7d;
  h ^= (h >>> 10);
  h += (h <<  3);
  h ^= (h >>> 6);
  h += (h <<  2) + (h << 14);
  return h ^ (h >>> 16);
}   

Dependency Injection is Broken

Beside adding support for closures to Java 7, I propose adding support for runtime interface and abstract class reification.  Well, I propose that someone who actually knows what they're talking about propose such a mechanism. 

Background: Earlier today I was reading a blog about the worthlessness of constructors.  Frankly, I didn't really get the point of the post, but the title was catchy.  Jeremy mentioned something about dependency injection (DI), one of my favorite topics, having written at length about how crappy Spring is (it's really not, and I hope the Spring guys didn't take offense to it--like Jeremy, I tend to be hyperbolic in my praise and criticism).

The problem I've always had with DI frameworks, be it Spring or Guice, is they create this nasty dependency tree.  If you don't want to use GlobalApplicationContext.getBean() or Injector.getInstance() then you'll need to inject all your dependencies at the root.  It annoys the crap out of me, but I suppose there's just no way around it...

Except if the language had a mechanism to realize interfaces and abstract classes at runtime, either built-in or through some extension. 

I want to be able to do something like this

interface MovieFinder {...}

...
MovieFinder mf = realize MovieFinder();
List<Movie> movies = mf.findAll("Scarlet Johansson");
...

and have the language realize the MovieFinder interface for me (at runtime).  It could be a DBMovieFinder, or maybe a MockMovieFinder for testing purposes.  "realize" is just like "new" except we let the runtime figure out what concrete implementation(s) reifies the interface or abstract class.  The fundamental problem with all dependency injection tools is they are trying to do what  language should be doing (instantiating objects that implement some interface).

As I mentioned earlier, I don't think the Java language should have this built-in, because it is a rather specific use case; but Java might have some sort of extension mechanism so that it appears built-in to the average programmer. 

I'm sure there are many issues with such a mechanism, but I don't think I'm too off base.   Gilad Bracha writes,

The root of the problem DIFs address is that mainstream languages provide inadequate mechanisms to abstract over classes.

And apparently the creator of Guice agrees,

Ideally, the language itself would provide most of the same features, but until such a language comes along, we have Guice.

It's 2008, we've landed a man on the moon, and I'm still clunking around with DI tools!

Java Control Abstractions

If you were puzzled by my last post, it was a poor attempt at humour.  Apparently, there is some politics around adding closures to Java.  Two current Google and former Sun heavyweights have competing proposals for adding closures to Java 7, so Google issued a statement of neutrality. 

Closures allow us to write succinct, clean code like this (taken from Ruby)

def highPaid(emps)
 threshold = 150
 return emps.select {|e| e.salary > threshold}
end

in which the free variable threshold is bound in its lexical context. 

The first of the competing closure proposal, what I call "closure light", is admittedly syntax sugar for anonymous inner classes.  For example, you could sort a list of Strings with

List<String> ls = ... ;
Collections.sort(ls,
 Comparator<String>(String s1, String s2){ return s1.length() - s2.length(); });

instead of the current

List ls = ... ;
Collections.sort(ls, new Comparator() {
 public int compare(String s1, String s2) {
  return s1.length() - s2.length(); 
 }
});

The goal is not to revamp the language to support closure but just to make things more concise.   Proponents argue that it does much of what is desired via anonymous inner classes (limited closures) but without the complexity of "full blown" closure.

So what does full blown closure buy us that makes me want it?  Two words: control abstraction.  In the following

List<Double> deposits = ... ;
synchronized (myMonitor) {
 for (Double d : deposits) {
  // update checking account
 }
}

synchronized is a control abstraction, as is the for-each loop.  They are both built-in control abstractions.  Full blown closure would allow us to implement our own control abstractions.  With full blown closure, synchronized  and for-each could have been implemented as a library API.  In fact, in Smalltalk, if statements, while loops, for loops, etc. are all implemented as regular methods in the language using block closures.   If you have been working in Java your entire career like I have, re-read these last two sentences and tell me it doesn't make you pause for a second.

With full blown closure you replace

FileReader fileReader = ... ;
try {
 // read file using fileReader
} finally {
 fileReader.close();   
}

long start = System.nanoTime();
try  {
 // do some stuff
} finally {
 log("stuff", System.nanoTime() - start );
}

with

FileReader fileReader = ...;
withReader (fileReader) {
 // read file using fileReader
}

recordTime ("stuff") {
 // do stuff 
}

The key thing to note is that within the block closure every statement and expression has the same semantics as it does in its enclosing scope.  Not only are free variables bound in its lexical context, so is "this" and "return," "continue," and "break".  You wouldn't be able to write

List<Double> deposits = ... ;
synchronized (myMonitor) {
 for (Double d : deposits) {
  this.deposit(d);
 System.out.println("deposited " + d + " in instance " + this.hashCode());
 }
}

if the semantics changed inside the synchronized block.

Obviously full blown closure is much more powerful than closure light, but at the expensive of adding complexity to the Java language.  For example, what happens with returns when the closure is executed in a different thread? And therein lies the debate, whether the added complexity is worth it. 

I've never really bought into the complexity argument.  When was the last time the UI guy at work complained JavaScript is too complex because of closure.  Generics and anonymous inner classes added complexity to the language, but if you and I (the average programmer) don't use them, they don't really get in our way.  And I imagine that's how closure will be.  Mainstream programmers will casually use closures where needed, but leave the finer points to library developers.

In fairness, closure light does have an additional proposal to add resource management to Java, which would alleviate the need for some of the control abstractions.  It then gets philosophical, whether you want to strategically change the Java language to do X and Y; or give the language the facilities so that anyone can implement X and Y (and Z).

Maybe I will get my employer, Rearden Commerce, to issue a statement on adding closures to Java before Google acquires us and we are force to remain neutral.  For now, at least you know my position.

References:

1. Neal Gafter's blog

2. javac.info (BGGA)

3. Smalltalk versus Java

4. Crazy Bob: The Java Closure Spectrum

The Java Memory Model in 500 Words

What is the Java Memory Model?  The JMM explains why the original double-checked locking optimization is broken and how it can be fixed.

It answers the seemingly simple question, when does a read of myVariable see 3 after the assignment

public int myVariable = 3;

The JMM defines a partial-ordering called happens-before on all actions in a program.  For example, in the figure below,

Figure by Brian Goetz

All the actions prior to the unlock M in Thread A happens-before the lock M in Thread B.  This guarantees that j = y = 1.  Without the JMM  j = y = 1 could not be guaranteed because of the various "quirks" in the hardware and compiler layer (processor cache coherence, compiler reordering, etc.).

Actions include

• reads and writes to variables
• locks and unlocks of monitors
• starting and joining with threads

The rules for happens-before are

• Program order rule.  Within a thread actions happen in program order.
• Monitor lock rule.  Unlock on monitor happens-before every subsequent lock on the same monitor.
• Volatile variable rule.  A write to a volatile happens-before every subsequent read of that volatile.
• Thread start rule.  Thread.start happens-before actions in the Thread
• Thread termination rule.  Actions in a thread happens-before other threads detect the thread's termination.
• Interruption rule.  A thread calling interrupt on another thread happens before the interrupted thread detects the interrupt.
• Finalizer rule.  End of object construction happens-before start of object finalization.
• Transitivity.  If A happens-before B, and B happens-before C, then A happens-before C.

There you have it, the Java Memory Model in 500 words.  This summary has been taken from Brian Goetz's Java Concurrency in Practice, which I can't recommend enough.

Biased Locking

Here's the dilemma: with multiprocessor machines the norm these days we need to write concurrent applications to take advantage of multiprocessing; but atomic operations that are the building blocks of concurrency controls needed in these applications are significantly more expensive on multiprocessor computers.  To address this issue the folks at Sun have implemented a runtime optimization called Biased Locking in Java 6.  In their own words,

Biased Locking is a class of optimizations that improves uncontended synchronization performance by eliminating atomic operations associated with the Java language’s synchronization primitives. These optimizations rely on the property that not only are most monitors uncontended, they are locked by at most one thread during their lifetime.

For the gritty details you can read "Eliminating Synchronization-Related Atomic Operations with Biased Locking and Bulk Rebiasing". 

The first level of optimization involves so-called lightweight locking, which avoids heavier operating system mutexes and conditional variables.  Lightweight locking instead uses atomic operations where possible, before resorting to the aforementioned heavyweight operations.  This works well because most lock acquisitions in real world applications are uncontended and atomic operations suffice.

The second level of optimization, Biased Locking, involves avoiding atomic operations where possible.  In many real world applications locks are acquired repeatedly by the same thread.  This makes it possible to bias the lock toward a thread, allowing that thread to acquire the lock without atomic operations.  The HotSpot JVM implements Store-Free Biased Locking, which I understand as not storing anything to the object header when a lock is biased to the current thread.

Biased Locking performs well until bias revocation is required (when another thread attempts to acquire the lock).  Even if there is no contention the bias must be revoked, an expensive operation.  This occurs, for example, in the common producer-consumer pattern.  Biased locking in producer-consumer queues would be disadvantageous because of all the revocations that would take place as the two threads work off the queue.

To deal with such scenarios the Sun JVM performs bulk rebiasing and bulk revocation, followed finally by disabling SFBL.  The rebiasing and revocation are done in bulk on all instances of the data type.  This amortizes the cost of the rebiasing and revocation.  Performing the bulk operations on the data type has been shown to be reasonable.  This intuitively makes sense, since each class will probably be used in the same fashion. Heuristics are used to decide when to bulk rebias, then when to bulk revoke and disable SFBL.

So there you have it, you can have you cake and eat it too.  Continue to write those multithreaded applications, run them on mutiprocessor servers, and let the JVM optimize the runtime synchronization.