{ work }

One Big Ambient Monad

In my last two blogs on The von Neumann Bottleneck and The Problem with Immutability I was flushing out some thoughts on immutability, side effects and the difference between functional and imperative programming.  One thing I continue wrestling with is reconciling "no side effects" with the real world need for side effects.  We know that side effects lead to all sorts of problems but how can we eliminate side effects and still be left with useful programs?  The answer seems to lie in these magic monads that everyone keeps talking about.  So I spent some time skimming some papers on monads.  It seems as though I'm late to the party.  2007-2008 was the big year of the monads, when people were comparing them to burritos, elephants and sexual conquests.  But I'm always late to the party. 

After a day of casual reading I kind of get monads.  There's left unit, right unit, type constructor, a bind function and a couple of other goodies.  Still a bit abstract since when was the last time a Java programmer like myself ran across an explicit monad.  But something still felt off.  Philip Wadler writes in "Monads for functional programming"     

Monads provide a convenient framework for simulating effect found in other languages, such as global state, exception handling, out-put, or non-determinism

So aren't monads just a neat math trick for keeping things pure when things are in fact full of side effects?  That's like me saying my apartment is clean after I shove all my junk in a closet out of sight.  No, it's still dirty, you just can't see it anymore. 

Then I saw this video of Brian Beckman of Microsoft Research explaining the state monad and I think I'm one step closer to my "ah ha" moment.  Sequential programmers (Java, C, etc.) live in a huge ambient monad.  In this ambient monad side effects (updates) are allowed.  FP forces you to live in smaller monads.  Brian Beckman:

In fact there's nothing wrong about side effects at all, it just how disciplined, how precise are you going to be in your use of side effects.  If your programming language allows you to update any variable then you can never tell by looking at a variable whether it has been side effected. All Haskell does is discipline the side effects; so if you're doing side effects you have to do them in an explicitly written monad.  So now you can tell.  The stuff in the monad may have been side effected by whatever function was ahead of you and may be side effected by whatever function is behind you...It's precise in the text of the program. In a programming environment [like c# or vb] you are in am ambient monad so everything is updatable.

OK, this makes a lot more sense now.  Side effect is not this horrible, terrible, bad thing you absolutely cannot have (duh), you just need to be precise with it.  There's no way to be precise with it in Java or the imperative languages (enforce preciseness), but there is a way to be precise with it in functional languages.  Monads make this precision more convenient than passing the world around as was done in the past.

It should be noted that Beckman goes on to say that monads are not a panacea.  While reading up on Haskell one question in the back of my mind was how does Haskell do logging?  In Java I can do something like System.out.println("the value of x is " + x), but does this mean I have to use the IO monad now to do basic logging?  And Beckman points this out as a shortcoming, that to just do a printf you have to rewrite your functions to use monad.  I guess that's why there's some "unsafe" IO stuff you can do in Haskell, but as the name implies it's unsafe and the compiler can't guarantee things, as it can with monads.

The Problem with Immutability

There's been so many articles touting the benefits of functional programming lately.  Read just a few and one theme immediately emerges: no side effects is good.  With immutability there's no side effects, and with no side effects life becomes a lot easier.  Programs are easier to write, compose, debug and you get concurrency for "free".  While all this may be true, I feel there needs to be a little balance on the subject lest some people start to think functional programming is a silver bullet. 

We live in an imperative world where there's state and things are mutable.    This fact alone hints as to why functional programming cannot be the end all solution.  I/O is the classic example of where imperative operations are required.  For example, Haskell, a functional language, has these things called monads to do I/O.  Michael Scott writes in Programming Language Pragmatics,

Monads...acknowledge that the physical world is imperative, and that a language that needs to interact with the physical world in nontrivial ways must include imperative features.

I also recall a recent article with Joe Armstrong on state and mutability in Erlang that came to the same obvious conclusion: state and side effects are necessary, we just need to confine them so the rest of the program is not polluted.

Beyond this inherent issue of modeling the imperative physical world, there are just some things that are more imperative in nature, like counting and updating.  Destructive updating assignments may clog the von Neumann tube, but immutability creates a lot of garbage.  The need for destructive updates leads to the so-called trivial update problem.  How can we efficiently handle updates without creating new copies of the entire data structure.  In imperative languages it's very easy to do map.remove("myKey") but in a functional language you have to call a function passing in the current immutable map and getting back a new immutable map with one entry removed. 

