Fun times with concurrency.

March 18, 2011

Just checked in an improvement for JDBM at google code (we are using jdbm here for a little job), applying a pattern for handling thread contention that I worked out a while ago. Didn’t have the source, but I remembered how it worked. I think I’m getting old, you know – recognising problems as something that I encountered ages ago in another context.

I any case, the particular specific fun bit is LockingStrategy.java.

Basically – we have a “thing” and it’s mostly threadsafe. For certain operations (we’ll call ’em reads): go for it. Threads won’t interfere and we want them to be able to run freely. But certain other operations need exclusive access to the thing – all other threads must block.

The problem is that things that need exclusive access can’t just wait for no-one to be reading. Like one of those people that can’t merge onto a freeway, they’d wait forever. The reading threads have to stop and wait when something needs exclusive access. Thus, although readers run freely with respect to one another, they cant do so with respect to threads that exclusively lock.

Potentially, multiple threads might want exclusive access. They have to run one at a time.

And finally – I don’t want things to poll. Polling is bad. Everything must wait() and be notify()ed.

The key to the algorithm is the use of two java mutexes, not one. One regulates the readers, and one regulates the exclusive lockers. The interplay between the two, however, is … a bit of a headspin. But it does work.


Java intersection types

April 6, 2010

There is an obscure little language feature in java, called intersection types, which I have miraculously found a use for. Quite a nice use really.

As you no doubt know, enumerated types cannot be subclassed, because they “belong” to the language itself. This is a bit of a hassle when you have a variety of enumerated types that have common functionality. A typical example of this is when your enum constants have corresponding database records.

(BTW: this is always a horror to work with, because you need to synchronise your java code with your database records)

You have a “lookup” table in the database, containing sets of constants for “state” and for “city”, let’s say, and an “importance” field. The corresponding java is:

enum City {
    NSW, ACT, VIC;
    private int importance;
    public int getImportance() {...;}
    void setImportance();
}

enum State {
    SYD, CAN, WAG;
    private int importance;
    public int getImportance() {...;}
    void setImportance();
}

Now, setting the importance from the database is reasonably easy:

    for(City c: Enum.allOf(City.class)) {
        c.setImportance(getImportanceFor(c));
    }

But you need a separate loop for each enumeration. There may be several. Even worse, the getImportanceFor() method is not type-safe: it just takes an enum.

A java intersection type is a type that is an intersection of othertypes. Just as an interface can extend any number of other interfaces, an intersection type can “extend” a class and any number of interfaces. But it’s a synthetic thing: no class is created for it, there is no .class file. The compiled code simply understands that the class extends the correct types, without casting or type-checking.

So. Let’s create an interface and implement it:

interface Lookup<T extends Enum<T>> {
 public int getImportance();
 public void setImportance(int importance);
}

enum City implements Lookup<City>{
 NSW, ACT, VIC;
 private int importance;
 public int getImportance() {
  return importance;
 }
 public void setImportance(int importance){
  this.importance=importance;
 }
}

enum State implements Lookup<State>{
 SYD, CAN, WAG;
 private int importance;
 public int getImportance() {
  return importance;
 }
 public void setImportance(int importance){
  this.importance=importance;
 }
}

At this stage, we can do the magic thing: we can state that a method takes a parameter that is both an Enum and also a Lookup. So, let’s define a method to which you pass a lookup/enum class, and which fills in the importance values:

enum State implements Lookup<State>{
 NSW, ACT, VIC;
 static {
   LookupDAO.getDAO()
     .fillinImportance(State.class);
 }
 private int importance;
 public int getImportance() {
  return importance;
 }
 public void setImportance(int importance) {
  this.importance=importance;
 }
}

enum City implements Lookup<City>{
 SYD, CAN, WAG;
 static {
  LookupDAO.getDAO()
    .fillinImportance(City.class);
 }
 private int importance;
 public int getImportance() {
  return importance;
 }
 public void setImportance(int importance) {
  this.importance=importance;
 }
}

abstract class LookupDAO {
 public <T extends Enum<T> & Lookup<T>> 
       void fillinImportance(Class<T> c) {
   for(T e: EnumSet.allOf(c)) {
     e.setImportance(
       getLookupImportance(e.name()));
   }
 }
 // DAO implementation goes in a subclass ////////
 protected abstract int getLookupImportance(String code);
 public static LookupDAO getDAO() {
   throw new UnsupportedOperationException(
    "Haven't written this bit";
   );
 }
}

as you can see, the argument c of fillinImportance is declare to be both an enum and a Lookup. Our code freely uses code specific to Enum types: allOf(), name(), and also code specific to Lookup types: setImportance().

The important thing is: it’s all type-safe. Aside from the declaration itself, the code looks simple and everything does what it’s supposed to do.


Patterns, Java Generics, and locking together N parameterised types

March 21, 2010

