Forking around the christmas tree

Some time ago, I heardread about the Fork/Join-framework, coming with Java 7.

The basic concept is pretty easy, and quickly understood:
If you have a large task, split it, and give the parts to different threads/processors to better utilize your hardware (Hey, there are even low-end smartphones with dualcores, nowadays).

While the concept is pretty easy, there are few good examples. Some of the examples are even labeled as bad examples by the author. Others are so complex, you can't see the important parts.

That's why I didn't dig into it, until recently. I will try to show you a simple example with a little story:

A Heavily Loaded Christmas Tree

We have bought a christmas tree with a lot of branches. Of course, every branch needs to be decorated with ornaments. Luckily we got some elves to do the work.
The ornaments are heavy, so our little elves can't carry more than one ornament from the storage room to the tree.

Lets do this with a single elf:

public drapeTree(){
  drapeBranch(trunk);
}

public void drapeBranch(Branch branch){
  Ornament o = getOrnamentFromStorage();
  branch.drape(o);
  for(Branch subBranch : branch.getSubBranches()){
    drapeBranch(subBranch);
  }
}

poor little elf, 200 branches takes a lot of time to drape.

Organizing Elves

Int-elves usually come in groups of 2,4 or 8. But there are even elves (so called Advanced Micro Elves) that comes in groups of 3 or 6. Other elves are much smaller but are seen in huge groups.

A simple model to organise elves, would be, to split the job and assign every elf of the group the same amount of branches to drape. In an ideal world, all elves would be finished at the same time.
But some ornaments are broken and have to be repaired before draping them to the branch. Others need to be polished. This takes longer, so some elves are faster than others.
Another problem is, that we need to check before, how much elves belong to the group, so we can split the work accordingly.

Self Organizing Elves

Luckily our elves are intelligent enough to organize themself. Just give them tasks todo:

class DrapeTask extends RecursiveAction{
  Branch branch
  DrapeTask(Branch branch) {
    this.branch = branch;
  }  

  protected void compute(){
    Ornament o = getOrnamentFromStorage();
    branch.drape(o);
    for(Branch subBranch : branch.getSubBranches()){
      new DrapeTask(subBranch).fork();
    }
  }

}

ForkJoinPool elfGroup = new ForkJoinPool(); 

public drapeTree(){
  elfGroup.invoke(new DrapeTask(trunk));
}

Now the first of the elves start to drape the trunk with a tree-topper. On his way back, he notes all branches from the trunk and creates tasks from it. Now, every elf in the group is going to get a task with a dedicated branch. Every time the elves return from a branch, they return with tasks for the subbranches of this branch. Usually, the elves will work on the branch and all of its subbranches. If one elves finishes all his tasks faster than the others, he will look up the remaining tasks of the other elves and "steal" some of them.

Meanwhile At The North Pole

Santa Claus watches his elves closely. He notices that the tasks have to be a specific size. If they are too small, his elves have to do more organization (writing tasks, etc.) than actual work. If the tasks are too big, the work isn't well balanced in the group.

There's some deeper stuff (sorry, no elves here) on the heise site.