From: Benjamin Coutu <ben.coutu@zeyos.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: Insertion Sort Improvements
Date: Fri, 26 Aug 2022 16:06:16 +0200
Message-ID: <ac56d6b6bb4d3a6f65b5@zeyos.com> (raw)
In-Reply-To: <CAFBsxsHPrvpqfNpHHC6R9fTe_us=AJ4_REWdUO9NuHcwPFF1tA@mail.gmail.com>
References: <CAFBsxsHPrvpqfNpHHC6R9fTe_us=AJ4_REWdUO9NuHcwPFF1tA@mail.gmail.com>
> convenient if you know the type at compile time. See the attached,
> which I had laying around when I was looking at PDQuicksort. I believe
> it's similar to what you have in mind.
That looks very promising.
I also love your recent proposal of partitioning into null and non-null. I suspect that to be a clear winner.
> I think it belongs around 10 now anyway.
Yeah, I think that change is overdue given modern hardware characteristics (even with the current implementation).
Another idea could be to run a binary insertion sort and use a much higher threshold. This could significantly cut down on comparisons (especially with presorted runs, which are quite common in real workloads).
If full binary search turned out to be an issue regarding cache locality, we could do it in smaller chunks, e.g. do a micro binary search between the current position (I) and position minus chunk size (say 6-12 or so, whatever fits 1 or 2 cachelines) whenever A[I] < A[I-1] and if we don't find the position within that chunk we continue with the previous chunk, thereby preserving cache locality.
With less comparisons we should start keeping track of swaps and use that as an efficient way to determine presortedness. We could change the insertion sort threshold to a swap threshold and do insertion sort until we hit the swap threshold. I suspect that would make the current presorted check obsolete (as binary insertion sort without or even with a few swaps should be faster than the current presorted-check).
Cheers, Ben
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: ben.coutu@zeyos.com, john.naylor@enterprisedb.com
Subject: Re: Insertion Sort Improvements
In-Reply-To: <ac56d6b6bb4d3a6f65b5@zeyos.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox