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: Tue, 23 May 2023 11:10:45 +0200
Message-ID: <042b841e324e22c79e23@zeyos.com> (raw)
In-Reply-To: <CAFBsxsFs5=0yHx+-03EYkf+Y_s0evkgDYstUXFeQvogTi7dSig@mail.gmail.com>
References: <CAFBsxsFs5=0yHx+-03EYkf+Y_s0evkgDYstUXFeQvogTi7dSig@mail.gmail.com>
Greetings,
I would like to revisit the discussion and concur with John's perspective that incremental progress through small, successive modifications is the appropriate approach to move forward. Therefore, I would like to propose two distinct ideas aimed at enhancing the functionality of insertion sort:
1. Implementation of a more efficient variant (as described in the introductory part of this thread):
------------ OLD ------------
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP)
for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
pl -= ST_POINTER_STEP)
DO_SWAP(pl, pl - ST_POINTER_STEP);
------------ NEW ------------
for (
pm = a + ST_POINTER_STEP;
pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP
) {
ST_POINTER_TYPE tmp = *pm;
for (
pl = pm - ST_POINTER_STEP;
pl >= a && DO_COMPARE(pl, &tmp) > 0;
pl -= ST_POINTER_STEP
)
*(pl + ST_POINTER_STEP) = *pl;
*(pl + ST_POINTER_STEP) = tmp;
}
------------
2. It appears that there is a consensus against disregarding the presorted check, despite its questionable value. In light of this, an alternative suggestion is to integrate the presorted check into the insertion sort path by utilizing an unbounded insertion sort. Only after a maximum number of swaps have occurred should we abandon the sorting process. If insertion sort is executed on the entire array without any swaps, we can simply return. If not, and we continue with quicksort after the swap limit has been reached, we at least have left the array in a more sorted state, which may likely be advantageous for subsequent iterations.
------------ OLD ------------
if (n < 7)
{
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP)
for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
pl -= ST_POINTER_STEP)
DO_SWAP(pl, pl - ST_POINTER_STEP);
return;
}
presorted = 1;
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP)
{
DO_CHECK_FOR_INTERRUPTS();
if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
{
presorted = 0;
break;
}
}
if (presorted)
return;
------------ NEW ------------
#define LIMIT_SWAPS 30 /* to be determined empirically */
int swaps = 0;
for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
pm += ST_POINTER_STEP)
for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
pl -= ST_POINTER_STEP) {
DO_SWAP(pl, pl - ST_POINTER_STEP);
if (++swaps == LIMIT_SWAPS)
goto quicksort;
}
if (swaps == 0)
return;
quicksort:
------------
Naturally, both modifications (with point 2 being highly speculative) are currently independent of each other, and it is also crucial to benchmark the combined variant as well as different values for LIMIT_SWAPS.
I would greatly appreciate assistance in benchmarking these proposed changes. Your collaboration in this matter would be invaluable.
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: <042b841e324e22c79e23@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