After reading a paper that grabbed his curiosity and wouldn't let go, Andrei set out to determine if Lomuto partitioning should still be considered inferior to Hoare for quicksort on modern hardware. This blog post details his results.

Blog:
https://dlang.org/blog/2020/05/14/lomutos-comeback/

Reddit:
https://www.reddit.com/r/programming/comments/gjm6yp/lomutos_comeback_quicksort_partitioning/

HN:
https://news.ycombinator.com/item?id=23179160

On 5/14/20 9:26 AM, Mike Parker wrote:
> After reading a paper that grabbed his curiosity and wouldn't let go, Andrei set out to determine if Lomuto partitioning should still be considered inferior to Hoare for quicksort on modern hardware. This blog post details his results.
> 
> Blog:
> https://dlang.org/blog/2020/05/14/lomutos-comeback/
> 
> Reddit:
> https://www.reddit.com/r/programming/comments/gjm6yp/lomutos_comeback_quicksort_partitioning/ 
> 
> 
> HN:
> https://news.ycombinator.com/item?id=23179160

Thanks, Mike. HN has possibly categorized it as spam already. One thing they do is they detect (by using the "Referrer" header) whether the post has been shared via a direct link. They do so to prevent manipulation.

The right way to share something on hackernews is to send people to https://news.ycombinator.com/newest and mention the time of sharing.

On Thursday, 14 May 2020 at 13:26:23 UTC, Mike Parker wrote:
> ...
> Reddit:
> https://www.reddit.com/r/programming/comments/gjm6yp/lomutos_comeback_quicksort_partitioning/
> ...

If possible could you please next time share link with "old" instead of "www"? Like:

https://old.reddit.com/r/programming/comments/gjm6yp/lomutos_comeback_quicksort_partitioning/

Thanks,

SG.

On Thursday, 14 May 2020 at 13:40:24 UTC, Andrei Alexandrescu wrote:
> On 5/14/20 9:26 AM, Mike Parker wrote:

> The right way to share something on hackernews is to send people to https://news.ycombinator.com/newest and mention the time of sharing.

Okay everyone, please use this link or search for "Lomuto's Comeback" in the search field.

I've been hearing conflicting accounts of this for a while, with more people telling me it doesn't happen anymore. However, it seems posts were never flagged as spam for this. Instead, any upvotes from people coming through direct links *do not count*. Coupled with the fact that the FAQ still says posts are penalized for "asking for votes", I'm no longer going to share direct links to HN articles.

Found multiple sources about it, but this 2015 post lays it all out and I assume it's still mostly relevant:
https://wiredcraft.com/blog/how-to-post-on-hacker-news/

https://news.ycombinator.com/newsfaq.html

On Thursday, 14 May 2020 at 13:40:24 UTC, Andrei Alexandrescu wrote:
> [snip]

Really interesting. Thanks for sharing.

I have recently been spending some spare time learning more about D's topN and pivotPartition implementation, which led me to your paper on fast deterministic selection.

Would you consider changing the pivotPartition implementation based on this?

Would the insights gleamed from this paper mean that a branchless version of topN could be faster?

On Thursday, 14 May 2020 at 13:26:23 UTC, Mike Parker wrote:
> After reading a paper that grabbed his curiosity and wouldn't let go, Andrei set out to determine if Lomuto partitioning should still be considered inferior to Hoare for quicksort on modern hardware. This blog post details his results.
>
> Blog:
> https://dlang.org/blog/2020/05/14/lomutos-comeback/
>
> Reddit:
> https://www.reddit.com/r/programming/comments/gjm6yp/lomutos_comeback_quicksort_partitioning/
>
> HN:
> https://news.ycombinator.com/item?id=23179160

Wow, very interesting article.
Thanks for sharing.

On Thursday, 14 May 2020 at 13:26:23 UTC, Mike Parker wrote:
> After reading a paper that grabbed his curiosity and wouldn't let go, Andrei set out to determine if Lomuto partitioning should still be considered inferior to Hoare for quicksort on modern hardware. This blog post details his results.

Fantastic work and great result. Having privately done a very heavy critique of the narrow niche the article had chosen to explore I still recognize and love the results.

—
Dmitry Olshansky

On Thursday, 14 May 2020 at 13:26:23 UTC, Mike Parker wrote:
> After reading a paper that grabbed his curiosity and wouldn't let go, Andrei set out to determine if Lomuto partitioning should still be considered inferior to Hoare for quicksort on modern hardware. This blog post details his results.
>
> Blog:
> https://dlang.org/blog/2020/05/14/lomutos-comeback/

Nice stuff!

One curious question -- unless I've misread things horribly, it looks like the D benchmarks for Lomuto branch-free are consistently slower than for C++.  Any idea why that is?  I would expect gcc/gdc and clang/ldc to produce effectively identical results for code like this.

On Friday, 15 May 2020 at 10:28:41 UTC, Joseph Rushton Wakeling wrote:
> One curious question -- unless I've misread things horribly, it looks like the D benchmarks for Lomuto branch-free are consistently slower than for C++.  Any idea why that is?  I would expect gcc/gdc and clang/ldc to produce effectively identical results for code like this.

Wrt. the LDC results, LDC v1.17 was shipped with LLVM 8.0.1, while the used clang is v10 based on LLVM 10, so that might account for some slight diffs.

On Thursday, 14 May 2020 at 13:26:23 UTC, Mike Parker wrote:
> After reading a paper that grabbed his curiosity and wouldn't let go, Andrei set out to determine if Lomuto partitioning should still be considered inferior to Hoare for quicksort on modern hardware. This blog post details his results.
>
> Blog:
> https://dlang.org/blog/2020/05/14/lomutos-comeback/

Great post, and nice to have another example for how bad branches can
really be for performance!

One note: The clang/ldc compiler explorer links for
lomuto_partition_branchfree
are wrong.