Kitchen Remodeling as Computation

I once had an opportunity to observe a kitchen remodel from start to finish, interacting with the general contractor who was heading up the remodel along the way.  And I must say, if you consider yourself to be a competent contractor or handyman and are looking for a career change, all I can say is...consider computer science.

In my limited sample of one well-executed kitchen remodel, I submit that the knowledge and skill set that makes one excel in managing a kitchen remodel are not so different from those required to excel in computer science.  While the generated artifacts are different — cabinets, plumbing, and countertops as opposed to applications, data structures, and algorithms — the thought processes and mindsets toward making high-quality versions of these artifacts are very similar in the two endeavors.  Heck, the term “architecture” is meaningful, and even congruent, in both areas.  That’s got to count for something, right?

As the contractor walked me through what he was doing — start with setting appliances aside, demolish the old kitchen, go on to rough electrical and plumbing, mount the cabinets, [almost] finish the electrical (but not the plumbing), measure out the countertops, paint the area, install the countertops, install the sink, reinstall appliances (or install new ones), and finally finish electrical and plumbing, all with periodic cleanup at appropriate in-between periods — I found that everything made sense, and fell into place in much the same way that variables, subroutines, objects, and modules connect and build upon each other to form useful (and reusable) software.  Indeed, as he explained what was going on (and why), I found that he was using many of the same concepts that computer scientists use in designing, studying, and choosing among algorithms:

• Priorities: “We need to relocate the refrigerator first so that food storage is disrupted for the least amount of time.”


• Pre- and post-conditions: “I can’t start the cabinets until we’ve settled the rough electrical and plumbing, since the cabinets might get in the way.”  “The cabinets aren’t right until they’re completely plumb and level from end to end.”


• Fault tolerance: “It doesn’t make sense to order the countertops until the cabinets are completely laid out — that’s the only time that we’ll know the exact dimensions of the counter surface, since all kinds of adjustments and tweaks might happen during installation.”


• Scheduling/load balancing/optimization: “There’s no rush to pick out the sink or install the glass panes in the cabinet doors, since you can do that while everything else is going on with plenty of time to spare.”


• Efficiency: “If we cut the cabinet skin in this way, we’ll be able to use more of it to cover off these areas, with the fewest gaps.”


• Tradeoffs: “I can make that adjustment if you’d like, but it will delay this next step and cost a little more money.”


• Side effects: “While we can move the refrigerator, we can’t move the valve that feeds the ice maker. So we’ll need to shift these cabinets a little so that they can accommodate a connector between the fridge and the valve.“


• Constraints: “The countertop can only go this far through the kitchen pass-through, because the material won’t be strong enough to support itself past that.”

The list goes on — and every step of the way, I saw what was going on and why, and even though one might wish that things would go faster, or that some decisions were easier, I couldn’t help but appreciate how the big picture, and all of the factors involved, really compelled the work to proceed in a certain way.  The contractor might even have been slightly surprised at my demeanor, as he started telling me horror stories of how other jobs got derailed due to unreasonable demands or fickle decision-making.

In the end, it came down to one thing — we were thinking about the task and its components in very much the same way.  Thus, a good contractor would make a good computer scientist.  And, if a computer scientist somehow learned to deal with a nail gun, circular saw, and plumber’s dope, then that computer scientist might make a good contractor!  :)

Let’s take it a step further, in fact — for what endeavors or fields would considerations like those listed above (and numerous others from the computer science realm) not be useful at all?  Of course, I may be biased, but I think one can make a pretty strong case that almost every facet of the human experience would benefit from some kind of computational proficiency — and I mean “computational” in the general computer science sense, not just the numeric manipulation that most folks would associate with the term.  In the end, wasn’t the contractor really “computing” a new kitchen, based on the “input” provided by the homeowner?

A music professor once told me that a quality shared by all good music, regardless of genre, was that it was “logically compelling.”  He didn’t mean that good music was mechanical or overly structured; he meant that good music always seems like it must go to a particular place, and no other destination seems like it would do.  This is what makes pop songs “catchy,” and what gives arrangements an excellent “hook” — when you hear them, the sounds and silences that come before seem destined only to lead to the sounds and silences that come after; anything else would be wrong, or else just not-as-great.