There are two ways to deal with this.  One is to hope your compiler can optimize.  If the compiler can verify that the old map is never used after the function returns instead of creating a new copy of the map the compiler can just do the update imperatively, in-place.  Apparently there's this Sisal compiler that was shown to eliminate 99-100% of all copy operations.  And that was back in 1992.  Then again, that was very geared toward numerical calculations, so I'm not sure how things would translate to your run of the mill web app.

Another approach is to make your data structures smarter.  Smarter is probably the wrong word.  The key is to recognize the difference between imperative and functional data structures.  In imperative languages data structures are ephemeral, existing as-is, without a history.  Think of all the data structures we use everyday in Java: HashSet, HashMap, ArrayList.  They're all ephemeral.  Functional languages, because of immutability, have automatically persistent data structures.  Adding two elements to an initially empty list means you have three versions of the list: (), (e1), (e1 e2).  In the imperative world you just have a single list of three elements.

The problem is how to achieve persistence with O(1) additional space and O(1) slowdown.  Good news is really smart guys like Sleator, Tarjan and Okasaki have laid the foundation for efficient persistent data structures.  I know Rich Hickey's Clojure has persistent data structures base on Okasaki's work with some modifications to get around just the amortized guarantees.  A lot of the work around persistent data structures is around amortized running times, but Clojure has these "persistent vectors" so the time is guaranteed for certain data structures.  While much progress has been made in this area ephemeral data structures still have quite a head start.

As someone who's basically programmed in Java all his career I find all this very functional stuff very fascinating.  No doubt about functional programming's many pros, but it's also good to be aware of the cons.  I remember when Java faced much criticism because creating objects was expensive, but those criticism have largely subsided.  The Java language hasn't really changed, the bad programs we (I) write definitely haven't changed--it's just that the JVM has gotten a lot better at resource management.  So is functional programming at a similar stage, where all that's needed is improvements in compiler optimization and better functional data structures?  Or are we already there and I'm not just aware of it? 

The von Neumann Bottleneck

In high school English literature was my favourite class because it was the one class where I could be creative and develop new ideas, not just memorize equations.  But then it dawned on me that all my novel ideas and perspectives were just hackneyed, recycled ideas some guy from 1625 already wrote at length on.  This made me depress.  Today, more than a decade after high school, I find myself in the same predicament.  All these "new" things that seem so fascinating and exciting--well, they're just the same old ideas with a few refinements here and there.  It's pretty damn depressing.  Is there nothing truly original left in this world?

Take functional programming, for example.  It's all the rage these days.  I first wrote about it in January of 2007 in an entry titled "The Rise of Functional Programming".  Two and half years later FP is still going strong.  Just search DZone, Artima, InfoQ.  Countless articles and presentation of how imperative programming no longer meets the challenges of today's complex, concurrent world--and how functional programming can.  This gets me excited.  Have we reached a new stage of enlightenment, ready to move beyond for loops?  Are we at a tipping point?

Then I read this paper entitled "Can Programming Be Liberated from the von Neumann Style?  A Functional Style and Its Algebra of Programs" by John Backus, dated August 1978.  WTF, 1978.  In 1978 Backus was already telling us what so many experts are just telling us today, that mainstream programming languages suck.  It really is true, everything interesting in computer science was done between 1950-1980.

When I first saw the paper I asked myself, "who's this John Backus guy anyway?"  Well, he's the B in BNF and lead the invention of FORTRAN.  Hmm, OK, maybe I better read his paper, even if it's so old that all the PDFs on the web are bad scans from an ACM reprint.  Here's the elevator summary of the paper.

All the computers we work with are von Neumann computers, named after the Hungarian bad-ass mathematician John von Neumann.  There's a CPU, a store that holds both data and instruction (memory), and a connecting tube that can transmits a single word (think 16, 32, 64-bit) between the CPU and store.  As the great Senator Ted Stevens from Alaska astutely observed, tubes get clogged.  Backus called this tube the von Neumann bottleneck.  The adverse effect of the von Neumann model is "we have grown up with a style of programming that concerns itself with this word-at-a-time traffic through the bottleneck rather than with the larger conceptual units of our problems."

