Hi, Yuya Watari presented a series of patches, with the objective of improving the Bitmapset [1]. After reading through the patches, I saw a lot of good ideas and thought I'd help. Unfortunately, my suggestions were not well received. Even so, I decided to work on these patches and see what could be improved.
Eventually it arrived at the attached patch, which I'm naming v7, because of the sequence it had established. Those who follow the other thread will see that the original patch actually improves the overall performance of Bitmapset, but I believe there is room for further improvement. I ran the same tests provided by Yuya Watari and the results are attached. Both on Windows and Linux Ubuntu, the performance of v7 outperforms head and v4. At Ubuntu 64 bits: v7 outperforms v4 by 29% (Query A) v7 outperforms v4 by 19% (Query B) At Windows 64 bits: v7 outperforms v4 by 22% (Query A) v7 outperforms v4 by 33% (Query B) I believe patch v7 leaves the Bitmapset in good shape and readable, well written. Questions arose regarding possible regression when using the backward loop, but in all the tests I ran this version with backward performed better. Possibly because of the smaller number of variables and the efficient test (--i <= 0), which both the msvc and gcc compilers successfully optimize. If the v7 version with loop forward performs worse on x86_64 cpus, I don't see how it will perform better on other architectures, since the vast majority of modern ones and with great cache support. Another question is related to an alleged "spurius test", whose objective is to avoid test and set instructions for each element of the array. Again I ran the tests without the test and the performance was worse, showing its value. regards, Ranier Vilela [1] https://www.postgresql.org/message-id/CAJ2pMkZ0HfhfA0QNa_msknL%3D_-PavZmPHRWnW7yOb3_PWUoB%2Bg%40mail.gmail.com
bench_bitmapset == Query A == psql -U postgres -f c:\postgres_bench\tmp\bitmapset\create-tables-a.sql psql -U postgres -f c:\postgres_bench\tmp\bitmapset\query-a.sql ============= head: Time: 3501,780 ms (00:03,502) Time: 3489,097 ms (00:03,489) Time: 3481,080 ms (00:03,481) Time: 3480,050 ms (00:03,480) patched v4: Time: 2305,445 ms (00:02,305) Time: 2185,972 ms (00:02,186) Time: 2177,434 ms (00:02,177) Time: 2169,883 ms (00:02,170) patched v7 (backward): Time: 1889,757 ms (00:01,890) Time: 1895,982 ms (00:01,896) Time: 1893,659 ms (00:01,894) Time: 1892,793 ms (00:01,893) patched v7 (forward) Time: 2133,026 ms (00:02,133) Time: 2150,171 ms (00:02,150) Time: 2123,655 ms (00:02,124) Time: 2118,278 ms (00:02,118) == Query B == psql -U postgres -f c:\postgres_bench\tmp\bitmapset\create-tables-b.sql psql -U postgres -f c:\postgres_bench\tmp\bitmapset\query-b.sql patched v4: Time: 2684,360 ms (00:02,684) Time: 2482,571 ms (00:02,483) Time: 2452,699 ms (00:02,453) Time: 2465,223 ms (00:02,465) patched v7 (backward): Time: 2006,757 ms (00:02,007) Time: 1777,995 ms (00:01,778) Time: 1786,364 ms (00:01,786) Time: 1778,891 ms (00:01,779) patched v7 (forward) Time: 2521,442 ms (00:02,521) Time: 2452,695 ms (00:02,453) Time: 2449,300 ms (00:02,449) Time: 2439,535 ms (00:02,440)
speeding-up-bitmapset-v7.patch
Description: Binary data
create-tables-a.sql
Description: Binary data
linux Ubuntu 64 bit gcc 64 bits == Query A == /usr/local/pgsql/bin/psql -U postgres -f /home/ranier/Documentos/benchmarks/bitmapset/create-tables-a.sql /usr/local/pgsql/bin/psql -U postgres -f /home/ranier/Documentos/benchmarks/bitmapset/query-a.sql ============= head: Time: 1809,993 ms (00:01,810) Time: 1772,793 ms (00:01,773) Time: 1769,734 ms (00:01,770) patched v4: Time: 933,181 ms Time: 931,520 ms Time: 906,496 ms Time: 872,446 ms patched v7 (backward): Time: 721,305 ms Time: 720,289 ms Time: 716,932 ms Time: 715,405 ms patched v7 (forward): Time: 978,344 ms Time: 942,889 ms Time: 878,150 ms Time: 877,747 ms patched v7 (without "spurious test"): Time: 790,336 ms Time: 788,384 ms Time: 787,970 ms Time: 787,040 ms == Query B == /usr/local/pgsql/bin/psql -U postgres -f /home/ranier/Documentos/benchmarks/bitmapset/create-tables-b.sql /usr/local/pgsql/bin/psql -U postgres -f /home/ranier/Documentos/benchmarks/bitmapset/query-b.sql patched v4: Time: 1581,317 ms (00:01,581) Time: 1568,371 ms (00:01,568) Time: 1468,036 ms (00:01,468) Time: 1445,698 ms (00:01,446) patched v7 (backward): Time: 1326,782 ms (00:01,327) Time: 1322,362 ms (00:01,322) Time: 1321,670 ms (00:01,322) Time: 1319,427 ms (00:01,319) patched v7 (forward): Time: 1487,447 ms (00:01,487) Time: 1477,957 ms (00:01,478) Time: 1470,305 ms (00:01,470) Time: 1466,994 ms (00:01,467) patched v7 (without "spurious test"): Time: 1458,915 ms (00:01,459) Time: 1455,686 ms (00:01,456) Time: 1451,509 ms (00:01,452) Time: 1444,873 ms (00:01,445)
bench_bitmapset_ubuntu.ods
Description: application/vnd.oasis.opendocument.spreadsheet
bench_bitmapset_windows.ods
Description: application/vnd.oasis.opendocument.spreadsheet
create-tables-b.sql
Description: Binary data
query-a.sql
Description: Binary data
Linux Ubuntu 64 bits gcc 64 bits pgbench -U postgres -i -p 5432 -d postgres patched v7: /usr/local/pgsql/bin/pgbench -M prepared -c 10 -T 60 -S -n -U postgres -d postgres transaction type: <builtin: select only> scaling factor: 1 query mode: prepared number of clients: 10 number of threads: 1 maximum number of tries: 1 duration: 60 s number of transactions actually processed: 1106867 number of failed transactions: 0 (0.000%) latency average = 0.542 ms initial connection time = 16.517 ms tps = 18452.786191 (without initial connection time) /usr/local/pgsql/bin/pgbench -M prepared -c 50 -T 60 -S -n -U postgres -d postgres transaction type: <builtin: select only> scaling factor: 1 query mode: prepared number of clients: 50 number of threads: 1 maximum number of tries: 1 duration: 60 s number of transactions actually processed: 1047478 number of failed transactions: 0 (0.000%) latency average = 2.860 ms initial connection time = 81.995 ms tps = 17481.067898 (without initial connection time) /usr/local/pgsql/bin/pgbench -M prepared -c 100 -T 60 -S -n -U postgres -d postgres transaction type: <builtin: select only> scaling factor: 1 query mode: prepared number of clients: 100 number of threads: 1 maximum number of tries: 1 duration: 60 s number of transactions actually processed: 1018827 number of failed transactions: 0 (0.000%) latency average = 5.875 ms initial connection time = 156.956 ms tps = 17020.459142 (without initial connection time) head: /usr/local/pgsql/bin/pgbench -M prepared -c 10 -T 60 -S -n -U postgres -d postgres transaction type: <builtin: select only> scaling factor: 1 query mode: prepared number of clients: 10 number of threads: 1 maximum number of tries: 1 duration: 60 s number of transactions actually processed: 1096969 number of failed transactions: 0 (0.000%) latency average = 0.547 ms initial connection time = 16.791 ms tps = 18287.865642 (without initial connection time) /usr/local/pgsql/bin/pgbench -M prepared -c 50 -T 60 -S -n -U postgres -d postgres transaction type: <builtin: select only> scaling factor: 1 query mode: prepared number of clients: 50 number of threads: 1 maximum number of tries: 1 duration: 60 s number of transactions actually processed: 1030486 number of failed transactions: 0 (0.000%) latency average = 2.907 ms initial connection time = 80.533 ms tps = 17197.568349 (without initial connection time) /usr/local/pgsql/bin/pgbench -M prepared -c 100 -T 60 -S -n -U postgres -d postgres transaction type: <builtin: select only> scaling factor: 1 query mode: prepared number of clients: 100 number of threads: 1 maximum number of tries: 1 duration: 60 s number of transactions actually processed: 993385 number of failed transactions: 0 (0.000%) latency average = 6.024 ms initial connection time = 157.635 ms tps = 16599.447414 (without initial connection time)
query-b.sql
Description: Binary data