The notion of “logically compelling” certainly resonates with me regarding good software design, both internal (the code’s structure) and external (the user interface).  On both counts, high-quality designs “compel” that code be written in a certain way or that a user’s intuition match what a user interface presents — all because factors such as priorities, pre- and post-conditions, fault tolerance, optimization, tradeoffs, constraints, and other core elements of computation are brought to bear upon a situation.

And now, after observing a kitchen remodel up close, I would say that a well-executed kitchen remodel is also “logically compelling.”  Indeed, if everybody knew a little computer science, how many more day-to-day human activities would share that property — a sensible result due to sensible decisions made based on sensible reasons, with sensible (and acceptable) compromises.  Would you trade some extra time and resources off for that mid-life adjustment?  Or better yet, start ’em young.  After all, I don’t know of anyone who doesn’t appreciate a brand-spanking-new kitchen.  :)

That Drowning Feeling

I once had a friend who fretted mightily about an upcoming party.  She had that deer-in-the-headlights look to her — simultaneously distracted yet fixated.  Upon some inquiry, I found out that the issue in question was the food: how much of it to order.  She bounced around about being worried that there wouldn’t be enough food, but such and such people haven’t RSVPed, plus these other people have a tendency to bring a bunch of other folk along, plus if there were too much, what would she do with it, does that mean she’ll need to get some boxes so people can take the excess home, but then she might order too little food…

This has happened to all of us at one time or other: we are faced with a situation that has a lot of unknowns, a variety of factors to consider (sometimes contradictory), and no apparent resolution.  Fortunately, we frequently don’t need to face these situations alone, and in this case, it was my turn to keep someone company.

Having (mostly) understood the problem at hand, I tried to get a few things straight.  First, I asked my friend how much food would be viewed as “enough” food for the guests.  She had a ready answer — for the kids at the party, she would want them to eat a certain amount; for the adults, a little bit more.  Memory of precise values and items escapes me, but the answer was definite and clear, something like “1 piece of pizza for the kids, and 2 pieces of pizza plus 3 buffalo wings for the adults.”

Little did my friend know that she had almost solved half of her problem for me.  I then asked how many people she expected.  A little bit of the fluster bluster came back, but, once focused on just a head count and not all of the implications of such a head count, she also had a fairly ready answer — “Well, I invited 30 people, but only 20 have RSVPed, and some guests might bring others along.”

Some uncertainties there, for sure, but before I pursued the head count further, I asked my friend, “What’s more important to you — that there’s too much food left over, or that there’s too little?”

Confusion city started looming again, but once more, I found my friend actually continuing to solve more of the problem on her own.  “Well,” she said, “I really want to have the right amount of food...but in the end, I wouldn’t know what to do with too many leftovers, and if the food looks like it’s getting low, I can always run out and get some easy ready-made stuff.  But if I can avoid that, that would be great.”

Which returned me to head count — I asked around how many “surprise” guests might show up, and she listed the invitees who have, in the past, brought in some freeloaders — uh, crashers — uh, no, um, extra mouths to feed.  For each invitee, she found that she had some idea of, at worst case, how many unsolicited additions might pop up.  In the end, we had a number — by no means a surefire one, of course, but still a guesstimate that sounded reasonable.

“Now,” I concluded, “with that fair guess of how many kids and adults might show, let's just multiply that by how much food you’d like them to eat, and that’s how much you should order.  If that amount goes over, then it probably won’t be way over; if it goes under, then either it won’t be too bad of a shortage, and like you said, if you were really in a bind, you can always get some more food.”

That seemed to settle things.  My friend calmed down, settled on a quantity of food, and finally started to actually look forward to this party which had been causing her so much grief.  There was a final, lingering doubt — “So you think that will really be enough?” — but she seemed to replay our backups and contingencies and priorities in her mind, and squashed that question once and for all.

