Javasaurus

Nothing about dinosaurs; apologies to any 6-year-olds I've misled.

There's an interface in the Java libraries called "Runnable", that just packages up the idea of "some code that you might want to run." This is handy when writing algorithms like "do some preparation; then run whatever it is the client wants to run; then do some clean-up." It's a way to hand a series of program steps from one module to another without having to know in advance what those steps are. ("Closures," much debated in Java, are another way of doing this.)

Runnable defines one method, "run". But the "run" method doesn't allow for the possibility of failure. I needed something similar, that was allowed to communicate failure (by throwing an exception). I knew there was something, but what? A search of the likely spots didn't turn up what I was looking for.

It would be really cool if there was a Thesaurus of Java, a tool or a web site that would let me type in "Runnable" and would come back with all the other things that were kind of like "Runnable." In this case the answer, provided by my colleague Hung, is "Callable." Doh.

A similar task that comes up for me a lot is that I've got a This, and I know it's possible to convert it to a That, but I'm not sure how. For instance, let's say I've got an Eclipse IFile, and I want to convert it to an ordinary Java File. The mapping isn't perfect, but basically, given an IFile there is a chain of methods you can call that will either get you the corresponding File or tell you it doesn't exist. But what is that chain of methods?

There's a finite number of methods that take an IFile as an argument (or receiver). There's a finite number of methods that produce a File. So there's a finite, although very large, possible graph between them - for instance, you could imagine calling something like IFile.getURL() and then URL.getFileDescriptor() and then FileDescriptor.getFile(). (I just made those names up, that's not the real answer.)

Most of the paths through the graph will be wrong, and some will be long and some will be short. But you could use the same sort of semantic analysis tools that are used for natural language translation, feeding off existing code (such as the Eclipse code base, in this example), to inform the graph of common versus uncommon pairings. I'd enter my start and end types, and I'd see a view of the top ten paths through the graph of possible method calls connecting them, perhaps even with links to existing code examples where something like that path had been used before.

I tried Googling for "Java Thesaurus" to see if this existed already, but all that comes up is Java code for writing thesauri.

Comments

I often hear that comments in source code are A Bad Thing. Comments are evil because they don't accurately describe the code they apply to; because the code gets modified and the comment doesn't; because good code is self-documenting and therefore doesn't need comments; and because you need to read the code anyway to understand what it does and so comments just get in the way.

Horseshit.

This is roughly like saying that synchronization is evil, because it's often done incorrectly, because it gets broken when people update the code without fixing the synchronization, and because good code uses constructs like immutability that don't require synchronization.

If we treated comments as being as important as synchronization, they'd live up to their end of the deal just fine. There is nothing inherent in the idea of a comment that renders it impotent. Think of comments as being like error-handling code or synchronization: bulky, hard to write, even harder to test, but crucial to reliability.

I think the real reason so little code is commented is simply that most code is written in short bursts of effort by highly productive individuals, and while they're writing it, they understand their own assumptions well enough to not need the comments themselves, and they're in too much of a hurry to worry about the next fellow. And because this is what new programmers then see all around them, this is how they in turn learn to program.

If we built buildings this way, instead of having architectural drawings, the carpenters would come in after the foundations were poured, look at where the rebar was sticking out, and frame the walls where it looked like they should probably go. The resulting buildings would be ugly, short, and tend to collapse in a few years. Much like software, in fact.

If I were to design a programming language, any uncommented abstract definition (for instance, a method definition in an interface class) would be a compiler error. Yes, people would work around it by putting in useless comments, but it would be a start.

Control Theory

In the last post I mentioned that we programmers don't generally get training in control theory. This is too bad, because I think learning to recognize the behavioral modes of feedback-controlled systems can have a lot of practical benefit for us.

Suppose that you have the following two Java classes, B and Main. Without running this, can you tell how it will behave?

If you do run it, you'll see that the output is spread across a range of numbers. Without changing class B, how would you make that range smaller? What properties of the code determine the range?

This program is an analog of an elementary problem in control theory, so basic that even my espresso machine implements a solution to it. But I suspect that most computer programmers, coming upon behavior like this while performance-tuning an application, wouldn't immediately recognize it.

