Re: Sort functions with specialized comparators

>
> Hello all.
>
> I have decided to explore more areas in which I can optimize and have added
> two new benchmarks. Do you have any thoughts on this?
>
> postgres=# select bench_int16_sort(1000000);
> bench_int16_sort
>
>
> -----------------------------------------------------------------------------------------------------------------
> Time taken by usual sort: 66354981 ns, Time taken by optimized sort:
> 52151523 ns, Percentage difference: 21.41%
> (1 row)
>
> postgres=# select bench_float8_sort(1000000);
> bench_float8_sort
>
>
> ------------------------------------------------------------------------------------------------------------------
> Time taken by usual sort: 121475231 ns, Time taken by optimized sort:
> 74458545 ns, Percentage difference: 38.70%
> (1 row)
>

Hello all
We would like to see the relationship between the length of the sorted array
and the performance gain, perhaps some graphs. We also want to see to set a
"worst case" test, sorting the array in ascending order when it is initially
descending

Best, regards, Antoine Violin

postgres=#
>

On Mon, Jul 15, 2024 at 10:32 AM Stepan Neretin <sncfmgg(at)gmail(dot)com> wrote:

>
>
> On Sat, Jun 8, 2024 at 1:50 AM Stepan Neretin <sncfmgg(at)gmail(dot)com> wrote:
>
>> Hello all.
>>
>> I am interested in the proposed patch and would like to propose some
>> additional changes that would complement it. My changes would introduce
>> similar optimizations when working with a list of integers or object
>> identifiers. Additionally, my patch includes an extension for
>> benchmarking, which shows an average speedup of 30-40%.
>>
>> postgres=# SELECT bench_oid_sort(1000000);
>> bench_oid_sort
>>
>>
>> ----------------------------------------------------------------------------------------------------------------
>> Time taken by list_sort: 116990848 ns, Time taken by list_oid_sort:
>> 80446640 ns, Percentage difference: 31.24%
>> (1 row)
>>
>> postgres=# SELECT bench_int_sort(1000000);
>> bench_int_sort
>>
>>
>> ----------------------------------------------------------------------------------------------------------------
>> Time taken by list_sort: 118168506 ns, Time taken by list_int_sort:
>> 80523373 ns, Percentage difference: 31.86%
>> (1 row)
>>
>> What do you think about these changes?
>>
>> Best regards, Stepan Neretin.
>>
>> On Fri, Jun 7, 2024 at 11:08 PM Andrey M. Borodin <x4mmm(at)yandex-team(dot)ru>
>> wrote:
>>
>>> Hi!
>>>
>>> In a thread about sorting comparators[0] Andres noted that we have
>>> infrastructure to help compiler optimize sorting. PFA attached PoC
>>> implementation. I've checked that it indeed works on the benchmark from
>>> that thread.
>>>
>>> postgres=# CREATE TABLE arrays_to_sort AS
>>> SELECT array_shuffle(a) arr
>>> FROM
>>> (SELECT ARRAY(SELECT generate_series(1, 1000000)) a),
>>> generate_series(1, 10);
>>>
>>> postgres=# SELECT (sort(arr))[1] FROM arrays_to_sort; -- original
>>> Time: 990.199 ms
>>> postgres=# SELECT (sort(arr))[1] FROM arrays_to_sort; -- patched
>>> Time: 696.156 ms
>>>
>>> The benefit seems to be on the order of magnitude with 30% speedup.
>>>
>>> There's plenty of sorting by TransactionId, BlockNumber, OffsetNumber,
>>> Oid etc. But this sorting routines never show up in perf top or something
>>> like that.
>>>
>>> Seems like in most cases we do not spend much time in sorting. But
>>> specialization does not cost us much too, only some CPU cycles of a
>>> compiler. I think we can further improve speedup by converting inline
>>> comparator to value extractor: more compilers will see what is actually
>>> going on. But I have no proofs for this reasoning.
>>>
>>> What do you think?
>>>
>>>
>>> Best regards, Andrey Borodin.
>>>
>>> [0]
>>> https://www.postgresql.org/message-id/flat/20240209184014.sobshkcsfjix6u4r%40awork3.anarazel.de#fc23df2cf314bef35095b632380b4a59
>>
>>
> Hello all.
>
> I have decided to explore more areas in which I can optimize and have
> added two new benchmarks. Do you have any thoughts on this?
>
> postgres=# select bench_int16_sort(1000000);
> bench_int16_sort
>
>
> -----------------------------------------------------------------------------------------------------------------
> Time taken by usual sort: 66354981 ns, Time taken by optimized sort:
> 52151523 ns, Percentage difference: 21.41%
> (1 row)
>
> postgres=# select bench_float8_sort(1000000);
> bench_float8_sort
>
>
> ------------------------------------------------------------------------------------------------------------------
> Time taken by usual sort: 121475231 ns, Time taken by optimized sort:
> 74458545 ns, Percentage difference: 38.70%
> (1 row)
>
> postgres=#
>
> Best regards, Stepan Neretin.
>