Of course, at this point, you may be wondering, “Now where is the computer science in all of this?”  Looking back, I would say that the entire food-amount-determination episode comprised the computer science.  Assessing a situation, looking at its positives and negatives, specifying priorities, and finally coming up with a plan that maximized the positives while handling or accepting possible negatives, is, in some respects, precisely what computer scientists do for a living.  This cycle happens all the time, particularly with algorithms: there is almost always more than one way to approach a particular computation.  Each alternative has its own set of advantages and disadvantages; for many problems, there is no clear winner.  When deciding how to allocate files on a disk, one may favor the simplicity of contiguous allocation but realize that frequent changes to files on disk may eventually lead to external fragmentation.  Thus, other approaches that are more amenable to change (linked lists, indices) should be considered.

And yet, we must realize that the very notion of “frequent changes” is an assumption in this scenario — and sometimes, this assumption will not hold, such as with DVDs or other non-writable media.  In this case, perhaps contiguous allocation’s benefits then outweigh its detriments, precisely because our needs or priorities have changed.

In another area of computer science, computer graphics, lies the search for hidden surface removal algorithms.  A variety of approaches were devised and tested, each having different pluses and minuses when compared against each other.  The approach that proved to be the most general, with the best performance over a wide variety of situations, was the depth- or z-buffer algorithm.  It had one caveat, however: it used a lot of memory, possibly more memory than the visible graphics display itself.  Depth-buffer effectively “trades off” space in exchange for time — something that happens in many algorithms.

As you may have guessed, depth-buffer may have been prohibitive at first, but as memory became cheaper and more available in larger and larger amounts, depth-buffer’s “disadvantage” was finally rendered moot.  Today, kids bring around devices that use the depth-buffer.

Thus, like my friend and her food-at-a-party conundrum, computer scientists are frequently faced with unknowns and no clear-cut choices; unlike my friend, we are actually trained to tackle these situations in toto, so that we can determine not necessarily the absolute best solution, but the best solution under the current circumstances.  We are trained to be explicitly aware of these circumstances, as well, because one day, those circumstances may change, and all of a sudden another alternative may become preferable.

In the end, I’m left asking, if everyone knew a little more computer science, how many “deer-in-the-headlight” situations might actually be avoided?  How many people, mired in apparently insurmountable problems, might actually find a way through?  While there will certainly be challenges of genuine difficulty, one wonders how things might change if more of us could “swim” with the computer scientists, and thus not drown in every problem that isn’t blatantly cut and dried.

When 1 + 1 < 2

Today's hectic, frenetic world has carved out a Special Place for the almighty “multitasker” — the master of the modern world, armed with a Blackberry or Palm or iPhone or whatever other Smart Thing gets everyone hot and bothered about being “productive.”  This multitasker can send texts, perform Google searches, take kids to soccer practice, and close face-to-face deals while making dinner reservations and dictating letters to a secretary...all at once!!!  Indeed, sometimes it seems as if society has been transformed in the multitasker’s image, stacking the odds for a successful and satisfactory life so that they heavily (and perhaps unfairly?) favor those among us who can divide the work that we do into 24-second shot clock sprints.

I’ve had my own personal encounters with this multitaskalomania.  A prior supervisor once advised me to structure my time in just such a multitasker mode, “in order to succeed.”  To manage the 7–10 really important things that my job entailed every day (supervisor’s emphasis, not mine), I was told to allocate roughly an hour on each task, no more and no less.  Need to do some reading and make some phone calls?  Give myself an hour to read, then stop and pick up the phone.  Stop talking after an hour — no matter what — then check in on some of the folks on my team.  Then eat, then work on that proposal, then work on that paper, then attend this meeting, then write some code — for just an hour! — then finally write more code, but of the recreational type, so that I can “keep on pushing the envelope.”

Indeed, said supervisor seemed to take this advice to heart as well — no hypocrisy here, at the very least.  Every day was a whirlwind of activity...a whirlwind that was so nearly literal that he earned the nickname “Tasmanian Devil.”  In order to succeed, I also had to become Taz-like — move forward, a little bit, on a bunch of things everyday, papers a-flying, arms a-flailing, task chair a-spinning.  Otherwise, I would fall behind, as irrevocably as a lost hour of sleep, outplayed and outlasted by those who were better suited to career survival.

