Tuesday, December 26, 2006

Functionality Over Elegance

I'm reading Where Wizards Stay Up Late which is a book about the people that invented the internet.  It's the story of ARPA and BBN and the creation of essentially the first computer network.  I ran across an interesting quote from one of the programmers of the first networking gear (the IMP).  Dave Walden said, "There was an infinity of ways we could go wrong, and a substantials number of ways to go right.  Good engineers find one of the ways of going right."  He was pointing out the difference between a computer scientist and a computer engineer.  The scientist looks for the ultimate way of doing things.  The one that trumps all others.  The engineer just looks for a way.*

This isn't to say that all ways are equal.  There are tradeoffs that must be made and their consequences considered.  However, given a time budget, reliability requirements, and performance metrics, a number of solutions often make the grade.  A scientist might continue to investigate which one is best whereas an engineer picks one and moves on. 

The author says it this way:  "At its core, all engineering comes down to making tradeoffs between the perfect and the workable."  He makes the point that when you are trying to ship a product, functionality trumps beauty and elegance. 

As I stated in my essay on the subject of design, sometimes you just need to go with a solution.  It is the job of those of us in the trenches to find a solution and make it work.  It is all too easy to continue to pursue the better in the face of the adequate.  More often than not, doing so leads to overdesign and missed deadlines.  The place where this bites most engineers is in the desire to rewrite.  How often have you heard someone say "This whole module needs to be rewritten."?  Sometimes it really does but more often it comes from a sense of aesthetics.  The code isn't written the way we would have done it or it isn't written as optimally as possible. 

As software engineers, we must remember that the ultimate goal is the shipping of a product.  We must make decisions with that goal in mind.  When faced with the temptation to rewrite a whole section of code, we must resist.  If a simple patch will solve the problem, go with the patch.  The product will thank you.


* The use of engineer and scientist here is my choice, not necessarily Walden's.

Monday, December 25, 2006

Merry Christmas

By now you're all probably stuffed full of food and staring at a pile presents not to mention wrapping paper, ribbons, bows, and boxes.  I hope you all had a great day.  Enjoy your time away from the regular routine for a while.  Take the time to do something you don't normally get to--reflect, talk to family, play some games, do some programming for yourself, etc.  Whatever it is, have a great time doing it.  Merry Christmas!


Tuesday, December 19, 2006

Secret Santa is NP-Complete

Every year my group of friends undertakes a Secret Santa gift exchange.  When we started we each drew names from a hat and bought a gift for the names we drew.  Being budding programmers, we soon dispensed with the hat and wrote a program to do the work for us.  In 1999 a friend and I wrote a C++ app to do the work.  Though we've been running it every year, the code hasn't much changed in the intervening seven years.  It is getting dated and needs reworking. 

Toward that end, I've been contemplating the match routine lately.  The current one does something naive like:

Pick a person

Choose a match at random

If there is a conflict with that person, slide to the next one on the list.

Once a match is found, remove those people from the relative lists and pick a new person.

If a match cannot be made, start the process over.

With a small number of people and not a lot of blacklisting (husband shouldn't draw wife's name, etc.), this algorithm will work.  However, for a complicated list of people, this algorithm is nondeterministic and could theoretically run forever.  I was thus searching for a better algorithm.  One which was faster than a complete enumeration of all options and deterministic in nature.

This weekend I took the final for my Formal Models of Computation course.  (Yes, this ties in with the above--be patient) The last thing we covered was complexity classes and the concepts of P and NP.  What follows is a brief description of this concept.  For a more formal handling of the subject, check out the Wikipedia entry

In theoretical computer science, they don't use real computers.  Rather, they use formal models called Turing Machines.  These have the same power to solve problems that modern computers do, just a bit less efficiently.  They are a good proxy for real computers.  The speed of these machines is measured roughly in terms of the input.  So given an input of length n, a linear algorithm would take O(cn) time, where c is a constant.  We usually ignore these constants and just call it O(n) time. 

There is a class of problems called P or Polynomial-time which represent those problems that can be solved by a Turing machine in a time which is a polynomial of the input length.  That is, O(n^2), O(n^3), ... , O(n^k).  These are generally thought of as those problems that computers can efficiently solve.

There is another class of problems called NP or Nondeterministic-Polynomial-time.  These represent those problems that can be solved by a nondeterministic Turing machine in polynomial time.  A nondeterministic Turing machine is bascially one that can do more than one thing at once.  When it comes to a fork in the algorithm, it can take both forks simultaneously. 

It is assumed that NP describes a bigger universe of problems than P.  That is, P !=NP.  What takes nondeterministic Turing machines polynomial time takes regular Turing machines exponential time.  That is, they take something like O(2^n) time.

Back to my Secret Santa problem.  It was just after my final that I turned my thoughts back to solving this problem.  It then hit me that what I was trying to do was impossible.  There is a well-known NP-class problem which involves finding a Hamiltonian circuit.  A Hamiltonian circuit is a path that traverses an entire graph by visting each node exactly one time.  It turns out that this is exactly the problem I was trying to solve.  Imagine my Secret Santa problem as a graph where each person is a node and there are edges between all nodes that are not blacklisted.  In this view of the problem, I'm trying to find a path around the graph, visting each node once.  In theoretical computer science this is known as a reduction.

