News for hackers. Stuff that matters.

A comment on Fastest table sort in the West – Redesigning DuckDB's sort.

Re:Fastest table sort in the West – Redesigning DuckDB's sort by masklinn on Friday August 27, 2021 @01:49PM (#28330882)
> While std::sort is excellent algorithmically, it is still a single-threaded approach that is unable to efficiently sort by multiple columns because function call overhead would quickly dominate sorting time.

I don't understand what this is saying. Is it just using a lot of words to note that as the number of columns increase so do the comparator's cost?

[ Parent | on HN ]
Re:Fastest table sort in the West – Redesigning DuckDB's sort by dahfizz on Friday August 27, 2021 @02:03PM (#28331071)
The author is pointing out two problems with std::sort

1- std::sort is single threaded

2- std::sort is unable to efficiently sort by multiple columns

[ Parent | on HN ]
Re:Fastest table sort in the West – Redesigning DuckDB's sort by masklinn on Friday August 27, 2021 @02:24PM (#28331302)
> 1- std::sort is single threaded

I would hope it is quite obvious that is not what I have an issue with.

> 2- std::sort is unable to efficiently sort by multiple columns

It's asserting that with an explanation which is not one, and I'm asking what it is actually saying. "unable to efficiently sort by multiple columns because function call overhead would quickly dominate sorting time." is not an actual explanation.

[ Parent | on HN ]
Re:Fastest table sort in the West – Redesigning DuckDB's sort by dragontamer on Friday August 27, 2021 @05:32PM (#28333201)
Hmmm.

std::sort is a template in C++. Which means that in most cases, I'd expect std::sort to inline the comparator and not have any function call overhead at all. (And even further: that the optimizer can make optimizations to std::sort + comparator together since they've been inlined)

So you have a good point. Function overhead is in qsort, not in std::sort. The line reads kinda nonsensically to me now that I think of it.

[ Parent | on HN ]
Re:Fastest table sort in the West – Redesigning DuckDB's sort by b9a2cab5 on Friday August 27, 2021 @05:50PM (#28333342)
The way I read it was that with many columns the overhead of the compare function (even if it's inlined) is too high compared to sorting overhead.
[ Parent | on HN ]
Re:Fastest table sort in the West – Redesigning DuckDB's sort by lnkuiper on Friday August 27, 2021 @06:32PM (#28333659)
Exactly. Even when it’s inlined, having a comparator with if/else is much, much slower than a single memcmp
[ Parent | on HN ]