If, upon reading this far, you find yourself doing the Tiger Woods elbow jab saying “Yes!  That’s the way to do it!” then good for you — you may well have that Darwinian edge which will ensure your descendants’ survival into the cockroach era.  But, if you’ve been reading this going, “Yes, that’s what I’ve been told to do before, but I never felt too comfortable with it and prefer to work on fewer things — preferably one — in a single day,” then you may have some computer scientist in you.

For, as computer scientists know — especially those who specialize in operating systems and concurrent programming — multitasking has a cost.  And, if we aren’t careful, we can easily end up spending more time juggling jobs than whipping up work.

Not surprisingly, the cost of human multitasking is most concrete when looking at computer multitasking.  Most modern computers have more work (processes) going on at once that they have brains (processors) — yes, even in this day and age of multicore processors.  Thus, they are a lot like us — they need to divide their time and “attention” among multiple tasks.

One of the primary tasks of a computer’s operating system is the scheduling of these tasks.  One such scheduling approach, called round robin, is used by systems that need to be “interactive” (in other words, systems that make sure their users don’t feel ignored).  Round robin scheduling is not unlike my aforementioned supervisor’s work style: do a little bit here, then stop.  Then a little bit there, then stop.  The more “little bits” you do, the better.

Every time an operating system makes a computer go from one task to another (round robin scheduling or otherwise), it undergoes a process called a context switch.  Transferring a computer’s attention from one program to another entails a certain amount of bookkeeping: taking note of where the computer left off in the previous program, keeping track of the values used by the previous program and the values that will be used by the next, etc.  The catch is, while the work done during a context switch is critical to proper operation, this work is outside the actual work that needs to be done — that is, the work being done by the programs running on a computer.  Because of this property, a context switch is viewed as overhead — something that takes up time and resources, but isn’t the actual “thing” that we want to do.

The big gotcha with context switches and round robin scheduling lies in the round robin quantum — that is, the amount of time to give each process before moving to the next one.  The quantum has to be small enough to make the overall computer feel like it’s doing a bunch of things at once — sort of in the same way that the individual frames of a movie fly by fast enough for our eye to perceive smooth movement.  But, as you switch tasks, you incur the overhead of a context switch, which, no matter how you cut it, will take some amount of time — and thus, if your quantum is small enough, you’ll end up spending more time doing context switches than you do with actual work!

So it is with daily life.  Like computers, we undergo a form of “context switch” when we shift from one task to another.  Ever feel light headed after trying to work on a project but getting interrupted frequently by a phone call?  That’s the toll of too many context switches.

Tom DeMarco and Tony Lister, the authors of Peopleware, use different terms for the same idea: when people are working on some task, they get into what DeMarco and Lister call flow.  Flow is a kind of “work continuum,” a “groove” of sorts, where thoughts are flowing, muscles are coordinating, and production moves along smoothly.  When flow is broken — either by phone calls, people stopping by your office, or changing to another task — then we need some time to get back “into” the flow of the original task.  This is analogous to a computer’s context switching — it’s overhead.  Something that takes time to accomplish, but isn’t part of what we actually want to accomplish.  Bottom line: the more you break the flow (rotate tasks every hour!  or even less if you can handle it!), the less work you will actually get done within the same amount of time.  Or, 1 + 1 turns out to be less than 2.  When you can, don’t juggle — take a task, get it done completely, and move on.  When you can’t avoid juggling, try to spend as much time on something before switching.  The time you spend now will come back to you in the long run.

Learning to Let “Goto”

Have you ever had a conversation like this before:

“So, how do I get from my office to the restaurant?”

“Well, you take the 10 freeway and go east. Then when you hit the 405 interchange, head north.”

“Head north. So stay on the left lane on the off-ramp?”

“No, actually, the right lane.”

“The right lane??? No way. You’re going east on the 10 and so if you want to go north, you’ll have to be on the left.”