This analysis pretty much dashes my chances of finding an elegant solution to the problem.  There is no true solution other than brute force trying each combination.  With the small number of nodes in my usual matching, this works but I still want something better.  All is not lost, however.  There are some techniques I can use to get close to the solution without necessarily trying all of the combinations which I intend to investigate.  I'll write about them after I understand more.

Wow.  I guess I did learn something practical in that class after all. 

Monday, December 18, 2006

None of Us Is as Dumb as All of Us

That's the subtext on the "Meetings" inspirational poster from Despair.com.  What it means to me is that you'll never get a great design out of a committee.  When designing a piece of software, you want to get input from many people but how do you keep from being paralyzed by input.  Worse yet, how do you keep the design from becoming an incoherent mess with so many people making the decisions?  The simple answer is to elicit feedback from a large group but continue to act autonomously.

It is my contention that things of beauty tend to come from a single mind.  At best, they come from a small group.  The flip side of this coin is that the ugliest things also tend to come from this same group.  A large number of contributors tends toward bland and average.  Look at television or movies.  The best shows are often those where the creators are allowed creative license.  The shows that merely average are many times those where the studio plays a large role.  Let's take one of my all-time favorite shows, Babylon 5.  The initial series was brilliant.  The studio stayed out of the way.  Fans responded.  After it was finished, there was a spinoff called Crusade.  This time the studio came in and meddled.  They demanded more action.  They rearranged the order of the episodes.  They changed the dialog.  The show tanked.

How does this apply to designing software?  Should you just shut yourself in your office (or cube) and design?  Not exactly.  What makes the great come from a small group and the mundane come from lots of input is that a small group has a coherent vision.  Large groups have a hard time operating under a shared vision.  Each memberr has a different idea of what the outcome should be.  This usually leads to a poor design.  The features are often implemented in a nonuniform way or are difficult to work together.  Sometimes, to satisfy everyone, nothing is pruned.  Every option and setting is exposed.

The value of a single decision-maker is coherency.  As I state above, this can lead not only to the best designs but also to the worst.  Doing things completely alone is often a prescription for even greater disaster than doing them by committee.  What then is to be done?  It is a necessity to satisfy customer desires.  A "great" product no one wants isn't really great.  The secret is to listen to idea but not to be beholden to them.

Recently we were trying to make some changes to a shared test shell.  The major changes were fairly noncontroversial.  The small details, however, became a serious sticking point.  People couldn't agree on the exact semantics.  Each person had a preference.  Most were equally valid but no one idea was coming out on top.  Eventually I called for a close to the debate and told the person responsible to just go with whatever convention he deemed best.  This settled the issue and people are (apparently) satisfied with the results.

Too often we get stuck into a binary mindset.  Either we take feedback and treat it as gospel or we ignore feedback altogether--because we know best.  Instead, we need to mix the two. 

My advice when designing something is to have an individual or a small group with a shared idea drive the design.  This ensures a coherent interface and gives a greater chance that the solution will be elegant.  To avoid the trap of irrelevance, this group should solicit feedback from a wide variety of sources.  They must listen to ideas, but be willing to reject them. 

Tuesday, December 5, 2006

The State of PC Audio

One of the things I own at Microsoft is test development for audio in Windows.  For Vista we did a lot of work to rewrite the audio system and make it more stable and enable more features.  Just recently ExtremeTech published an article on the State of PC Audio.  It talks about the various options for audio including motherboard sound and the various discrete cards available.  If the changes we made for Vista are interesting to you, the article contains a useful drawing of the audio paths in XP and Vista. 

The author complains about the state of motherboard audio.  This is one of the things we're looking to improve for Vista.  In order to get a Windows Vista logo, all machines are required to pass a certain set of qualification tests.  Some of those tests--provided by my team--are there to measure the quality of the audio coming out of a PC.  With these tests, we hope to move the quality of motherboard audio forward.

If PC Audio interests you, be sure to check out these two blogs:

The Audio Fool - One of the people responsible for writing the audio fidelity tests behind the logo.

Larry Osterman - A developer on the audio team.  Also a great source for programming tips and amusing Microsoft history.

Friday, December 1, 2006

New Vista Sound

This is a bit dated but it's worth mentioning anyway now that Vista is officially launched for businesses.  Each major release of Windows comes with a startup sound.  Vista is no different.  It has a sound created by Robert Fripp.  I was lucky enough to be able to attend one of the recording sessions for the new sound.  Scoble captured that session and it is availabe at channel9.

The person responsible for the Vista sound is Steve Ball who happens to be a program manager in my group and sits just down the hall.  He recently gave an interview to NPR where he introduces the new sound.  It is short at just over 2 minutes and goes over the various sounds from past versions as well as the new one.  Here is an article talking about the new sound.

 Update:  In the spirit of accuracy, the session I point to above is not the one that I attended, but is one like it.