Re: Sort functions with specialized comparators
On Tue, Jul 16, 2024 at 1:47 AM Andrey M. Borodin wrote: > > > > On 15 Jul 2024, at 12:52, Stepan Neretin wrote: > > > > > > I run benchmark with my patches: > > ./pgbench -c 10 -j2 -t1000 -d postgres > > > > pgbench (18devel) > > starting vacuum...end. > > transaction type: > > scaling factor: 10 > > query mode: simple > > number of clients: 10 > > number of threads: 2 > > maximum number of tries: 1 > > number of transactions per client: 1000 > > number of transactions actually processed: 1/1 > > number of failed transactions: 0 (0.000%) > > latency average = 1.609 ms > > initial connection time = 24.080 ms > > tps = 6214.244789 (without initial connection time) > > > > and without: > > ./pgbench -c 10 -j2 -t1000 -d postgres > > > > pgbench (18devel) > > starting vacuum...end. > > transaction type: > > scaling factor: 10 > > query mode: simple > > number of clients: 10 > > number of threads: 2 > > maximum number of tries: 1 > > number of transactions per client: 1000 > > number of transactions actually processed: 1/1 > > number of failed transactions: 0 (0.000%) > > latency average = 1.731 ms > > initial connection time = 15.177 ms > > tps = 5776.173285 (without initial connection time) > > > > tps with my patches increase. What do you think? > > > Hi Stepan! > > Thank you for implementing specialized sorting and doing this benchmarks. > I believe it's a possible direction for good improvement. > However, I doubt in correctness of your benchmarks. > Increasing TPC-B performance from 5776 TPS to 6214 TPS seems too good to > be true. > > > Best regards, Andrey Borodin. Yes... I agree.. Very strange.. I restarted the tps measurement and see this: tps = 14291.893460 (without initial connection time) not patched tps = 14669.624075 (without initial connection time) patched What do you think about these measurements? Best regards, Stepan Neretin.
Re: Sort functions with specialized comparators
> On 15 Jul 2024, at 12:52, Stepan Neretin wrote: > > > I run benchmark with my patches: > ./pgbench -c 10 -j2 -t1000 -d postgres > > pgbench (18devel) > starting vacuum...end. > transaction type: > scaling factor: 10 > query mode: simple > number of clients: 10 > number of threads: 2 > maximum number of tries: 1 > number of transactions per client: 1000 > number of transactions actually processed: 1/1 > number of failed transactions: 0 (0.000%) > latency average = 1.609 ms > initial connection time = 24.080 ms > tps = 6214.244789 (without initial connection time) > > and without: > ./pgbench -c 10 -j2 -t1000 -d postgres > > pgbench (18devel) > starting vacuum...end. > transaction type: > scaling factor: 10 > query mode: simple > number of clients: 10 > number of threads: 2 > maximum number of tries: 1 > number of transactions per client: 1000 > number of transactions actually processed: 1/1 > number of failed transactions: 0 (0.000%) > latency average = 1.731 ms > initial connection time = 15.177 ms > tps = 5776.173285 (without initial connection time) > > tps with my patches increase. What do you think? Hi Stepan! Thank you for implementing specialized sorting and doing this benchmarks. I believe it's a possible direction for good improvement. However, I doubt in correctness of your benchmarks. Increasing TPC-B performance from 5776 TPS to 6214 TPS seems too good to be true. Best regards, Andrey Borodin.
Re: Sort functions with specialized comparators
On Mon, Jul 15, 2024 at 4:52 PM Stepan Neretin wrote: > > > On Mon, Jul 15, 2024 at 12:23 PM Антуан Виолин > wrote: > >> 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(100); >>> 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(100); >>> 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 >> wrote: >> >>> >>> >>> On Sat, Jun 8, 2024 at 1:50 AM Stepan Neretin 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(100); 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(100); 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 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, 100)) 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(100); >>> 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(100); >>> bench_float8_sort >>> >>> >>>
Re: Sort functions with specialized comparators
On Mon, Jul 15, 2024 at 12:23 PM Антуан Виолин wrote: > 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(100); >> 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(100); >> 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 wrote: > >> >> >> On Sat, Jun 8, 2024 at 1:50 AM Stepan Neretin 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(100); >>> 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(100); >>> 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 >>> 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, 100)) 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(100); >> 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(100); >> bench_float8_sort >> >> >> -- >> Time taken by usual sort: 121475231 ns, Time taken by optimized sort: >> 74458545 ns, Percentage difference: 38.70% >> (1 row) >> >> postgres=# >> >>
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(100); > 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(100); > 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 wrote: > > > On Sat, Jun 8, 2024 at 1:50 AM Stepan Neretin 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(100); >> 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(100); >> 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 >> 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, 100)) 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(100); > 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(100); > 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. >
Re: Sort functions with specialized comparators
On Sat, Jun 8, 2024 at 1:50 AM Stepan Neretin 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(100); > 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(100); > 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 > 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, 100)) 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(100); 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(100); 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. From a3c03ee1b4f6d94d6bf2dc8700c30349271ef9b3 Mon Sep 17 00:00:00 2001 From: Stepan Neretin Date: Tue, 11 Jun 2024 12:02:48 +0700 Subject: [PATCH v42 08/12] Refactor sorting of attribute numbers in pg_publication.c and statscmds.c This commit refactors the sorting of attribute numbers in two modules: pg_publication.c and statscmds.c. Instead of using the qsort function with a custom compare function, it utilizes the recently introduced sort_int_16_arr function, which offers enhanced performance for sorting int16 arrays. Details: - Replaced qsort calls with sort_int_16_arr for sorting attribute numbers. - Improved efficiency by utilizing the sorting template for int16 arrays. This change ensures consistency in sorting methods and enhances sorting performance in relevant modules. --- src/backend/catalog/pg_publication.c | 2 +- src/backend/commands/statscmds.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/backend/catalog/pg_publication.c b/src/backend/catalog/pg_publication.c index 8518582b76..196f696c1e 100644 --- a/src/backend/catalog/pg_publication.c +++ b/src/backend/catalog/pg_publication.c @@ -540,7 +540,7 @@ publication_translate_columns(Relation targetrel, List *columns, } /* Be tidy, so that the catalog representation is always sorted */ - qsort(attarray, n, sizeof(AttrNumber), compare_int16); + sort_int_16_arr(attarray, n); *natts = n; *attrs = attarray;
Re: Sort functions with specialized comparators
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(100); 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(100); 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 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, 100)) 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 > From 74bad4bbcff9ea4a9a68f91618c84854dab24701 Mon Sep 17 00:00:00 2001 From: Stepan Neretin Date: Sat, 8 Jun 2024 01:29:42 +0700 Subject: [PATCH v42 6/6] Implemented benchmarking for optimized sorting This commit adds benchmarking functions to compare the performance of two list sorting operations: bench_int_sort and bench_oid_sort. These functions measure the execution time of sorting lists of integers and OIDs, respectively, using different algorithms (list_sort and custom sorting functions). Random lists of specified sizes are generated, sorted using both methods, and their execution times are recorded. The percentage difference in execution time between the two methods is also calculated. This commit aims to provide insights into the efficiency of the sorting algorithms used. --- contrib/Makefile | 1 + contrib/bench_sort_improvements/Makefile | 20 contrib/bench_sort_improvements/bench.c | 105 ++ .../bench_sort_improvements--1.0.sql | 3 + .../bench_sort_improvements.control | 5 + 5 files changed, 134 insertions(+) create mode 100644 contrib/bench_sort_improvements/Makefile create mode 100644 contrib/bench_sort_improvements/bench.c create mode 100644 contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql create mode 100644 contrib/bench_sort_improvements/bench_sort_improvements.control diff --git a/contrib/Makefile b/contrib/Makefile index abd780f277..a1ee9defc2 100644 --- a/contrib/Makefile +++ b/contrib/Makefile @@ -10,6 +10,7 @@ SUBDIRS = \ auto_explain \ basic_archive \ basebackup_to_shell \ + bench_sort_improvements \ bloom \ btree_gin \ btree_gist \ diff --git a/contrib/bench_sort_improvements/Makefile b/contrib/bench_sort_improvements/Makefile new file mode 100644 index 00..46458ee76c --- /dev/null +++ b/contrib/bench_sort_improvements/Makefile @@ -0,0 +1,20 @@ +MODULE_big = bench_sort_improvements + +OBJS = \ + $(WIN32RES) \ + bench.o + +EXTENSION = bench_sort_improvements + +DATA = bench_sort_improvements--1.0.sql + +ifdef USE_PGXS +PG_CONFIG = pg_config +PGXS := $(shell $(PG_CONFIG) --pgxs) +include $(PGXS) +else +subdir = contrib/bench_sort_improvements +top_builddir = ../.. +include $(top_builddir)/src/Makefile.global +include $(top_srcdir)/contrib/contrib-global.mk +endif diff --git a/contrib/bench_sort_improvements/bench.c b/contrib/bench_sort_improvements/bench.c new file mode
Re: Sort functions with specialized comparators
Em sáb., 18 de mai. de 2024 às 15:52, Andrey M. Borodin < x4...@yandex-team.ru> escreveu: > 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, 100)) 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? > Makes sense. Regarding the patch. You could change the style to: +sort_int32_asc_cmp(const int32 *a, const int32 *b) +sort_int32_desc_cmp(const int32 *a, const int32 *b) We must use const in all parameters that can be const. best regards, Ranier Vilela
Sort functions with specialized comparators
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, 100)) 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 v1-0001-Use-specialized-sort-facilities.patch Description: Binary data