“No, the right lane of the off-ramp goes north.”

“That’s impossible. North is on your left when you're going east.”

...and so on. While a conversation such as this might not necessarily have earth-shaking consequences — at worst, this insistent instructee may have to turn around and lose some travel time — it does reflect yet another situation that may be different if more of us knew a little bit more about computer science.

Some may be surprised to realize that the central object of study in computer science is not the computer. On the contrary, the computer is merely a tool for creating, studying, and making use of the real star of computer science: the algorithm.

While there are many formal definitions for an algorithm, in keeping with the “daily life” tone of this blog, let’s stay relatively informal: in essence, an algorithm is a set of instructions. It’s a “how-to,” a “1-2-3,” a “step-by-step guide.” And yes, to borrow yet another catch phrase, in many respects an algorithm is meant “for dummies.”

No, this doesn’t mean computer scientists are dummies — it means that computers are. The “dummy” aspect of algorithms lies not in their discovery, definition, or creation — that‘s squarely in the realm of computer science, and certainly not for “dummies” — but in their execution. An algorithm should include all of the information necessary in order to complete it successfully — no more, no less. And this is why computers are the ideal “algorithm executives” — they rely completely on the information provided by the algorithm, and nothing else. No questions asked. If an algorithm’s instructions will make a computer “freeze,” then the computer will “freeze.” If these instructions will make a computer produce a convincing facsimile of Angelina Jolie playing Grendel’s mother, then that’s exactly what you get.

In other words, computers follow instructions, and the information provided within those instructions, without injecting (or needing) any other information. There is no “insight,” or “intuition,” or “experience,” or “understanding” involved. The bottom line: much as we tend to anthropomorphize computers, they actually operate in a manner that is almost contrary to how we do. One can argue that the previous four concepts — insight, intuition, experience, and understanding — are fundamental to being “human.” And yet, they have nothing to do with the amazing things that computers can accomplish; in fact, they may even get in the way.

Which brings us back to the conversation above: the driving directions being given in that conversation can be viewed as constituting an algorithm — an algorithm for traveling from one’s office to some restaurant. The recipient of this algorithm, however, is a living, breathing human being...who appears to know better. Indeed, prior experience and an understanding of directions does make these directions seem incorrect: north is to your left when you’re going east. So of course it would be the left lane of an offramp that would head north.

Right?

There are two ways to go here: first, one can be “more human” and state that no, the person receiving directions does not actually have enough understanding nor experience. Sometimes, offramps do turn in opposing directions — it just depends on how the roads were built. So it is possible to head north by staying on the right lane on an eastbound offramp.

But wait — the would-be restaurant guest was already being told to stay on the right lane in order to head north on the 405. The issue was that, because said guest had “understanding,” “experience,” and “insight,” he or she was doubting the instructions being given. This guest is human, after all. Had these instructions been given to a computer, then no questions would have been asked, and the computer would have arrived at the restaurant sooner than the human.

Now that you’ve come this far, you might think that this entry is some sort of invective against that which makes us human — if this were The Matrix, I’d be rooting for Agent Smith, or if this were Terminator, I’d be squarely on Arnold’s side. And why not — I’m a computer scientist after all, right?

On the contrary, this entry is actually all about the perks of being human: we have a choice. We can choose to invoke our insight, understanding, and experience...and, when the situation is right, we can also choose not to do so. In the case of the dogged dinnergoer, he or she probably should have recognized that the directions’ provider was authoritative, and his or her instructions should simply be followed. There will be other times to invoke one’s sense of direction or navigation; this probably was not one of them.

With this perspective, you can probably think of some other times when it’s better to just put our “computer faces” on and follow instructions. Even without inborn culinary aptitude, one can probably whip up a decent meal as long as he or she sticks to a good recipe (and executes its instructions correctly). I’m also sure that teachers everywhere have, at one time or another, asked their students to “just please follow the instructions.“ And how many times have negative consequences, ranging from the comic to the tragic, emerged due to a failure to “use as directed?”

