Lessons from the Sub Shop (or Why Your Computer is Slow)

I was buying another sub the other day and found myself in the middle of a classic computer science problem. OK, I see you’ve mentally (and perhaps physically) recoiled at this topic already. But bear with me for a minute. This is light stuff.

There were three customers in line and one lonely sub artist working. There are three tasks to sub-making at this sub chain:

1. cutting bread and adding cheese;
2. adding toppings; and
3. taking money.

At busier times there are three people performing these three tasks. When there is only one person, switching between tasks has a cost:

• After cutting bread, you have to put the knife down (humour me, OK?).
• After putting on toppings, you have to take off your plastic gloves.
• After taking money, you have to wash your hands and put on new plastic gloves.

So with three customers in line, our sub dude has two choices. He can a) perform all three tasks for one customer at a time or b) he can cut everyone’s bread then put on everyone’s toppings then take everyone’s money.

Obviously the best choice for customer 1 is for all three tasks for his sub to get performed first. But that will introduce context switching which will increase the total amount of time it takes to prepare all three subs, which is the worst case scenario for the last customer.

Actually, the worst case for customer 3 is that Sub Dude gets bored and quits before he makes the last sub. But I digress…

Let’s assume the following times for tasks:

• 15s – Cutting bread
• 1s – Putting down knife
• 30s – Adding toppings
• 5s – Taking off gloves
• 30s – Taking money
• 30s – Washing hands and putting on new gloves

If Sub Dude completes each customer order completely before starting the next, the times look like this:

• Customer 1: 15s + 1s + 30s + 5s + 30s = 81 seconds to get sub
• Customer 2: 30s + 15s + 1s + 30s + 5s + 30s = 111 seconds to prepare sub = 192 seconds to get sub
• Customer 3: 30s + 15s + 1s + 30s + 5s + 30s = 111 seconds to prepare sub = 303 seconds to get sub

If Sub Dude does the same task for each customer before moving to the next task, it looks like this:

• Bread cutting: 15s + 15s + 15s + 1s (put down knife) = 46s
• Adding toppings: 30s + 30s + 30s + 5s (take off gloves) = 95s
• Taking money: 30s + 30s + 30s + 30s (wash hands) = 120s

In the second case, the total time is 261 seconds. Customer #1 gets his sub at 171 seconds. Customer #2 gets his sub at 201 seconds. Customer #3 gets her sub at 231 seconds. Customer #1 ends up waiting a lot more, customer #2 waits a bit more, and customer #3 waits a lot less. And the total time to completion is less.

So, what should Sub Dude have done the other day? Well, that depends on your priorities, doesn’t it? In this case, Sub Dude chose option b. I was customer #2 so I had to wait a bit longer and it bugged me just a tiny bit. But it looked like the extra wait time really bugged customer #1. Customer #1 had no interest in the total completion time being optimized. For customer #1, his priority was the completion time of only his sub, which was not optimized. In fact he was penalized for being first in line.

In computer science, this is a scheduling problem. Your computer has a bunch of things to do and switching between things adds overhead. If too much time is given to one task, other tasks get starved (that is, they don’t get anything done). But if the computer switches between tasks too often, the cost of context switching means less real work gets done. So the next time your cursing because Word seems to be slow while you’re listening to MP3s and compiling code and editing a video, just remember that your computer is frantically jumping between each program to make sure they can all get some work done. If the computer gave a really long chunk of time to Word, your MP3 would stop playing.

OK, wow, I’m not sure anyone will care about this post. If you made it to this last paragraph, thank you and congratulations. You have learned a tiny bit about computer science. Bet you weren’t expecting to do that today.