Date: Thu, 25 Aug 2022 12:55:46 +0200
Subject: Insertion Sort Improvements
From: Benjamin Coutu <ben.coutu@zeyos.com>
To: pgsql-hackers@postgresql.org
Message-ID: <ddc4e498740a8e411c59@zeyos.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/ddc4e498740a8e411c59%40zeyos.com>
Precedence: bulk

Hello,=0A=0AInspired by the recent discussions[1][2] around sort improvemen=
ts, I took a look around the code and noticed the use of a somewhat naive v=
ersion of insertion sort within the broader quicksort code.=0A=0AThe curren=
t implementation (see sort_template.h) is practically the textbook version =
of insertion sort:=0A=0Afor (pm =3D a + ST_POINTER_STEP; pm < a + n * ST_PO=
INTER_STEP; pm +=3D ST_POINTER_STEP)=0A  for (pl =3D pm; pl > a && DO_COMPA=
RE(pl - ST_POINTER_STEP, pl) > 0; pl -=3D ST_POINTER_STEP)=0A    DO_SWAP(pl=
, pl - ST_POINTER_STEP);=0A=0AI propose to rather use the slightly more eff=
icient variant of insertion sort where only a single assignment instead of =
a fully-fledged swap is performed in the inner loop:=0A=0Afor (pm =3D a + S=
T_POINTER_STEP; pm < a + n * ST_POINTER_STEP; pm +=3D ST_POINTER_STEP) {=0A=
  DO_COPY(pm_temp, pm); /* pm_temp <- copy of pm */=0A  =0A  pl =3D pm - ST=
_POINTER_STEP;=0A  =0A  for (; pl >=3D a && DO_COMPARE(pl, pm_temp) > 0; pl=
 -=3D ST_POINTER_STEP)=0A    DO_ASSIGN(pl + ST_POINTER_STEP, pl); /* pl + 1=
 <- pl */=0A    =0A  DO_COPY(pl + ST_POINTER_STEP, pm_temp); /* pl + 1 <- c=
opy of pm_temp */=0A}=0A=0ADO_ASSIGN and DO_COPY macros would have to be de=
clared analogue to DO_SWAP via the template.=0A=0AThere is obviously a trad=
e-off involved here as O(1) extra memory is required to hold the temporary =
variable and DO_COPY might be expensive if the sort element is large. In ca=
se of single datum sort with trivial data types this would not be a big iss=
ue. For large tuples on the other hand it could mean a significant overhead=
 that might not be made up for by the improved inner loop. One might want t=
o limit this algorithm to a certain maximum tuple size and use the original=
 insertion sort version for larger elements (this could be decided at compi=
le-time via sort_template.h).=0A=0AAnyways, there might be some low hanging=
 fruit here. If it turns out to be significantly faster one might even cons=
ider increasing the insertion sort threshold from < 7 to < 10 sort elements=
. But that is a whole other discussion for another day.=0A=0AHas anyone tes=
ted such an approach before? Please let me know your thoughts.=0A=0ACheers,=
=0A=0ABenjamin=0A=0A[1] https://www.postgresql.org/message-id/flat/CAFBsxsH=
anJTsX9DNJppXJxwg3bU%2BYQ6pnmSfPM0uvYUaFdwZdQ%40mail.gmail.com=0A[2] https:=
//www.postgresql.org/message-id/flat/CAApHDvoTTtoQYfp3d0kTPF6y1pjexgLwquzKm=
jzvjC9NCw4RGw%40mail.gmail.com=0A=0A-- =0A=0ABenjamin Coutu=0Ahttp://www.ze=
yos.com