Content-Type: text/plain;
	charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3826.700.81\))
Subject: Re: tuple radix sort
From: Chao Li <li.evan.chao@gmail.com>
In-Reply-To: 
 <CANWCAZaBeDPfF0sCdSssRXv6nBZeRP8Z=OO1731zsoUC58U5_Q@mail.gmail.com>
Date: Thu, 4 Dec 2025 16:40:18 +0800
Cc: Chengpeng Yan <chengpeng_yan@outlook.com>,
 "pgsql-hackers@lists.postgresql.org" <pgsql-hackers@lists.postgresql.org>,
 Peter Geoghegan <pg@bowt.ie>
Content-Transfer-Encoding: quoted-printable
Message-Id: <F7D64692-F979-4661-B91C-8A1FF09F69BD@gmail.com>
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>
To: John Naylor <johncnaylorls@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/F7D64692-F979-4661-B91C-8A1FF09F69BD%40gmail.com>
Precedence: bulk


> On Dec 4, 2025, at 13:30, John Naylor <johncnaylorls@gmail.com> wrote:
>=20
> On Wed, Dec 3, 2025 at 3:22=E2=80=AFPM Chao Li =
<li.evan.chao@gmail.com> wrote:
>> I played with this again today and found an optimization that seems =
to dramatically improve the performance:
>>=20
>> ```
>> +static void
>> +radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, =
Tuplesortstate *state)
>> +{
>> +       RadixPartitionInfo partitions[256] =3D {0};
>> +       uint8_t         remaining_partitions[256] =3D {0};
>> ```
>>=20
>> Here partitions and remaining_partitions are just temporary buffers, =
allocating memory from stack and initialize them seems slow. By passing =
them as function parameters are much faster. See attached diff for my =
change.
>=20
> The lesson here is: you can make it as fast as you like if you
> accidentally blow away the state that we needed for this to work
> correctly.
>=20

Yeah, I quickly realized I was wrong after I clicked =E2=80=9Csend". I =
was trying the firs two optimizations as I suggested in my previous =
email, but the first didn=E2=80=99t help much, and the second just =
didn=E2=80=99t work. After several hours debugging, I guess my brain got =
stuck and came out the weird idea.

I continued playing with this again today. I think the execution time is =
mainly spent on the in-place element switching, which uses 3 levels of =
loops (while->for->for). If we can use an extra temp array to hold the =
sorted result, then the 3-level loop can be optimized to 1-level, but =
that will cost a lot of extra memory which I am afraid not affordable.

Anyway, it=E2=80=99s a fun of playing with this optimization thing. I =
may play with it again once I get some time.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/