MIME-Version: 1.0
References: 
 <CANWCAZYzx7a7E9AY16Jt_U3+GVKDADfgApZ-42SYNiig8dTnFA@mail.gmail.com>
 <CANWCAZbsx5VY-F5RVvZ5H1abBWcinMY90gNra6EbdGS1CTx=7g@mail.gmail.com>
 <CANWCAZaN8kW6o7Ymc_jzPO_Z5SqekQTTNra3xTGYTH+cjrVp8g@mail.gmail.com>
 <269A8FB9-6D43-43CF-A6FE-52D28CBDB8A9@Outlook.com>
 <CANWCAZZiMGj6QuHfyBPv9at7xn23NPAz4nit=G6fr26V+h8MKg@mail.gmail.com>
 <F7935986-4E3D-477C-B45C-878420B45C0D@gmail.com>
 <CANWCAZaKRzsYPn9YWRR8g5dkX-ep_jgyUb4r3KFekK5ZTNo7ew@mail.gmail.com>
 <606C775A-4C1A-482B-BE7D-2E7A46AE14B9@gmail.com>
 <CANWCAZaBeDPfF0sCdSssRXv6nBZeRP8Z=OO1731zsoUC58U5_Q@mail.gmail.com>
 <F7D64692-F979-4661-B91C-8A1FF09F69BD@gmail.com>
 <9D3D4647-868B-4562-B382-D201478AD67B@gmail.com>
In-Reply-To: <9D3D4647-868B-4562-B382-D201478AD67B@gmail.com>
From: John Naylor <johncnaylorls@gmail.com>
Date: Mon, 8 Dec 2025 13:26:38 +0700
Message-ID: 
 <CANWCAZZo5rgE4+NYYES1hLN9PvonXMH=K3Z7b0TKcCBNOAjaag@mail.gmail.com>
Subject: Re: tuple radix sort
To: Chao Li <li.evan.chao@gmail.com>
Cc: Chengpeng Yan <chengpeng_yan@outlook.com>,
	"pgsql-hackers@lists.postgresql.org" <pgsql-hackers@lists.postgresql.org>,
 Peter Geoghegan <pg@bowt.ie>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/CANWCAZZo5rgE4%2BNYYES1hLN9PvonXMH%3DK3Z7b0TKcCBNOAjaag%40mail.gmail.com>
Precedence: bulk

On Mon, Dec 8, 2025 at 9:52=E2=80=AFAM Chao Li <li.evan.chao@gmail.com> wro=
te:
> First, I changed my direction and implemented the in-place switching in t=
he other way, where I did a way like chained-switching. Say starting from i=
tem0, for example, switching item0 to item5, then check where item5 should =
be switched to, and makes the switch, till an item is switch to position 0.=
 See my implementation in other-implemation.diff if you are interested in i=
t. This time, I eyeball checked the sort result and confirmed the correctio=
n. But my implementation is slightly slower than your implementation, based=
 on the same test procedure I described in my previous email, my implementa=
tion is roughly ~3% slower your implementation. So I think that at least pr=
oves your current implementation in v5 has been perfectly fine tuned.

That shouldn't be surprising, since the way you describe is basically
"American flag sort", which is much older, and the innovation of
ska_byte_sort was to recognize that this is bad for CPU pipelining.
That was explained in detail in the blog post I linked to in my first
email.

Also notice that by attaching a .diff, the CF bot tries and fails to
apply that to master, and has been complaining that my patch needs a
rebase. Please don't do that again.

--
John Naylor
Amazon Web Services