I really enjoy Andrei’s writing style, and the content here is very promising. He’s been spending a lot of time around the conference circuit lately trying to make the argument that traditional algorithm analysis needs to be reconsidered with newer hardware and this post makes a compelling show of a particular case study. “Measure, measure, measure” is a key concept and the techniques he touches upon in here are good to examine too.
I also enjoy his code samples compiling as both C++ and D lol. I wish I could up vote it twice but this comment is the next best thing. Well worth the read.
Very much agreed. This is a really great piece of work.
There’s a sort of comic tragedy in the overall story, as I see it. Software people have, over the brief history of our field, built up so much infrastructure, both technical and intellectual, on a reified foundation of hardware design choices. These in turn rely on economics and historical happenstance at least as much as physics. The physics hasn’t changed, but manufacturing costs and similar constraints have sometimes changed drastically over the past decades. Nonetheless, our premature abstractions have proven quite durable, perhaps due to the immense weight of the systems, practices, and pedagogies which rest on them. Meanwhile, hardware people have been methodically squeezing as much parallel processing power as possible out of machines which emulate the old standard sequential abstractions enshrined in our programming models, using tricks like speculative execution. Hardware designers consider software fixed and optimize against it, just like software engineers optimize against the hardware we consider fixed. We’re chasing each others tails in a spiral of increasing complexity.
I had to read the opening dialog twice to realize that Hoare wasn’t criticizing Lomuto’s algorithm, but pointing out a potential advantage of it. I wonder what Hoare would have said if Lomuto hadn’t interrupted him.
Since I’m pretty sure the dialogue is an imagined reconstruction or dramatization, I suppose we’re free to put words in Sir Tony’s mouth. I never met him, but I imagine that his remark, as written, is by no means out of character, since his advocacy for design simplicity is well known, and he was certainly aware of alternative computer architectures.
“Given that Hoare partition clearly does less work than Lomuto partition, the question would be why ever teach or use the latter at all. “
Formal verification. The simpler the algorithm, the less work in verifying it. The Lomuto scheme looks like it would be straightforward compared to normal Quicksort.
Might also be beneficial in parallelization. This is pure speculation on my part. It’s just that things going in one direction over a range of values might facilitate breaking the problem into pieces. If things go both directions, there’s interacting parts that might mess this up. Of course, going both directions gives an opportunity to do two things at once. Safely dealing with the shared data would probably knock out any advantages of parallelization on small amounts of data, though.
“It compiles and runs the same with a C++ or D compiler. “
That by itself was interesting. An extra argument for D as a C++ replacement that I hadn’t thought of.
“I don’t even need to worry about it because the title resolutely asserts that that problem I didn’t know I was supposed to worry about, I don’t need to worry about after all. So in a way the title cancels itself out.”
The funny thing is, the more you learn about tech, the more titles are like that without even trying to be. ;)