public class B implements Runnable {
  private static final int ELEMENTS = 100;
  private double[] v = new double[ELEMENTS];
  private boolean state;
  private volatile boolean done = false;
  
  public void run() {
    while (!done) {
      synchronized(this) {
        v[0] = state ? 200.0 : 0.0; 
        // propagate gradually through the array
        int i;
        for (i = 1; i < v.length - 1; ++i) {
          v[i] = (v[i - 1] + v[i] + v[i + 1]) / 3.0;
        }
        v[i] = (v[i - 1] + v[i]) / 2.0;
      }
      try {
        Thread.sleep(1);
      } catch (InterruptedException e) {}
    }
  }

  public synchronized int get() {
    return (int)v[v.length - 1];
  }
  
  public synchronized void set(boolean state) {
    this.state = state;
  }
  
  public void finish() {
    done = true;
  }
}


public class Main {
  final Object l = new Object();
  final long end = System.currentTimeMillis() + 60000; // 1 minute
  
  public static void main(String[] args) {
    new Main().run();
  }
  
  private void run() {
    B b = new B();
    new Thread(b).start();
    
    while (System.currentTimeMillis() < end) {
      double t = b.get();
      boolean state = t < 50.0;
      System.out.println("t = " + t + 
        " - state is " + (state ? "true" : "false"));
      
      b.set(t < 50.0);
      try {
        Thread.sleep(1000);
      } catch (InterruptedException e) {}
    }
    b.finish();
  }
}

Synchronization and Relativity

Thinking about state as a way of reasoning about synchronization seems like a good approach. But the problem is, the concerns I have about synchronization are often about execution: will it deadlock? Will there be lock contention? Reasoning purely about state leads me to write programs where the data is always correct but nothing can actually complete. Both state and execution are important, and they're kind of like matter and energy, seemingly unrelated concepts.

Einstein managed to show that energy and matter were actually two sides of the same coin: that a certain amount of matter was, in fact, equivalent to a certain amount of energy, if you chose the right units. Particle physicists took this and ran with it, coming up with the idea of symmetry breaking and explaining the circumstances it takes for the coin to flip. I need someone to do the same for multithreading. I want a theory of multithreading relativity that explains how given multithreading constructs act on execution and state, and what the symmetries are.

For instance, if you protect state with a mutex (in Java, a "synchronized()" block), then you can debug deadlocks by asking the system what threads own what locks. But you can also protect state by waiting for a notification event; this is a common way to implement a reader/writer pattern. The result is similar: the state is protected at the expense of some thread being blocked. But when a system deadlocks because every thread is waiting for a notification, there's no way to ask the system which thread was supposed to send it.

You'll never make a program hang by removing a synchronized(), but you might make a program hang by removing a notify(). On the other hand, you'll never make a program corrupt data by removing a notify(), but you might make a program corrupt data by removing a synchronized(). Is this a real symmetry?

Similarly, it's possible (but maybe not algorithmically possible) to look at code and see at least the hallmarks of deadlockability: for instance, code that takes nested locks out of order. Is there an equivalent analysis for code based on wait() and notify()?

In electrical engineering, it's possible to take any circuit based on voltage sources and impedances, and convert it (using the Thevenin and Norton theorems) to a different but equivalent circuit based on current sources and impedances, that will behave just the same to an outside observer. Doing this is often very useful for understanding how a circuit works. Is this possible for synchronization? Given some code implemented with certain synchronization tools, is it always possible to reimplement that code using different synchronization tools, such that the behavior will be the same? What do the rules of that conversion look like, and what will I learn about the underlying synchronization pattern by doing this? Exactly what "behavior" will prove to be invariant?

Synchronization is Hard

I read a newspaper story about a neuropsychologist who had a stroke. She recounted trying to call 911, but not being able to figure out which digit was which on the phone, or what the steps were to make a phone call. She knew what the right tool was, but she'd lost the cognitive tools to use it. All the while, being a neuropsychologist, she was aware of what was going on, and even somewhat fascinated by it, but also aware that her life depended on doing a seemingly simple thing that she nonetheless could not quite grok.