A little computer science provides the perspective and the skill set to discern when to invoke our human gifts (i.e., develop the algorithm) and when to simply let go, and follow instructions (i.e., perform the algorithm). There are right and wrong times to behave one way or the other, and for the moment, only a fully-realized human can compute that correctly.

Cafeteria Conundrum

Here’s a fun “riddle me this, Batman” scenario: Why does it take, on average, less time to get a burger/hotdog/chicken sandwich from the school cafeteria’s in-house grill during peak hours than during off-hours, when there are easily 5–10 times more people waiting?

Consider the Riddler defeated if you answered “Because there are more people working the grill.” Consider yourself a computer scientist if you aren’t put off by the apparently blatant common sense behind this answer. In case you haven’t already noticed, the explanation behind many “common sense” premises turns out to be computational sense, and this scenario is no exception.

It turns out that the seemingly obvious notion that more workers results in more work getting done has a few gotchas. “More workers” in computer science is typically associated with parallelism, and the one of the biggest gotchas in parallelism is Amdahl’s law, which is named after computer architect Gene Amdahl.

Simply put, Amdahl’s law states that the speedup gained from increased parallelism (i.e., adding more workers) is limited by the amount of work that can actually be parallelized. For example, having two people at the french fries station won’t churn out french fries twice as quickly, since that vat of oil doesn’t really work faster if two people are watching it. Instead, what you want is to increase the number of french-fry vats, and you get the near-ironic result that a single person suddenly churns out french fries twice as quickly.

Note how Amdahl’s law isn’t doesn’t necessarily rain on the parallelism parade — it just cautions us to make good decisions regarding when parallelism pays off. And in the case of a fixed cafeteria grill setup, the “parallelism” that brings about genuine speedup lies in additional equipment, and not additional workers.

So if parallelism isn’t truly the answer behind our grill’s peak-hour productivity, then what is? Another possible answer also comes from computer architecture’s bag of tricks: pipelines.

In a computing pipeline, a particular task is broken up into distinct stages. If each stage can be performed by a different working unit, then multiple tasks of the same type can overlap, meaning that such tasks can finish at a faster rate than if the work were performed in strict sequence.

When you think about it, a grill’s tasks, which include preparing burgers, hot dogs, chicken strips, french fries, and the like, can fit the pipeline model. A burger, for example, requires the following stages:

1. Cook the meat
2. Assemble the sandwich (bun, fixings, etc.)
3. Wrap the sandwich

If you break the grill’s personnel up into a meat cooker, sandwich assembler, and sandwich wrapper, then you can potentially churn out hamburger sandwiches at a perceived rate of three times faster than with a single person doing all three jobs in sequence.

Note how we said perceived rate. In the end, it still takes the same amount of time to make a single hamburger, pipeline or not. The trick lies in overlapping the work that’s being done on multiple hamburgers (or other grill products). Which leaves one last issue to address, if you’re a stickler for details: why did the riddle say that it takes less time to get a sandwich at peak hours, when pipelining doesn’t really change the amount of time it takes to produce an individual sandwich?

Again, the answer may reek of “plain old” common sense — “less time” in this case is less time as perceived by the person waiting for the food. With more people behind the grill, and thus more overlapping stages in the pipeline, the time from order to food becomes less and less dependent on the number of orders that came before me. The “time-to-food” includes less waiting time: having a well-populated pipeline makes it seem more and more like the folks at the grill have only me as their customer.

One last real-world detail from this analysis: you might then think that a totally empty grill — i.e., a grill where I’m the only customer — will produce a sandwich just as quickly as the pipelined, peak-hour grill. While this might be true in general, note how, for the specific case of a cafeteria grill, you might still win out at peak hours. This is because, with a single person at the grill performing all of the tasks involved with making a sandwich, you may incur overhead as that person moves from one stage to another. In a pipeline, workers can churn right along on their single task, without changing places or switching equipment. So a peak-hour cafeteria grill with more workers may still get you your food faster than an off-hour grill with a single worker.

