Re: tuple radix sort

> On Dec 4, 2025, at 13:30, John Naylor <johncnaylorls@gmail.com> wrote:
> 
> On Wed, Dec 3, 2025 at 3:22 PM 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:
>> 
>> ```
>> +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/