Re: tuple radix sort

> On Dec 4, 2025, at 13:30, John Naylor <johncnaylorls(at)gmail(dot)com> wrote:
>
> On Wed, Dec 3, 2025 at 3:22 PM Chao Li <li(dot)evan(dot)chao(at)gmail(dot)com> wrote:
>> I played with this again today and found an optimization that seems to dramatically improve the performance:
>>
>> ```
>> +static void
>> +radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, Tuplesortstate *state)
>> +{
>> + RadixPartitionInfo partitions[256] = {0};
>> + uint8_t remaining_partitions[256] = {0};
>> ```
>>
>> 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.
>
> 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.
>

Yeah, I quickly realized I was wrong after I clicked “send". I was trying the firs two optimizations as I suggested in my previous email, but the first didn’t help much, and the second just didn’t 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’s 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/