Descent from the Summit

Just back from wallowing in geekery at another JVM Language Summit. These things always leave me overcaffeinated, exhausted, and completely thrilled.

My big discovery this year is that everyone more or less agrees on what the pain points in the JVM are, in terms of performance and convenience. The people who work on Oracle's (formerly Sun's) JVMs largely mentioned the same desiderata as the people who write languages for the JVM, which are also the things I've wanted as a library writer and occasional author of weird bytecode hacks. Those include structs and value types, arrays that behave well with type parameters and can themselves be value types, and unerased type arguments, all things I would have used recently if I had them.

Of course, just catching the attention of the movers and shakers doesn't mean a quick solution is around the corner. I attended a workshop in 1998 where many of the attendees were quite insistent that they needed value types, and James Gosling agreed and said they ought to go into Java “soon”…

The Psychology of Syntax: Lemon Meringue Pie, Functional-Style

A lemon meringue pie results from baking in a preheated oven for 10 minutes, or until golden brown, a baked pastry shell filled with a lemon filling produced by stirring and boiling until thick the whisked combination of egg yolks and a sugar mixture obtained from whisking together sugar, flour, cornstarch, and salt and adding water, lemon juice, and zest topped with a meringue, spread to seal the edges at the crust, created by whipping until peaks form the mixture resulting from gradually adding sugar to egg whites whipped until foamy.

Functional style is mathematically elegant, but except in small doses, most people find imperative style a lot more readable (as in the original from which this recipe was derived).

Bon appétit!

Hash Table Performance: the Not Always Completely Told Story

Here is a story everyone knows, but with an ending that maybe not everyone knows.

How do you find a piece of information in a data structure? If you want to do so efficiently, generally you use either an array or a hash table.

Your typical Von Neumann machine has only one really efficient data structure built into its architecture: namely, the array, which allows you to map an integer index into a memory location. If the contents of your array are instances of some data type with a fixed maximum size, you can premultiply the index by that size and thereby map the index to a value of the data type stored in the array. If your data type is implemented as pointer to some structure, you can effectively drop the maximum-size constraint (because all array elements are the size of a pointer), at the cost of a pointer dereference on each array element access.

Looking up something in an array generally requires constant (O(1)) time, whereas finding a particular value in a data structure without an array (such as a linked list) takes time proportional to the size of the data structure (O(n)).

Arrays are fine if each thing you want to look up has a number, and if the set of numbers assigned is compact enough that the array fits easily in memory. But not everything you want to find out about is easy to represent as a number. For example, you'll want to order an address book by name, not by assigning a number to everyone you know.

Hash functions are functions that take a value (the “key”) and return an integer (a “hash code”). For a given value, the hash code must always be the same (a hash function is a pure function of the value). The key value is not itself usually an integer (although it can be, which is useful when you look something up using a noncompact set of integers as lookup keys). A hash function argument is often a text string, but it makes sense to transform just about any type of value into a hash code (which is why Java puts hashCode at the top of the type hierarchy, in Object). For example, if you want to keep track of information by object type, you can use a java.lang.Class instance as a hash key.

Hash functions are typically used in a conjunction with a hash table, which is an array whose index is a hash code (or a truncation of a hash code, in the common case where the hash function produces a larger range of values than the size of the array). The hash table has a mechanism for dealing with hash collisions, to cover the case where more than one value has the same truncated hash code. You can view a hash table as an array indexed by something other than an integer, and because the key lookup operation is an array index operation, which is O(1), hash table performance can often be taken to be O(1).

A hash table is more complicated than an array, however, because a hash table usually needs to include its index values within its entries. Except in the case of perfect (collision-free) hashing, you must ensure that the key you think you're looking up is really present in the table—that you haven't instead reached an entry that happens to have the same truncated hash code as the one you want. This typically entails comparing the key you're given with the copy of the key stored in the hash table to entry, to make sure they're the same.

The real performance characteristics of a hash table depend on several factors:

• The time to compute the hash code on an index value. This time is actually O(n), where n is the size of input to the hash function, which might be nontrivial (consider a hash code that examines every character of a long string. If you use the same value as an index more than once, it may be worthwhile to cache the hash code. java.lang.String, for example, caches the hash code for a Java string.)
  
  
• The mechanism used by the hash table to deal with collisions. In hash tables that allocate larger arrays as they grow (the usual strategy), collisions are few, and the overall cost of the array reallocations is amortized O(1), so this cost can typically be ignored.
  
  
• The time required to check whether the index value is valid by comparing it with the index value stored in the hash table. Like the computation of the hash code itself, in the general case, this is O(n) in the size of the data compared. (To ensure that a hash table behaves both efficiently and consistently, you typically want to examine exactly the same components of an index value in both the hash function and the comparison for equality.)

