I was going to get coffee today at work, minding my own business, when someone from the test-team asked me if the order I was doing things when preparing coffee was intentional. Absentmindedly, I explained the reasoning behind the order of things and how I reached this way of doing things and belatedly realized that I may have gone too far in my explanation – I think it was the look of pity in his eyes that clued me in.

To explain, first you need to understand what our kitchenette looks like and the various steps in making coffee:

Here are the various things we are seeing here:

1) Access – that’s where I typically come to the kitchenette from.
2) The coffee machine
3) Counter
4) Cups
5) Lids
6) Fridge (Where milk is).

Our coffee machines basically give you an Americano – no milk. The way I take my cup’o’joe is to do 12 oz of machine generated coffee (into a 16 oz cup) and fill another 2-3 oz of milk – and then the  cup needs to be lidded as well. Of course, there are a number of variations on how to make such a coffee with this layout.

Making Coffee – the naive way:

Step 1: Go to position (4) – grab a cup.
Step 2: Go to position (1) – place cup at machine.
Step 3: Press buttons - Wait for coffee to be made.
Step 4: Take milk from fridge (6)
Step 5: Fill cup with milk (possibly at position (3))
Step 6: Discard milk carton or, if still full, place back in fridge.
Step 7: Go to (5) and grab a lid.
Step 8: Place lid on cup.

And we are done. To understand how this can be optimized we first need to figure out how much each part of the coffee making process takes:

Making coffee (the machine phase): ~2 minutes (constant).
Getting milk (from position (1)): On average, takes about 20 seconds. Depending on traffic, can easily take as long as 1:00 minutes if there is a lot of traffic and even longer if you consider the possibility of people talking to you while you are making the coffee.
Getting a cup: Usually takes about 5 seconds from position 1 – can take longer due to traffic and chat. Rarely takes more than 30 seconds and requires little concentration.
Filling cup with milk: Takes about 5 secodns.
Discarding/Returning milk: Takes about 10 seconds. Worst case (traffic etc) can take up to a minute.
Grabbing a lid: 5 seconds from position (1).
Lidding the cup: 5 seconds at position (3).

So.. Translating this into pseudo code, this is what we get:

function NaiveCoffeeMaking()
{
WalkTo(4);
GetCup(); // 10s
WalkTo(2);
PlaceCupInMachine(); // 1s
MakeCoffee(); // 120s
GrabCupFromMachine(); // 1s
WalkTo(6);
GetMilk(); // 20s
PourMilk(); // 5s
WalkTo(5);
GrabLid(); // 5s (probably closer to 3s in this case)
WalkTo(3);
LidCup(); // 5s
}

Phew.. Okay.. So we have that. Now lets calculate how much time this takes (best case):177 seconds!

The thing to consider though is that the machine phase can be asynchronous – that is to say – while the machine is making coffee, the CPU (me) is waiting Idle. The question is, how can we use that to optimize the time? For our pseudo code then, we will now separate MakeCoffee into two functions: BeginMakeCoffee() which essentially means pressing the buttons on the machine and immediately return to the caller and EndMakeCoffee() which completes the operation (and if not done, blocks until done). And so, the most optimized version of how to make coffee is:

function FullyOptimizedCoffeeMaking()
{
WalkTo(2);
BeginMakeCoffee(); // 120s – but returns immediately
WalkTo(4);
GrabCup(); // 5s
WalkTo(6);
GetMilk(); // 20s
PourMilk(); // 5s
WalkTo(5);
GrabLid(); // 5s (probably closer to 3s in this case)
WalkTo(2);
PlaceCupInMachine();
EndMakeCoffee();
LidCup(); // 5s
}

Notice that when we call BeginMakeCoffee(), we immediately return and continue processing – going through the phases of getting the milk, preparing the cup and only then, when done, placing it in the machine. So, in this case, best case time would be: 125 seconds. That’s 120 seconds that it takes to make the coffee plus the 5 that it takes to lid the cup. The rest of the time is taken up in parallel to making the coffee.

But there’s a problem! BeginMakeCoffee() and EndMakeCoffee() do not work exactly like a machine async operation. Generally speaking, when you issue an async operation, the sub-system will take care to store the result for you when it’s done and wait patiently for you to call the second part of the operation (EndMakeCoffee) before it returns the result. A coffee machine does not work that way. When the coffee is ready, it’s coming out – whether there’s something to store it or not. That presents some problems for the FullyOptimizedCoffeeMaking() function! What happens if instead of talking about Best case, we were to talk about worst case. The GetCup() can sometimes take 30 seconds. GetMilk can sometimes take 120 seconds. As well as some of the other things that make take longer under high-stress cases. What happens then? Well, what happens is that the coffee starts pouring and there’s nowhere for it to go, so it gets wasted. Sacrilege!!

In essence, we need something that’s both optimized AND safe. Since life does not have convenient temporary memory (where the coffee would have been stored) or sync objects (where the act of pouring the coffee could have been locked and deferred until a cup is to be placed underneath the nozzle), it means we need to work around those limitations:

function OptimizedAndSafeCoffeeMaking()
{
WalkTo(2);
BeginMakeCoffee(); // 120s – but returns immediately
WalkTo(4);
GrabCup(); // 5s
WalkTo(2);
PlaceCupInMachine();
WalkTo(6);
GetMilk(); // 20s
WalkTo(2);
PourMilk(); // While cup is in the machine – 10s
WalkTo(6)