Synchronization is like this for me. At least I know I'm not alone - some of the smartest people I know have a hard time thinking about synchronization problems, and my industry is littered with bugs due to incorrect synchronization. But I always feel like there's a right way to reason about these problems, and I know it's there but I don't know what it is and I can't even quite articulate why it is that I can't think clearly about it. My hope is that one day I'll GET IT and then I won't be able to remember why I couldn't figure it out before.

I do know some wrong ways to think about synchronization, though. Any time I am reasoning about synchronization and I find myself thinking "okay, if two threads come in here at the same time...", I am about to make a mistake or go down a rat hole. This is how books always present the topic, but intuitively I think it's wrong - I don't believe you can think correctly about synchronization by thinking about execution.

Instead, I think it's probably better to reason in terms of state. "What states could this object be in when this variable is evaluated?" "If I modify the state, how will other threads discover the modification?"

Today I spent a couple hours trying, along with some people who are pretty good at these things, to come up with a good pattern for lazy initialization when the initialization routine is not trusted (e.g., when it might try to call back into the object being initialized). The real moral of the experience is twofold: first, we each wrote routines that we thought were good and that were promptly found wrong by the others; second, although I think we did end up with two valid solutions, I'm not sure how to PROVE that they're valid.

Hibernate locking

To continue the last topic: I'm working on a program that lets examinations be taken online. It uses Hibernate to get stuff from a database - for example, we get a list of possible answers to an exam question. The list is implemented by Hibernate, so that it doesn't actually read the database until the first time someone tries to access the contents of the list. But that fact is invisible to our code - to us it just looks like an ordinary Java list.

Now, like the ordinary Java collections, the Hibernate-provided collections don't have any built-in synchronization. If you tried to read the list from two threads at a time, it might try to initialize the collection twice, or not at all, or it might just crash.

This is not a problem for most uses of Hibernate. Generally any given Hibernate collection is only accessed by one execution thread, even though there might be zillions of Hibernate collections all referencing the same table in the database.

But in our application, we use the same collection from a lot of threads - perhaps tens of thousands, distributed over a cluster of machines with Terracotta. We never modify it, we just read it. Except for the very first time it's accessed. But there's no way to tell, from the outside, whether it's the first time - so we have to treat it as if it might be, every time.

This pattern does not work well. We could wrap the collections inside "synchronized" blocks, like the java.util.Collections$SynchronizedWhatever classes do; but that means that every time any thread tries to read an entry in the list, it has to wait for every other thread to get out of the way first, just because once upon a time one of those threads did the initialization.

Like I said in the last entry: replacing the implementation without changing the interface is powerful, but it means there's no way to know whether an operation is actually a read or a write. Locking is one reason why a caller cares about implementation.

The solution is to change the Hibernate code so that it does its own locking, using a read/write lock. Within a single method, it can take a read lock to figure out whether initialization is needed; if it is, then it gives up the read lock and takes a write lock to do the initialization. The first time through, a write lock will be taken, but (nearly) every time thereafter, it'll only need a read lock, which means that no thread will ever have to wait. In practice this is very effective. In one performance test we saw a roughly 200x speedup: latencies went from 4 seconds to 20 milliseconds.

The unfortunate part is that the code gets messier. This nice code:

  int size() {
    if (!initialized) {
      initialize();
      initialized = true;
    }
    return size;
  }

Becomes:

  int size() {
    readLock.lock();
    try {
      if (initialized) {
        return size;
      }
    } finally {
      readLock.unlock();
    }
    writeLock.lock();
    try {
      if (!initialized) {
        initialize();
        initialized = true;
      }
      return size;
    } finally {
      writeLock.unlock();
    }
  }

Amidst all the locking and unlocking and multiple checking, it's hard to see what's actually being done by the method. Which gets back to my first post.

The two R's