More than 30 years ago Backus was bitching about the things we're bitching about today.  And many of us are only bitching about it because of the "multi-core revolution" and our desire for immutablity.  It really is depressing, to think about it.  We're still writing a bunch of statements to manipulate memory via this clogged tube.  Half the time we're not even dealing with the data, we're just assigning variables that point to the data.  Tomorrow, when I come into work bright and early, I know I'll be excited to spend the day thinking of ways to best clog this von Neumann tube.

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.

Axes of Systems - Performance, Capacity and Scalability

I like to think of software systems as having three axes: performance, capacity, scalability.  While related, each axis is independent of each other.  This is evident by systems that are high performing but unable to scale.

First, lets define the terms involved using a fictitious system that accepts requests to process images (resize, correct exposure, etc.). 

Performance is something we are all acutely aware of if we've ever bitched at Microsoft Outlook's search functionality.  Performance is how fast we can do something, typically measured in units of time.  In our image processing system a baseline image of some fixed size and some fixed color depth may take 500 milliseconds (ms) to process under some fixed conditions (e.g., system has gone through warmup, VM has optimized the code, lazy caches have been loaded, etc.).  That's our performance. 

Capacity is how much your system can handle subject to some service level agreement (SLA), which may be an internal SLA we provide to other teams in the company, not just an external facing SLA to our customers.  Say our system has an SLA that mandates 95 percent of all images be processed in under 1500 ms (tp95).  Given this SLA our system can process 100 images per second (100 requests per second).  More requests than this and our SLA will not be met.  The result could be fatal errors (maybe we run out of memory and crash) or gradual degradation, typically the more desirable behavior.  At 150 requests/second we can only meet an SLA of 2000 ms tp95; at 200 requests/second we can only meet and SLA of 2300 ms tp95.  So forth.

Performance and capacity treat our system as fixed.  Our system could consist of a single server or several servers--it's whatever we choose.  We can vary our inputs or change our system configuration/state to get new performance and capacity numbers, but fundamentally the system is fixed.

Scalability, on the other hand, treats our system as malleable.  Scalability is how our system responds when we add resources to the system.  Scalability is the affect on our system of additional resources--servers, storage, etc.  Some literature discuss scalability in terms of how the system is affected under various loads; but I prefer to view that as performance and capacity under different configurations/inputs to maintain a clear separation that scalability involves the addition of resources to the system. 

Scalability is a broader term than performance and capacity.  Here are three examples of scalability.

Operational scalability.  Say our system, currently consisting of 10 nodes, requires 2 IT guys to manage.  Tomorrow, if we add 10 more nodes will it require 2 more IT guys to manage?  If it does then we have horrible operational scalability.  A system that can operationally scale should require the same number of people to manage 10 servers or 20 servers. 

Capacity scalability.  Given the same SLA as above, if we add more storage or more servers to the system will our capacity increase and how does it increase?  The design of some systems make it impossible to increase capacity with additional resources.  Our image processing system can scale in capacity fairly easily if image processing is self-contained.  Add a new server and we can now guarantee an SLA of 120 req/sec @ 1500 ms tp95 compared to the previous 100 req/sec.  On the other hand, if the first thing our system did was store the image in a single, monolithic, already maxed out database, we can add all the servers to the system we want and capacity will remain the same until we re-architect/re-design our system to get rid of that single database.

Performance scalability.  Will additional resources improve my system performance?  If our image processing algorithm is serially, no.  An image will still require 500ms to process.  If our algorithm split the images into parts and farmed things out to multiple servers to be done in parallel, addiing servers will reduce our processing time.

Performance, capacity and scalability are related but not in any direct way.  Think of all these different ways a system can be characterized,

• great performance but unable to scale
• decent performance and can scale
• bad performance and can't scalability
• great performance but low capacity
• etc.

Often these dimensions are at odds with one another.  Our image processor might be very fast, able to process images in 100 ms, but require excessive memory, reducing our capacity.  Great performing systems might not be very scalable without a lot of work.