So in fact, hash table performance is not strictly O(1), because it depends on the speed of the hash and equality-check functions applied to the table's keys. For many data structures, however, keys are small (of fixed size, or with a reasonably small maximum size), so that calling the performance O(1) is no more than a little white lie.

Pictures of the Superdesk

The completed desk, partly raised. It goes several inches lower, or a good deal higher, so that it's quite comfortable for both sitting and standing.

I use the mat on the floor when I'm standing to keep my feet from getting tired.

And I heartily recommend the book sitting on my desk, Coders at Work. It's inspiring to see how much great work some people have done, and also a little depressing to see how much I have yet to learn, but mostly it's eye-opening to learn where the experts agree and disagree on how to go about the craft of writing software.

Dragon's Demise, Desk's Design

The copy of Dragon Naturally Speaking that I ordered back in January is no longer with us. As I guessed, it turned out to be too strange to be talking to my computer in the house I share with my partner. I gave it to a friend of mine who has an attic office where he's unlikely to disturb his wife by talking to a machine.

In the brief experimentation I did with Dragon, it was difficult to adjust the microphone close enough that it could hear me talking at a normal volume. And even when I did so, the recognition rate was very low—less than 10%. Since I invested no effort in further effort in figuring out How to Train My Dragon, I don't know how much or how quickly that might improve.

Other people I've since talked to who have experimented with speech recognition software had mixed reviews, but the consensus seemed to be that the technology is still rough around the edges. Given my experience with the microphone, I doubt I'll pursue speech recognition anymore until it advances a lot farther—ideally to the point where you don't actually have to wear the microphone.

Another experiment I'm conducting in smoothing the human-computer interface looks more promising. My partner and I have been building me a sit-stand desk, so that I don't have to spend all day in the same position. I ordered a motorized desk frame from GeekDesk, and we got a piece of butcher block countertop from Ikea to use as the desktop. We also got a Workrite monitor arm for the new 28-inch Hanns G monitor I got from Costco (to keep me from constantly bending my neck down to look at the laptop screen) and a Workrite keyboard tray arm (so I can position the laptop keyboard at a comfortable angle). We cut the butcher block to size and made an additional cutout in it for the keyboard tray to keep the overall desktop size about 48 by 32 inches. Today we finished sanding and oiling the desktop and attached the frame and keyboard arm. Tomorrow, if all goes according to plan, we'll attach the keyboard tray, and move the monitor arm (which I've temporarily attached to an old manually adjustable desk to try it out) to the new desk. And that should be it—I won't have to take computing sitting down any longer!

Postcard from the Bleeding Edge

I love Scala. It's so expressive, it's almost not like writing code at all. It's more like just thinking.

I hate Scala. The official beta release of 2.8 is out, and my existing code doesn't compile anymore. I get a bunch of errors related to the way Scala redesigned its collection classes.

And then when I fix those errors, I get a bunch of deprecation warnings related to my favorite Scala feature, the case class. This has me so irked that I screwed up my courage and made my first post to the Scala mailing lists about it.

It's clear that Scala is still a young language that makes substantial changes from release to release, and that it has not yet achieved the near-perfect stability (or is it fossilization?) of Java.

So does this instability mean the end of my romance with Scala? No. I don't have any installed code base to worry about. And to the extent that I understand the changes in Scala 2.8.0, they mostly seem like a good idea. So for now at least, I'm willing to be tossed in the wake of Scala's developers and deal with whatever they come up with.

It was just a lover's quarrel. Scala and I are fine now. At least until a better language comes along.

Are You a Man, or a Mouse? Or a Joystick?

Maybe the Aerobic Keyboard is a little closer to realization. An article on the front page of yesterday's New York Times talks about how hardware and software have progressed to the point where controlling electronic devices by gestures may soon become common.

And this site describes an experimental project (still in existence?) that effectively lets you use your body as a joystick to move through Second Life.

Computer users of the world, arise! You have nothing to lose but your flab!