Re: A qsort template

On Mon, Apr 11, 2022 at 5:34 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> With this particular test, v15 is about 15% *slower* than v14. I
> didn't know what to blame at first, so I tried commenting out the sort
> specialisations and got the results in the red bars in the graph. This
> made it about 7.5% *faster* than v14. So looks like this patch is to
> blame. I then hacked the comparator function that's used in the
> specialisations for BIGINT to comment out the tiebreak to remove the
> indirect function call, which happens to do nothing in this 1 column
> sort case. The aim here was to get an idea what the performance would
> be if there was a specialisation for single column sorts. That's the
> yellow bars, which show about 10% *faster* than master.

Thanks for investigating! (I assume you meant 10% faster than v14?)

On Mon, Apr 11, 2022 at 4:55 AM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:

> The B&M quicksort implementation that we adopted is generally
> extremely fast for that case, since it uses 3 way partitioning (based
> on the Dutch National Flag algorithm). This essentially makes sorting
> large groups of duplicates take only linear time (not linearithmic
> time).

In the below thread, I wondered if it still counts as extremely fast
nowadays. I hope to give an answer to that during next cycle. Relevant
to the open item, the paper linked there has a variety of
low-cardinality cases. I'll incorporate them in a round of tests soon.

https://www.postgresql.org/message-id/CAFBsxsHanJTsX9DNJppXJxwg3bU+YQ6pnmSfPM0uvYUaFdwZdQ@mail.gmail.com

On Mon, Apr 11, 2022 at 4:44 AM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:

> Upthread we were discussing which variations it'd be worth investing
> extra text segment space on to gain speedup and we put those hard
> decisions off for future work, but on reflection, we probably should
> tackle this particular point to avoid a regression. I think something
> like the attached achieves that (draft, not tested much yet, could
> perhaps find a tidier way to code the decision tree). In short:
> variants qsort_tuple_{int32,signed,unsigned}() no longer fall back,
> but new variants qsort_tuple_{int32,signed,unsigned}_tiebreak() do.

Looks good at a glance, I will get some numbers after modifying my test scripts.

> We should perhaps also reconsider the other XXX comment about finding
> a way to skip the retest of column 1 in the tiebreak comparator.
> Perhaps you'd just install a different comparetup function, eg
> comparetup_index_btree_tail (which would sharing code), so no need to
> multiply specialisations for that.

If we need to add these cases to avoid regression, it makes sense to
make them work as well as we reasonably can.

--
John Naylor
EDB: http://www.enterprisedb.com