Of course, in the realm of computer architecture, we do have the advantage that additional workers don’t cost an additional chunk of salary, with benefits. This whole “employee cost” mentality is the primary reason, of course, for why many operations don’t happily hire more workers even though they know that their customers will be happier and get served faster. But somewhere along the way, there must be an inflection point: at a certain level of excellent service, wouldn’t more customers eventually show up, perhaps eventually offsetting the cost of the additional workers? Certainly — but this entails a completely different kind of “computational sense.”   :)

Keep Your Friends Close, Your Enemies Closer, and Your Work Closest of All

As coffee and tea were being proffered after dinner at a friend’s house one night, I noticed that our hosts had loaded the dishwasher and started it up. It was a gathering of good friends, and so the dishes were done well before the group was ready to call it a night.

This friend has a large, spacious kitchen, with storage galore and an attractive island in the middle. Said island also houses the dishwasher, which our host then approached upon realizing that the dishes were done. He opened the dishwasher, and started to take items out a few at a time, moving around the kitchen as he put them in their respective locations.

What’s wrong with this picture? Nothing, really, except that my friend was taking more time to put away the dishes than was really necessary. I suggested an alternative: instead of taking random groups of items from the dishwasher, then placing them in the appropriate locations in the kitchen immediately, why not take everything out of the dishwasher first, and then, when everything was laid out on that generous island, sort them out by where they belong and take them in these clusters to their designated places?

This tweak in dishwasher unloading sped things up noticeably. Instead of multiple repetitions of crouching into the dishwasher, pulling things out, walking around the kitchen, then keeping them where they belong, all of the crouching and pulling was done at the beginning. Walking clusters of items from the island to their designated cabinet, drawer, or cupboard resulted in fewer trips to and from the kitchen’s center island.

What happened here? Some would say common sense; in this case, however, there is also computer science beneath the common sense. By doing all of the crouching-pulling-out first, and then doing all of the walking-to-cupboard activities in clusters next, we were taking advantage of locality of reference.

Locality of reference is a fairly simple premise: individual tasks or units of work tend to cluster around a certain group of items. We stay “within” this group of items for as long as we’re performing that particular task. When we move on to something else, we shift to a different group of items.

The upshot of this principle is that, if we identify the items that we need in order to perform a particular task, we can perform that task more quickly if we keep those items close by for the duration of that task. Here’s where computer science shoots back to common sense: for as long as you need something, keep it close by; the closer something is to you, the more quickly you can get to it, and so doing any work that involves that item proceeds more quickly.

Unloading a kitchen item from a dishwasher can be broken down into:

1. Crouching over the open dishwasher
2. Taking the item out of the dishwasher
3. Transporting the item to its proper location in the kitchen
4. Placing the item in that location

At first, our dinner host was performing each of these steps for random batches of items — whatever he can carry — from the dishwasher. Note how he wasn’t taking advantage of locality of reference: he had to shuttle between the dishwasher and multiple locations in the kitchen for every batch of items, thus incurring travel time that made the overall task take longer. The “fix” that was suggested took into account the fact that multiple items typically belonged to a particular area of the kitchen. Multiple trips for individual items became a single trip for a group of items: the “referenced” items were kept together (“local”) as much as possible, both when taking them out of the dishwasher (one “locality”) and when putting them away in their designated kitchen location (the other “locality”).

Locality of reference plays a significant role in many areas of computer science. For instance, it is the foundational principle behind caches in computer architecture — small blocks of fast memory which hold the most-referenced data at any given time. Faster memory access for the data we need most frequently translates to faster performance.

In operating systems, virtual memory allows programs to work as if they have more memory available to them than actually exists on the physical machine. Due to locality of reference, a program is very unlikely to need absolutely all of that memory at any given time; instead, it moves from one section of its memory space to another as it does its work. The net result is that an operating system can temporarily shunt the (currently) unused sections of memory to a disk, automatically moving them back when the program goes into a new unit of work (thus needing a new memory “locale”).

But the bottom line is that locality of reference may be found in any task that we undertake, regardless of whether that task involves a computer. If we are on the lookout for the “localities” within that task, and find ways to restructure what we do to stay within those localities as much as possible, then we may be able to squeeze things out just a little (or a lot) more quickly.

