Bookshelf Classic: Beautiful Code

-
Cover
This book is what you get when you ask 38 top software developers "What is beautiful code?"  An open ended question, you get diverging answers such as a deep dive into a regular expression matcher from Brian Kernighan, an optimization of population counts from Henry S. Warren Jr. (for bit-heads, not sociologists), and a treatise on why code is better treated as an essay from Yukihiro "Matz" Matsumoto.

For this post though, I want to focus on Jon Bentley's contribution, curiously titled "The Most Beautiful Code I Never Wrote."  Elaborating, Bentley writes

In software, the most beautiful code, the most beautiful functions, and the most beautiful programs are sometimes, not there at all.

He then uses the Quicksort algorithm to illustrate his point, first reviewing the code, instrumenting it with counters, and optimizing it along the way.  But the pressing question he tries to answer is: "How many comparisons does Quicksort make, on average, for a random array of size n?"

One could generate large samples of random data, make several trial runs, and get an average, but Bentley takes a different route, a code-less path that crosses into mathematical proofs.  I didn't find it easy to follow, and got help from a talk he gave to Google in 2007: Three Beautiful Quicksorts.



In the end, Bentley derives a completely mathematical analysis of Quicksort's behavior.  It's wonderful.  It's frustrating.  It reminds me of an old joke:

A hungry man walks into a diner and sees the special is a Ham Sandwich.  "Nothing would be better than a ham sandwich!"  

 The waitress returns with an empty plate.  "What's this?" the man asks.

She replies, "You said 'Nothing would be better than a ham sandwich.'  So I gave you Nothing."

The piece doesn't fill the belly, but it does move the mind.

For more on Bentley's work, see my review of his book More Programming Pearls.









Comments

Post a Comment

Popular posts from this blog

MR2 Check Engine

-
Image
Shown here is the 1991 Toyota MR2. Thanks to the mechanical skills of a family enthusiast, it purrs, growls, and turbo whistles like a dream.   My hardware ability doesn't go much further than oil changes. Rather, my expertise is in software, and I wrote an Android App (iOS version is in progress) to diagnose the flashes of the check engine light. This second generation MR2 predates the OBD2 connector, a standard used to diagnose engine, transmission, and emissions problems quickly and easily. Instead, we have a flashing check engine light which needs some deciphering, followed by a lookup in the service manual. Basically, you count flashes to arrive at fault code number. A short pause (~1.5 seconds) indicates the start of the next digit. A medium pause (~2.5 seconds) indicates start of the next fault code. And a long pause (~4.5 seconds) means the sequence has ended and will repeat. The video below corresponds to the codes 41 and 51. Using the the MR2 Check app and selecting ...
Read more

Bookshelf: UNIX A History and a Memoir

-
Image
  A man page will give you, in black and white, specific information about UNIX. Brian Kernighan's new book adds color and depth about UNIX you won't find anywhere else. I'm not a gray beard (yet), but I imagine they would plow through the book knowingly, but at the same time, learn a few things. Those new to UNIX -- recent college grads or those experimenting with Raspberry Pi -- would be better off starting with Chapter 8 which describes more relatable events and the descendants of UNIX, including Minux and Linux. It's when they start to ask questions like "Where does UNIX come from?" and "Why is Gamora grep?" that they should start from the beginning: Bell Labs, 1969. Kernighan opens with a birds-eye-view of Murray Hill New Jersey, zooms in on the buildings, the offices, the significance of Center 1127, and offers a brief look at some of the key players there. As I progressed through the book, the two factors that made UNIX not just possible, bu...
Read more

Raspberry Pi 5 Resource Limits

-
Image
I was fortunate enough to get a Raspberry Pi 5. I had no particular purpose for it other than to explore it and have fun. On UNIX and Linux based systems, part of that exploration involves checking the default resource limits . The screen shot above is a vimdiff of the rlimits for the Raspberry Pi 400 (left) and the Raspberry Pi 5 (right). Both are running their respective 64-bit versions of Raspberry Pi OS. Four of the 15 resources turned up with diffs, and it's no surprise that the pi5 would have the higher limits. These include the number of processes , the locked-in-memory address space , the number of pending signals , and the realtime priority .  They all serve the common purpose of improving realtime performance.  The last item, realtime priority , is the most telling.  On the pi400, the current and max values are 0.  On the pi5, they are 2.  These settings most likely support hardware destined for the Pi5's new PCIe connector. For a detailed review o...
Read more