Java generics are for patterns – meta-classes. The most obvious example is the collections interfaces. In some patterns it’s necessary to lock together mutually dependent classes that do not have in inheritance hierarchy. This can be done in Java, no worries. As with all java generics: the declarations are hideous, but once you do them the classes you derive look great and the code writes itself. Literally, if your IDE does auto-completion.

Over at agency X, we had a database in which we wanted to journal pretty much every table. As a result, we produced a whole stack of classes in pairs: Person/PersonVersion, Address/AddressVersion, (umm…) Breakfast/BreakfastVersion and so on. This is a pattern – it’s a common thingy that is meta beyond inheritance. We want to achieve a couple of things here. There should be a pair of common superclasses Versionable and Version, containing useful functionality. If I have a Versionable object, I want to be able to ask it “what is your latest version”, or “what version of you was current at timestamp“? If I have a Version object, I want to be able to ask “What Versionable are you a version of”? And I want these things to be typesafe.

Now, this seems pretty straightforward, so let’s start coding:

class Versionable<VERSION extends …

Ah. A snag. Person needs to be the Versionable of PersonVersion, and Address the Versionable of AddressVersion. We would want to say something like:

class Person extends Versionable<PersonVersion> { …; }
class PersonVersion extends Version<Person> { …; }
class Address extends Versionable<AddressVersion> { …; }
class AddressVersion extends Version<Address> { …; }

But how to we do the declaration of the generic type? Well, to fit the code above, we could go:

class Versionable<T extends Version>  { …; }
class Version<T extends Versionable>  { …; }

But that won’t do, because there are implied arguments there:

class Versionable<T extends Version<?>>  { …; }
class Version<T extends Versionable<?>>  { …; }

Those question-marks tell us what we are missing. We need to declare not only that Versionables are always associated with Versions, but that the Versions they are associated with are Versions of the Versionable you are declaring.

If that makes sense.

To fix this, the generic declaration needs to include both types: each type refers to its partner and also to itself, using that class Foo<T extends Foo<T>> reflexive back-hook construct. It’s weird, but it can only ever be set to “the class where this parameter gets bound”. You can leave it unbound, but if tyou bind it then it must be “self”.

abstract class Versionable<
  T extends Versionable<T, V>,
  V extends Version<T, V>> {
 protected Map<Date, V> versions = null;
 public V getCurrent() { … }
 public V getCurrent(Date timestamp) { … }
 protected abstract V newVersion();
}

abstract class Version<
  T extends Versionable<T, V>,
  V extends Version<T, V>> {
 protected T base;
 public Version(T base) {this.base=base;}
 public T getBase() {return base;}
 public abstract boolean isPrettyMuchSameAs(V compareTo);
}

Each of them is declared as depending on itself and the other, simultaneously. I like to keep the sequence of parameters and their names identical – it reduces confusion. The point of the exercise is that you can now declare mutually interdependent classes:

class Breakfast extends Versionable<Breakfast, BreakfastVersion> { … }
class BreakfastVersion extends Version<Breakfast, BreakfastVersion> { … }

and so on. This means that BreakfastVersion.getBase() doesn’t simply return an unknown Versionable, or some Versionable known to have Versions that are of type BreakfastVersion, but it specifically returns a Breakfast object, and vice-versa. Thus, you can ask:

BreakfastVersion foo;
if(foo.isPrettyMuchSameAs(foo.getBase().getCurrent()) {…}

And have it all done in a type-safe way. It’s pretty obvious how this extends to N mutually interdependent classes. At our current site, we even have some funky stuff where something like this is subclassed fairly deeply, and one branch terminates before the other. This can be done, too. Let’s say you have two quite different types of breakfasts: Meat and Veg, but their Version objects are the same and you’d like to use the same class implementation for both.

abstract class Breakfast<T extends Breakfast<T>>
  extends Versionable<T, BreakfastVersion<T>> {
 public BreakfastVersion<T> newVersion() {
  return new BreakfastVersion<T>((T)this);
 }
}

class BreakfastVersion<T extends Breakfast<T>>
  extends Version<T, BreakfastVersion<T>> {
 public BreakfastVersion(T breakfast) { super(breakfast); }
 public boolean isPrettyMuchSameAs(
  BreakfastVersion<T> compareTo) { … }
}

class BreakfastMeat
 extends Breakfast<BreakfastMeat> { … }

class BreakfastVeg
 extends Breakfast<BreakfastVeg> { … }

Note how BreakfastMeat and BreakfastVeg are unparameterised classes, but the the generic class that serves as a version for each is parameterised with the kind of breakfast that it is a version of. We dont bother with subclasses for it, which means that it is always paramterised wherever it appears – but that’s ok. The whole thing is typesafe, and adding new kinds of breakfasts sharing the generic version class is straightforward. Heck – you can even subclass the version class if you want.