Of course, this whole discussion would never have come up had the guests also helped by lending more hands to put the dishes away...but that has to do with parallelism. That can show up in daily life too, but we’ll get to that some other time.

Waiting for Poisson

Most of us hate waiting in line. Or, at the very least, when given the choice of waiting in line or not, most of us would probably choose “not.”

Most of us probably also feel that not all lines are created equal. There’s your typical multiple-line setup at your favorite CostCo or grocery store; there’s the single-file aisle-of-impulse-buys at Fry’s Electronics or, more recently, at Best Buy. How about those tiered lines at the airport, separating the haves (first-class, super-plati-diamond-tanium members) from the have-nots (coach, me)? Have you ever stood in one of those lines, and thought, “I wish they’d line up they way they do at <put the place with your favorite type of line here>!”?

If you’ve ever felt that they aren’t the same, take heart — they’ve been proven to be different. And measurably so.

The subfield of computer science known as queueing theory (also spelled queuing theory) concerns itself with precisely this — lines, waiting in line, and servicing the “customers” that are in line. And if everyone knew just a little queueing theory, then many of us may not hate waiting in line as much as we do now.

The primary factor that affects me while waiting in line is fairness — that is, “first-come, first-served” is of paramount value. The longer you’ve been waiting in line, the sooner you should get helped. And this is where some of the lines I see everyday make me wish that everyone knew a little computer science: the single line (Fry’s, some Best Buy branches, some banks) waiting for multiple servers is known to enforce “first-come, first-served” — no matter how many tellers, cashiers, or other “servers” come and go, the client who has been waiting longest will get helped soonest. In technical terms, this type of line serializes the way customers are helped. Cut to the chase: everyone should just know to form this type of line, whenever we’re all waiting for some service that can be provided by more than one party at a time.

How many times have you groaned in frustration within a multiple-line setup, as a teller or cashier opens up at the far end of the store, and everyone who’s nearby (but who may not have necessarily been waiting as long as you have) jumps over to get helped? Or, have you ever stared longingly (or angrily) at another line, watching customers fly by because they all happened to have fewer items to check out? “Express lines” be damned — with a single queue, everyone benefits from “express” customers. With computer science, these “feelings” about multiple-line setups are no longer subjective — they’re quantifiable, objective, and provable.

Of course, we have the requisite complications. First, in a multiple-line system, we might simply try to change lines whenever we think that one line is faster than ours. This is theoretically true; however, practical issues arise. For one thing, jumping lines at our leisure in a grocery setting involves taking a shopping cart with us — this can range from being awkward to downright dangerous. For another, have you ever jumped lines like this, only to perceive that the line you just left started moving faster right after you bailed on it? Whether or not the perception is true, what matters is that it emerges — so we’re not happy. Or, at best, wistful for the line that got away. And even if line jumping weren’t potentially inconvenient or risky, there’s this final question: if more than one customer simultaneously notices a more favorable spot in another line, which one of them should take it?

Another complication is that some establishments want us to potentially hang around in line longer, to give us more of an opportunity to buy something on impulse. True, and some of us may truly enjoy the impulse experience. However, impulse buying can still be encouraged in a single line — just arrange your impulse wares along that single aisle, en masse. Bingo — less stress at the line, great chance at an impulse buy.

As mentioned, the point of all this is that if everyone knew a little bit more computer science, we’d automatically send “the man” a message that single lines are just the way to go. We would form this line automatically, without prodding, poking, or frustrating our fellow line-waiters. Daily life would be just a little easier.

For a postscript, please note that this barely scratches the surface of what queueing theory has learned about lines. The haves/have-nots line — i.e., clients with different priorities — has also been studied. Different rates at which things may happen — customer arrivals, the time it takes to perform services, etc. — are also considered and studied; this entry’s title references the Poisson distribution, which is commonly used for determining or simulating “rates of arrival” for clients and other events. But if everyone knew a little probability and statistics, then you would have known that already.   :)