Computer software consists of a lot of instructions that read and write information to memory. The basic idea hasn't changed since World War II. Imagine a gazillion toggle switches, each of which can be flipped up or down. That's the memory, and then there's a processor that runs instructions, what we call the "code". The instructions are like "go look at switch 3,452,125 and see if it's flipped up. Then go look at switch 35,289 and see if it's flipped up. If they're both flipped up, then go find switch 278,311 and flip it down." And so forth. Some of the switches do things, like turn on a pixel on the computer screen. Others are just there to remember. We have nice tools so that we don't actually have to use numbers for the individual switches when we write the instructions, but under the covers that's exactly what's going on.

I work at a company called Terracotta Technology. We make software that connects many computers together so that they can solve problems bigger than one computer could handle. We make a sort of virtual computer, that other people's programs can execute on. We fool the programs that run on Terracotta into thinking they're running on a normal computer. A program thinks it's flipping a switch on its own computer, when actually it might be on some other computer.

So, we care a lot about when the programs try to read from memory and when they try to write to it, because we have to intercept all those operations. If all they want to do is read, we don't have to do as much work. Flipping a switch, in our world, that's real work.

This idea of replacing what's under the covers without changing how it looks to the software that's using it is not original - it comes up over and over again in software, in fact it's probably the single biggest idea the industry ever had. Hibernate is another product that does something like this. Hibernate takes reads and writes to memory, and supports them with reads and writes to a database, which is more reliable and persistent and searchable. A programmer could just write instructions to talk directly to the database, but Hibernate makes it easier by hiding some of the complexity under the covers.

But the illusion breaks down. The picture up above is what happens when you ask Hibernate how many things are in a list. Asking how many things are in a list shouldn't change it, right? That's common sense. But asking Hibernate how many things are in a list might change memory, because it might have to go fetch the information from the database and then save it in memory.

So if you want to figure out whether an operation is a "read" or a "write" or both, you need to know who's responsible for performing it. And that's something that can change on the fly, because we're so good at replacing what's under the covers.

But why do we care about the distinction anyway? Are reading and writing really the only way to compute? Why should this implementational distinction matter to a programmer?

Is this the path to functional programming?

Ignorance is the mother of invention

I spend too much of my time trying to figure out what pieces of software do.

In 2008, generations after we started programming, it is still almost always easier to write an okay prototype yourself, than to use an existing component that someone else wrote. This is nuts. This is why software engineers like me still get paid as much as we do. I appreciate the pay, but it's holding back the industry.

The reason for this is that with very rare exceptions, we engineers suck at saying what the code we write does, and for that matter we also suck at coming up with code that does things that can be succinctly described. The rare exceptions have names like Josh Bloch.

Good software engineers excel at looking at other engineers' implementations - at the program code that they wrote - and figuring out what it does. (I am not very good at this, and I admire it in my coworkers.) That is because it's the only way to survive in the industry; there is no other way to figure out what a component does.

Imagine that, before going to the loo, you needed to trace the plumbing to make sure that it actually exited to a sewer rather than the drinking fountain. Imagine that before starting a rental car you needed to trace the ignition wiring to make sure that turning the key clockwise wouldn't break the timing belt. This is the state of the software industry.

When one piece of software calls another piece, it needs to give it some data, and then it expects some data back. The important things that it needs to know include: what is the range of data that it can safely pass in? What is the range of data that might be returned? Will anything change as a result of the call? Is it okay to call again, before the first answer comes back? If the rules are broken, how bad are the consequences?

The tools used in the mainstream software industry do not answer ANY of these questions. Instead we have "comments," which are bits of text written by the software engineer, hopefully describing the situation. This does not work, because comments (a) are not required; (b) are written by software engineers, who are often not very good writers; (c) do not have any validation; (d) are often not updated when the code is updated.

To continue with the loo analogy, it's as if the plumber put a sticky note on the toilet. The plumber assumes that you know the things that were obvious to him and focuses on the details you might not know, so the note says something like "sewer line is made of cast iron," rather than what you really need to know, "flushing toilet will cause contents to be safely sent elsewhere." But it doesn't matter, because at some point someone else went into the basement and replaced the cast iron with PVC, without realizing that there was a sticky note on the toilet.

This is the most serious problem the software industry faces. Arguing about whether Java 7 should include closures is irrelevant. We need enforceable, validatable contracts that describe how software components can correctly be used.