On the D Blog: Lomuto's Comeback

[Andrei Alexandrescu]

On 8/4/20 9:49 AM, Andrei Alexandrescu wrote:
> 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...
> [snip]
>> 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.
> 
> ...

Oh, and there are a few comments to the original blog post I'd be glad 
to respond to in an appendix.