Scala Gets Operator Overloading Wrong

If you like programming languages here's an interesting interview and discussion on language design and evolution featuring Erik Meijer, Gilad Bracha and Mads Torgersen.  I came across the video while googling for Mads Torgersen and his paper "The Expression Problem Revisited."  Gilad Bracha I recognized from the Java world and his thoughts on dependency injection with respect to his Newspeak language when I proclaimed that dependency injection is broken.  Not sure who Erik Meijer, but he looks really familiar.  Basically three really smart guys shooting the shit on languages.

One thing that stuck with me was language purity.  Erik mentioned that he really likes languages that are base on one fundamental concept, idea, notion.  A language where everything is a function (Haskell).  A language were everything is virtual (Newspeak).  A language where everything is a message send (Self). 

Java is far from pure and singular.  Most things are objects, but a few aren't.  You can do reflection, but not really.  Etc.  It then hit me why I've never really liked Java:  Java doesn't have a raison d'être.  Some people bash Java for its verbosity, or because it lack this feature or that feature, but those things don't really bother me as much as Java's conceptual elegance--lack thereof.  It is, by designed, a mix bag, meant for the hoi polloi.  And It's quite successful at what it does.  Don't get me wrong, I'm not a language zealot.  Java is great, with its VM, the available IDEs, the libraries, etc.  But it'll always be a Porsche, not a Ferrari (Porsche has always been designed with driveability in mind--the every man's sport car).

So I started thinking about Scala versus Newspeak/Smalltalk.  I think part of the reason Scala has been successful is it adopts a less than pure approach--a pragmatic approach.  Here's a trivial example (like all trivial examples it could just prove a trivial point).  Joey Gibson writes that Scala gets operator overloading right because 2 + 3 * 5  = 17 in Scala but 2 + 3 * 5 = 25 in Smalltalk (and likewise Newspeak).  But it's not that Scala gets it right, it's that Scala has chosen a pragmatic approach to operator precedence.  If Scala was pure then 2 + 3 * 5 would equal 25, because + and * are just ordinary methods on objects;  it'd be like saying method foo has higher precedence than method bar.  Smalltalk treats + and * equally because there's nothing special about them and the expression precedence is well-defined at a higher level: unary messages, then binary messages, then keywords.

Pragmatism "wins" in the "real" world.  That's why I don't expect Newspeak to gain wide adoption.  Worse is better?

The Expression Problem and Other Mysteries of Life

The "expression problem" or the "extensibility problem" is closely related to the Open-Closed Principle (OCP).  OCP states that software should be open for extension but closed to modification.  The expression problem observes that for the two fundamental dimensions found in programs, data types and operations, OCP is only achieved for one but not both.

Take, for example, an application involving vehicles.  There two kinds of vehicles, automobiles and trucks.  All vehicles can accelerate.  It is easy to extend our application to include space ships. 

The problem arises when we realize that vehicles should also be able to brake.  To add a brake operation we will need to modify vehicle, automobile and truck; violating OCP.

We can attempt to approach things from a more operational point of view.  Using something like the visitor pattern we can build our application to handle new operations without the need to modify existing source code.  Here we simply add a new brake operation visitor.

But now the problem becomes how do we add a new vehicle to our application without violating OCP.  It is not hard to add a truck vehicle but all of our existing operations must be aware of truck.

Mind you, we want to achieve everything discussed so far with type safety, and static type safety at that, because, as Bertrand Meyer would argue, run time is a little late to find out whether you have a landing gear.  Incidentally, if you're wondering what the mysteries of life title is all about, it from this Meyer's article.  I find his style amusing.

So how can we solve this expression problem and the goals of Open-Closed?  Don't ask me, I'm just a guy with a blog who likes to use OmniGraffle.  But from what I've been able to gather there's no easy, straightforward solution.  We can use generics and "F-bounds" but the code then looks like

interface FooBar<C extends FooBar<C>> extends Bar<C> {...}

Quick, anybody knows what this means, because I sure have a hard time keeping track of recursive types.  The Scala guys say you can solve the problem with abstract types, self types and mixins.  But there seems to be a lot of scaffolding involved--lots of redefinition.  Maybe it's not so bad if I really knew Scala beyond a cursory level.  Some people argue these techniques only work if you have the foresight--you have to parameterized your design from the beginning; you have to declare types as abstract types from the start; etc.  Multi-dispath/multi-methods can help, but I don't think any mainstream languages support those constructs. 

In conclusion, I have no idea what I'm talking about.  But I do find it interesting--and a bit sad--that such a seemingly fundamental problem, the expression problem, is pretty involved to solve.  You would think by now some brilliant language designer would have figured things out in a simple, elegant way.

Scalable Component Abstractions

If I was to summarize the evolution of my thoughts regarding dependency injection (DI)...

What is this dependency injection thing everybody is so excited about?

Oh, you mean decoupling interface and implementation--I like that. 

So what do these DI frameworks bring to the table?

Less boilerplate code--that's good.

But now I have a dependency on a framework--that kind of sucks.

Now I have all this hairy configuration in some XML file--that really sucks.

Annotations are pretty cool.  Still seems like be can do better.

Well, it's 2009 and maybe we have done better.  Consider how the Scala compiler is composed

While it's not called dependency injection per se the net result is the same: we're able to abstract the required services.  Tomorrow, if we wanted to log symbols we'd just implement a new LogSymbols and use mixin composition to get our new behavior.  Or we can stub/mock out Symbols during testing.  All without boilerplate code, messy configuration or clumsy bindings.  And everything is type-safe.  Pretty cool initial impression.  

You can read more about how Scala does it in "Scalable Component Abstractions."  Some of stuff is a bit foreign unless you have a strong functional background or really into type systems, but the compiler case study helps.

A Rebuttal to The Myth of the Genius Programmer

Started listening to Brian Fitzpatrick and Ben Collins-Sussman's talk on "The Myth of the Genius Programmer" during Google I/O 2009.  This is the talk's abstract,

A pervasive elitism hovers in the background of collaborative software development: everyone secretly wants to be seen as a genius. In this talk, we discuss how to avoid this trap and gracefully exchange personal ego for personal growth and super-charged collaboration. We'll also examine how software tools affect social behaviors, and how to successfully manage the growth of new ideas.

I'm not sure if I entirely agree with their opinions.  If you take a look at sports, the world's best athletes all have huge egos.  But their egos do not prevent them from learning from coaches, working effectively with their teammates and leading their teams to championships.  Why lose the ego?  Is it a bad thing to want to be seen as a genius, as long as you can continue to accept criticism, learn from your peers, work with your peers, accept failure, admit mistakes? The desire to be seen as a genius programmer can be a great motivating force for programmers, just as the desire to be the best can be a great motivating factor for athletes.  A healthy ego is not mutually exclusive with super-charged collaboration, although that's the feeling I get from watching the video.

In my ten years of programming I often wished some of my colleagues had bigger egos.  I generally find those without healthy egos often don't care about their work.  The programmer who wants to be seen as a genius will put in the extra effort to clean up his code, make his algorithm more efficient, track down subtle bugs, because he wants to be seen as the best programmer.  The genius programmer walks around with a bug count hovering over his head--and he's intent on keeping that bug count low.  The ego-less programmer will call it a day to go home and catch American Idol.  Then again, I've also worked with developers whose ego prevent them from admitting to bugs and design flaws.  The key is not to lose the ego but to have the right kind of ego, the ego that will motivate but not stifle.

Now this might be a stretch but I get the sense that Brian and Ben want a Communistic approach to software.  First they talk about losing your identity (your ego).  Then they talked about the community as stronger than the individual using the Apache Foundation example.  I don't know, it just sounds kind of like Communism.  There's no "me" in Communism, just the state.  Everybody is collaborating to further the state.  Well, we know how Communism turned out. 

Capitalism, on the other hand, while certainly not perfect, has brought more benefits to more people than any social-economic system in history.  At the core of Capitalism is the individual.  I would argue that healthy egos drive Capitalism and innovation.  This works because in Capitalism what is locally optimal for the individual is globally optimal for the state.  There's no shortage of collaboration in Capitalism, why would it not be the same in a team full of genius programmers?

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.