On the D Blog: Lomuto's Comeback

Andrei Alexandrescu SeeWebsiteForEmail at erdani.com
Tue Aug 4 13:49:32 UTC 2020

On 8/4/20 4:19 AM, Iain Buclaw wrote:
> On 04/08/2020 03:14, Andrei Alexandrescu wrote:
>> Interesting, thanks!
> Did a quick benchmark for n in `seq 1 10` ./lomuto.exe ${n}000000...
> Looks good, so committing patch. :-)

Awesome, thanks! That does solve a puzzler I had while benchmarking.

I'm thinking the story of discovering and fixing this would be a great 
follow-up in the blog. It doesn't quite mesh with Mike's current 
introductory series, but it could be done as an intermezzo a la "Now For 
Something Completely Different (And Much Lower Level)".

Sketch of an intro:

Upon reading "Lomuto's Comeback" in the D blog, I noticed the 
performance were consistently juuust a bit worse for the D version than 
for the C++ version for the same source code. My own measurements 
confirmed the same. That bothered me at two levels. First, people 
unfamiliar with the D language would form the opinion that D cannot 
reach the efficiency of C++. Second, as the gdc creator and maintainer, 
I knew for a fact the produced code must be literally identical. Any 
difference would pin point a bug somewhere in the code generation 
pipeline. So I set out to find it and fix it. This is the story of that 
investigation, which will take us through looking through disassembly, 
finding the culprit, devising a fix, confirming with measurements, and 
patching the open-source gdc compiler.


More information about the Digitalmars-d-announce mailing list