On Wed, Jan 3, 2024 at 10:12 PM John Naylor <johncnaylo...@gmail.com> wrote: > > On Tue, Jan 2, 2024 at 6:56 AM jian he <jian.universal...@gmail.com> wrote: > > > > My local computer is slow. but here is the test results: > > > > select * from bench_cstring_hash_aligned(100000); 7318.893 ms > > select * from bench_cstring_hash_unaligned(100000); 10383.173 ms > > select * from bench_pgstat_hash(100000); 4474.989 ms > > select * from bench_pgstat_hash_fh(100000); 9192.245 ms > > select * from bench_string_hash(100000); 2048.008 ms > > This presents a 2x to 5x slowdown, so I'm skeptical this is typical -- > what kind of platform is. For starters, what CPU and compiler?
I still cannot git apply your patch cleanly. in http://cfbot.cputube.org/ i cannot find your patch. ( so, it might be that I test based on incomplete information). but only hashfn_unstable.h influences bench_hash/bench_hash.c. so I attached the whole patch that I had git applied, that is the changes i applied for the following tests. how I test using pgbench: pgbench --no-vacuum --time=20 --file /home/jian/tmp/bench_cstring_hash_aligned.sql -M prepared | grep latency The following is tested with another machine, also listed machine spec below. I tested 3 times, the results is very similar as following: select * from bench_cstring_hash_aligned(100000); 4705.686 ms select * from bench_cstring_hash_unaligned(100000); 6835.753 ms select * from bench_pgstat_hash(100000); 2678.978 ms select * from bench_pgstat_hash_fh(100000); 6199.017 ms select * from bench_string_hash(100000); 847.699 ms src6=# select version(); version -------------------------------------------------------------------- PostgreSQL 17devel on x86_64-linux, compiled by gcc-11.4.0, 64-bit (1 row) jian@jian:~/Desktop/pg_src/src6/postgres$ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. lscpu: Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 46 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 20 On-line CPU(s) list: 0-19 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i5-14600K CPU family: 6 Model: 183 Thread(s) per core: 2 Core(s) per socket: 14 Socket(s): 1 Stepping: 1 CPU max MHz: 5300.0000 CPU min MHz: 800.0000 BogoMIPS: 6988.80 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp l m constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vm x smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetc h cpuid_fault ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsavec xgetbv1 xsaves split_lock_detect avx_vnni dtherm ida arat pln pts hwp hwp_notify hw p_act_window hwp_epp hwp_pkg_req hfi umip pku ospke waitpkg gfni vaes vpclmulqdq tme rdpid movdiri movdir64b fsrm md_clear serialize pconfig arch_l br ibt flush_l1d arch_capabilities Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 544 KiB (14 instances) L1i: 704 KiB (14 instances) L2: 20 MiB (8 instances) L3: 24 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-19 Vulnerabilities: Gather data sampling: Not affected Itlb multihit: Not affected L1tf: Not affected Mds: Not affected Meltdown: Not affected Mmio stale data: Not affected Retbleed: Not affected Spec rstack overflow: Not affected Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization Spectre v2: Mitigation; Enhanced IBRS, IBPB conditional, RSB filling, PBRSB-eIBRS SW sequence Srbds: Not affected Tsx async abort: Not affected jian@jian:~/Desktop/pg_src/src6/postgres$ git log commit bbbf8cd54a05ad5c92e79c96133f219e80fad77c (HEAD -> master) Author: jian he <jian.universal...@gmail.com> Date: Thu Jan 4 10:32:39 2024 +0800 bench_hash contrib module commit c5385929593dd8499cfb5d85ac322e8ee1819fd4 Author: Peter Eisentraut <pe...@eisentraut.org> Date: Fri Dec 29 18:01:53 2023 +0100 Make all Perl warnings fatal
From bbbf8cd54a05ad5c92e79c96133f219e80fad77c Mon Sep 17 00:00:00 2001 From: jian he <jian.universal...@gmail.com> Date: Thu, 4 Jan 2024 10:32:39 +0800 Subject: [PATCH v12 1/1] bench_hash contrib module --- .vscode/settings.json | 9 + contrib/bench_hash/Makefile | 23 + contrib/bench_hash/aligned_keywords.h | 991 +++++++++++++++++++++++++ contrib/bench_hash/bench_hash--1.0.sql | 30 + contrib/bench_hash/bench_hash.c | 169 +++++ contrib/bench_hash/bench_hash.control | 5 + contrib/bench_hash/meson.build | 19 + contrib/meson.build | 1 + src/backend/catalog/namespace.c | 28 +- src/include/common/hashfn_unstable.h | 309 ++++++++ src/include/utils/pgstat_internal.h | 9 +- src/tools/pgindent/typedefs.list | 1 + 12 files changed, 1583 insertions(+), 11 deletions(-) create mode 100644 .vscode/settings.json create mode 100644 contrib/bench_hash/Makefile create mode 100644 contrib/bench_hash/aligned_keywords.h create mode 100644 contrib/bench_hash/bench_hash--1.0.sql create mode 100644 contrib/bench_hash/bench_hash.c create mode 100644 contrib/bench_hash/bench_hash.control create mode 100644 contrib/bench_hash/meson.build create mode 100644 src/include/common/hashfn_unstable.h diff --git a/.vscode/settings.json b/.vscode/settings.json new file mode 100644 index 00000000..c83feba3 --- /dev/null +++ b/.vscode/settings.json @@ -0,0 +1,9 @@ +{ + "files.associations": { + "pg_bitutils.h": "c", + "hashfn_unstable.h": "c", + "hashfn.h": "c", + "memutils.h": "c", + "pgstat_internal.h": "c" + } +} \ No newline at end of file diff --git a/contrib/bench_hash/Makefile b/contrib/bench_hash/Makefile new file mode 100644 index 00000000..53270803 --- /dev/null +++ b/contrib/bench_hash/Makefile @@ -0,0 +1,23 @@ +# src/test/modules/test_parser/Makefile + +MODULE_big = test_parser +OBJS = \ + $(WIN32RES) \ + test_parser.o +PGFILEDESC = "test_parser - example of a custom parser for full-text search" + +EXTENSION = test_parser +DATA = test_parser--1.0.sql + +REGRESS = test_parser + +ifdef USE_PGXS +PG_CONFIG = pg_config +PGXS := $(shell $(PG_CONFIG) --pgxs) +include $(PGXS) +else +subdir = src/test/modules/test_parser +top_builddir = ../../../.. +include $(top_builddir)/src/Makefile.global +include $(top_srcdir)/contrib/contrib-global.mk +endif diff --git a/contrib/bench_hash/aligned_keywords.h b/contrib/bench_hash/aligned_keywords.h new file mode 100644 index 00000000..c2bd67c8 --- /dev/null +++ b/contrib/bench_hash/aligned_keywords.h @@ -0,0 +1,991 @@ +/* created by copying from kwlist_d.h with this patch: + +--- a/src/tools/gen_keywordlist.pl ++++ b/src/tools/gen_keywordlist.pl +@@ -97,7 +97,9 @@ while (<$kif>) + { + if (/^PG_KEYWORD\("(\w+)"/) + { +- push @keywords, $1; ++ my $len = length($1) + 1; ++ my $aligned = $1 . "\\0" . "_" x ( ($len % 8) == 0 ? 0 : (8-($len % 8)) ); ++ push @keywords, $aligned; + } + } + +@@ -127,7 +129,7 @@ for my $i (0 .. $#keywords - 1) + # Emit the string containing all the keywords. + + printf $kwdef qq|static const char %s_kw_string[] =\n\t"|, $varname; +-print $kwdef join qq|\\0"\n\t"|, @keywords; ++print $kwdef join qq|"\n\t"|, @keywords; + print $kwdef qq|";\n\n|; + + # Emit an array of numerical offsets which will be used to index into the +@@ -145,7 +147,7 @@ foreach my $name (@keywords) + + # Calculate the cumulative offset of the next keyword, + # taking into account the null terminator. +- $offset += $this_length + 1; ++ $offset += $this_length -1; + + # Update max keyword length. + $max_len = $this_length if $max_len < $this_length; + +*/ + + +static const char aligned_words[] = + "abort\0__" + "absent\0_" + "absolute\0_______" + "access\0_" + "action\0_" + "add\0____" + "admin\0__" + "after\0__" + "aggregate\0______" + "all\0____" + "also\0___" + "alter\0__" + "always\0_" + "analyse\0" + "analyze\0" + "and\0____" + "any\0____" + "array\0__" + "as\0_____" + "asc\0____" + "asensitive\0_____" + "assertion\0______" + "assignment\0_____" + "asymmetric\0_____" + "at\0_____" + "atomic\0_" + "attach\0_" + "attribute\0______" + "authorization\0__" + "backward\0_______" + "before\0_" + "begin\0__" + "between\0" + "bigint\0_" + "binary\0_" + "bit\0____" + "boolean\0" + "both\0___" + "breadth\0" + "by\0_____" + "cache\0__" + "call\0___" + "called\0_" + "cascade\0" + "cascaded\0_______" + "case\0___" + "cast\0___" + "catalog\0" + "chain\0__" + "char\0___" + "character\0______" + "characteristics\0" + "check\0__" + "checkpoint\0_____" + "class\0__" + "close\0__" + "cluster\0" + "coalesce\0_______" + "collate\0" + "collation\0______" + "column\0_" + "columns\0" + "comment\0" + "comments\0_______" + "commit\0_" + "committed\0______" + "compression\0____" + "concurrently\0___" + "configuration\0__" + "conflict\0_______" + "connection\0_____" + "constraint\0_____" + "constraints\0____" + "content\0" + "continue\0_______" + "conversion\0_____" + "copy\0___" + "cost\0___" + "create\0_" + "cross\0__" + "csv\0____" + "cube\0___" + "current\0" + "current_catalog\0" + "current_date\0___" + "current_role\0___" + "current_schema\0_" + "current_time\0___" + "current_timestamp\0______" + "current_user\0___" + "cursor\0_" + "cycle\0__" + "data\0___" + "database\0_______" + "day\0____" + "deallocate\0_____" + "dec\0____" + "decimal\0" + "declare\0" + "default\0" + "defaults\0_______" + "deferrable\0_____" + "deferred\0_______" + "definer\0" + "delete\0_" + "delimiter\0______" + "delimiters\0_____" + "depends\0" + "depth\0__" + "desc\0___" + "detach\0_" + "dictionary\0_____" + "disable\0" + "discard\0" + "distinct\0_______" + "do\0_____" + "document\0_______" + "domain\0_" + "double\0_" + "drop\0___" + "each\0___" + "else\0___" + "enable\0_" + "encoding\0_______" + "encrypted\0______" + "end\0____" + "enum\0___" + "escape\0_" + "event\0__" + "except\0_" + "exclude\0" + "excluding\0______" + "exclusive\0______" + "execute\0" + "exists\0_" + "explain\0" + "expression\0_____" + "extension\0______" + "external\0_______" + "extract\0" + "false\0__" + "family\0_" + "fetch\0__" + "filter\0_" + "finalize\0_______" + "first\0__" + "float\0__" + "following\0______" + "for\0____" + "force\0__" + "foreign\0" + "format\0_" + "forward\0" + "freeze\0_" + "from\0___" + "full\0___" + "function\0_______" + "functions\0______" + "generated\0______" + "global\0_" + "grant\0__" + "granted\0" + "greatest\0_______" + "group\0__" + "grouping\0_______" + "groups\0_" + "handler\0" + "having\0_" + "header\0_" + "hold\0___" + "hour\0___" + "identity\0_______" + "if\0_____" + "ilike\0__" + "immediate\0______" + "immutable\0______" + "implicit\0_______" + "import\0_" + "in\0_____" + "include\0" + "including\0______" + "increment\0______" + "indent\0_" + "index\0__" + "indexes\0" + "inherit\0" + "inherits\0_______" + "initially\0______" + "inline\0_" + "inner\0__" + "inout\0__" + "input\0__" + "insensitive\0____" + "insert\0_" + "instead\0" + "int\0____" + "integer\0" + "intersect\0______" + "interval\0_______" + "into\0___" + "invoker\0" + "is\0_____" + "isnull\0_" + "isolation\0______" + "join\0___" + "json\0___" + "json_array\0_____" + "json_arrayagg\0__" + "json_object\0____" + "json_objectagg\0_" + "json_scalar\0____" + "json_serialize\0_" + "key\0____" + "keys\0___" + "label\0__" + "language\0_______" + "large\0__" + "last\0___" + "lateral\0" + "leading\0" + "leakproof\0______" + "least\0__" + "left\0___" + "level\0__" + "like\0___" + "limit\0__" + "listen\0_" + "load\0___" + "local\0__" + "localtime\0______" + "localtimestamp\0_" + "location\0_______" + "lock\0___" + "locked\0_" + "logged\0_" + "mapping\0" + "match\0__" + "matched\0" + "materialized\0___" + "maxvalue\0_______" + "merge\0__" + "method\0_" + "minute\0_" + "minvalue\0_______" + "mode\0___" + "month\0__" + "move\0___" + "name\0___" + "names\0__" + "national\0_______" + "natural\0" + "nchar\0__" + "new\0____" + "next\0___" + "nfc\0____" + "nfd\0____" + "nfkc\0___" + "nfkd\0___" + "no\0_____" + "none\0___" + "normalize\0______" + "normalized\0_____" + "not\0____" + "nothing\0" + "notify\0_" + "notnull\0" + "nowait\0_" + "null\0___" + "nullif\0_" + "nulls\0__" + "numeric\0" + "object\0_" + "of\0_____" + "off\0____" + "offset\0_" + "oids\0___" + "old\0____" + "on\0_____" + "only\0___" + "operator\0_______" + "option\0_" + "options\0" + "or\0_____" + "order\0__" + "ordinality\0_____" + "others\0_" + "out\0____" + "outer\0__" + "over\0___" + "overlaps\0_______" + "overlay\0" + "overriding\0_____" + "owned\0__" + "owner\0__" + "parallel\0_______" + "parameter\0______" + "parser\0_" + "partial\0" + "partition\0______" + "passing\0" + "password\0_______" + "placing\0" + "plans\0__" + "policy\0_" + "position\0_______" + "preceding\0______" + "precision\0______" + "prepare\0" + "prepared\0_______" + "preserve\0_______" + "primary\0" + "prior\0__" + "privileges\0_____" + "procedural\0_____" + "procedure\0______" + "procedures\0_____" + "program\0" + "publication\0____" + "quote\0__" + "range\0__" + "read\0___" + "real\0___" + "reassign\0_______" + "recheck\0" + "recursive\0______" + "ref\0____" + "references\0_____" + "referencing\0____" + "refresh\0" + "reindex\0" + "relative\0_______" + "release\0" + "rename\0_" + "repeatable\0_____" + "replace\0" + "replica\0" + "reset\0__" + "restart\0" + "restrict\0_______" + "return\0_" + "returning\0______" + "returns\0" + "revoke\0_" + "right\0__" + "role\0___" + "rollback\0_______" + "rollup\0_" + "routine\0" + "routines\0_______" + "row\0____" + "rows\0___" + "rule\0___" + "savepoint\0______" + "scalar\0_" + "schema\0_" + "schemas\0" + "scroll\0_" + "search\0_" + "second\0_" + "security\0_______" + "select\0_" + "sequence\0_______" + "sequences\0______" + "serializable\0___" + "server\0_" + "session\0" + "session_user\0___" + "set\0____" + "setof\0__" + "sets\0___" + "share\0__" + "show\0___" + "similar\0" + "simple\0_" + "skip\0___" + "smallint\0_______" + "snapshot\0_______" + "some\0___" + "sql\0____" + "stable\0_" + "standalone\0_____" + "start\0__" + "statement\0______" + "statistics\0_____" + "stdin\0__" + "stdout\0_" + "storage\0" + "stored\0_" + "strict\0_" + "strip\0__" + "subscription\0___" + "substring\0______" + "support\0" + "symmetric\0______" + "sysid\0__" + "system\0_" + "system_user\0____" + "table\0__" + "tables\0_" + "tablesample\0____" + "tablespace\0_____" + "temp\0___" + "template\0_______" + "temporary\0______" + "text\0___" + "then\0___" + "ties\0___" + "time\0___" + "timestamp\0______" + "to\0_____" + "trailing\0_______" + "transaction\0____" + "transform\0______" + "treat\0__" + "trigger\0" + "trim\0___" + "true\0___" + "truncate\0_______" + "trusted\0" + "type\0___" + "types\0__" + "uescape\0" + "unbounded\0______" + "uncommitted\0____" + "unencrypted\0____" + "union\0__" + "unique\0_" + "unknown\0" + "unlisten\0_______" + "unlogged\0_______" + "until\0__" + "update\0_" + "user\0___" + "using\0__" + "vacuum\0_" + "valid\0__" + "validate\0_______" + "validator\0______" + "value\0__" + "values\0_" + "varchar\0" + "variadic\0_______" + "varying\0" + "verbose\0" + "version\0" + "view\0___" + "views\0__" + "volatile\0_______" + "when\0___" + "where\0__" + "whitespace\0_____" + "window\0_" + "with\0___" + "within\0_" + "without\0" + "work\0___" + "wrapper\0" + "write\0__" + "xml\0____" + "xmlattributes\0__" + "xmlconcat\0______" + "xmlelement\0_____" + "xmlexists\0______" + "xmlforest\0______" + "xmlnamespaces\0__" + "xmlparse\0_______" + "xmlpi\0__" + "xmlroot\0" + "xmlserialize\0___" + "xmltable\0_______" + "year\0___" + "yes\0____" + "zone\0___"; + +static const uint16 word_offsets[] = { + 0, + 8, + 16, + 32, + 40, + 48, + 56, + 64, + 72, + 88, + 96, + 104, + 112, + 120, + 128, + 136, + 144, + 152, + 160, + 168, + 176, + 192, + 208, + 224, + 240, + 248, + 256, + 264, + 280, + 296, + 312, + 320, + 328, + 336, + 344, + 352, + 360, + 368, + 376, + 384, + 392, + 400, + 408, + 416, + 424, + 440, + 448, + 456, + 464, + 472, + 480, + 496, + 512, + 520, + 536, + 544, + 552, + 560, + 576, + 584, + 600, + 608, + 616, + 624, + 640, + 648, + 664, + 680, + 696, + 712, + 728, + 744, + 760, + 776, + 784, + 800, + 816, + 824, + 832, + 840, + 848, + 856, + 864, + 872, + 888, + 904, + 920, + 936, + 952, + 976, + 992, + 1000, + 1008, + 1016, + 1032, + 1040, + 1056, + 1064, + 1072, + 1080, + 1088, + 1104, + 1120, + 1136, + 1144, + 1152, + 1168, + 1184, + 1192, + 1200, + 1208, + 1216, + 1232, + 1240, + 1248, + 1264, + 1272, + 1288, + 1296, + 1304, + 1312, + 1320, + 1328, + 1336, + 1352, + 1368, + 1376, + 1384, + 1392, + 1400, + 1408, + 1416, + 1432, + 1448, + 1456, + 1464, + 1472, + 1488, + 1504, + 1520, + 1528, + 1536, + 1544, + 1552, + 1560, + 1576, + 1584, + 1592, + 1608, + 1616, + 1624, + 1632, + 1640, + 1648, + 1656, + 1664, + 1672, + 1688, + 1704, + 1720, + 1728, + 1736, + 1744, + 1760, + 1768, + 1784, + 1792, + 1800, + 1808, + 1816, + 1824, + 1832, + 1848, + 1856, + 1864, + 1880, + 1896, + 1912, + 1920, + 1928, + 1936, + 1952, + 1968, + 1976, + 1984, + 1992, + 2000, + 2016, + 2032, + 2040, + 2048, + 2056, + 2064, + 2080, + 2088, + 2096, + 2104, + 2112, + 2128, + 2144, + 2152, + 2160, + 2168, + 2176, + 2192, + 2200, + 2208, + 2224, + 2240, + 2256, + 2272, + 2288, + 2304, + 2312, + 2320, + 2328, + 2344, + 2352, + 2360, + 2368, + 2376, + 2392, + 2400, + 2408, + 2416, + 2424, + 2432, + 2440, + 2448, + 2456, + 2472, + 2488, + 2504, + 2512, + 2520, + 2528, + 2536, + 2544, + 2552, + 2568, + 2584, + 2592, + 2600, + 2608, + 2624, + 2632, + 2640, + 2648, + 2656, + 2664, + 2680, + 2688, + 2696, + 2704, + 2712, + 2720, + 2728, + 2736, + 2744, + 2752, + 2760, + 2776, + 2792, + 2800, + 2808, + 2816, + 2824, + 2832, + 2840, + 2848, + 2856, + 2864, + 2872, + 2880, + 2888, + 2896, + 2904, + 2912, + 2920, + 2928, + 2944, + 2952, + 2960, + 2968, + 2976, + 2992, + 3000, + 3008, + 3016, + 3024, + 3040, + 3048, + 3064, + 3072, + 3080, + 3096, + 3112, + 3120, + 3128, + 3144, + 3152, + 3168, + 3176, + 3184, + 3192, + 3208, + 3224, + 3240, + 3248, + 3264, + 3280, + 3288, + 3296, + 3312, + 3328, + 3344, + 3360, + 3368, + 3384, + 3392, + 3400, + 3408, + 3416, + 3432, + 3440, + 3456, + 3464, + 3480, + 3496, + 3504, + 3512, + 3528, + 3536, + 3544, + 3560, + 3568, + 3576, + 3584, + 3592, + 3608, + 3616, + 3632, + 3640, + 3648, + 3656, + 3664, + 3680, + 3688, + 3696, + 3712, + 3720, + 3728, + 3736, + 3752, + 3760, + 3768, + 3776, + 3784, + 3792, + 3800, + 3816, + 3824, + 3840, + 3856, + 3872, + 3880, + 3888, + 3904, + 3912, + 3920, + 3928, + 3936, + 3944, + 3952, + 3960, + 3968, + 3984, + 4000, + 4008, + 4016, + 4024, + 4040, + 4048, + 4064, + 4080, + 4088, + 4096, + 4104, + 4112, + 4120, + 4128, + 4144, + 4160, + 4168, + 4184, + 4192, + 4200, + 4216, + 4224, + 4232, + 4248, + 4264, + 4272, + 4288, + 4304, + 4312, + 4320, + 4328, + 4336, + 4352, + 4360, + 4376, + 4392, + 4408, + 4416, + 4424, + 4432, + 4440, + 4456, + 4464, + 4472, + 4480, + 4488, + 4504, + 4520, + 4536, + 4544, + 4552, + 4560, + 4576, + 4592, + 4600, + 4608, + 4616, + 4624, + 4632, + 4640, + 4656, + 4672, + 4680, + 4688, + 4696, + 4712, + 4720, + 4728, + 4736, + 4744, + 4752, + 4768, + 4776, + 4784, + 4800, + 4808, + 4816, + 4824, + 4832, + 4840, + 4848, + 4856, + 4864, + 4880, + 4896, + 4912, + 4928, + 4944, + 4960, + 4976, + 4984, + 4992, + 5008, + 5024, + 5032, + 5040, +}; + + +#define SCANKEYWORDS_NUM_KEYWORDS 473 + diff --git a/contrib/bench_hash/bench_hash--1.0.sql b/contrib/bench_hash/bench_hash--1.0.sql new file mode 100644 index 00000000..43ce946b --- /dev/null +++ b/contrib/bench_hash/bench_hash--1.0.sql @@ -0,0 +1,30 @@ +/* src/test/modules/bench_hash/bench_hash--1.0.sql */ + +-- complain if script is sourced in psql, rather than via CREATE EXTENSION +\echo Use "CREATE EXTENSION bench_hash" to load this file. \quit + +CREATE FUNCTION bench_string_hash(int4) +RETURNS int +AS 'MODULE_PATHNAME' +LANGUAGE C STRICT; + + +CREATE FUNCTION bench_cstring_hash_unaligned(int4) +RETURNS int +AS 'MODULE_PATHNAME' +LANGUAGE C STRICT; + +CREATE FUNCTION bench_cstring_hash_aligned(int4) +RETURNS int +AS 'MODULE_PATHNAME' +LANGUAGE C STRICT; + +CREATE FUNCTION bench_pgstat_hash(int4) +RETURNS int +AS 'MODULE_PATHNAME' +LANGUAGE C STRICT; + +CREATE FUNCTION bench_pgstat_hash_FH(int4) +RETURNS int +AS 'MODULE_PATHNAME' +LANGUAGE C STRICT; diff --git a/contrib/bench_hash/bench_hash.c b/contrib/bench_hash/bench_hash.c new file mode 100644 index 00000000..017cf333 --- /dev/null +++ b/contrib/bench_hash/bench_hash.c @@ -0,0 +1,169 @@ +/*------------------------------------------------------------------------- + * + * bench_hash.c + * + * Copyright (c) 2023, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/test/modules/bench_hash/bench_hash.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "fmgr.h" + +PG_MODULE_MAGIC; + +#include "aligned_keywords.h" + +#include "common/hashfn.h" +#include "common/hashfn_unstable.h" +#include "miscadmin.h" +#include "utils/memutils.h" +#include "utils/pgstat_internal.h" + + +PG_FUNCTION_INFO_V1(bench_string_hash); +Datum +bench_string_hash(PG_FUNCTION_ARGS) +{ + int32 count = PG_GETARG_INT32(0); + uint32 hash = 0; + + while (count-- > 0) + { + for (int i=0; i< SCANKEYWORDS_NUM_KEYWORDS; i++) + { + int idx = word_offsets[i]; + int s_len = strlen(&aligned_words[idx]); + hash += hash_bytes((const unsigned char *) &aligned_words[idx], s_len); + } + CHECK_FOR_INTERRUPTS(); + } + + PG_RETURN_INT32(hash); +} + + +PG_FUNCTION_INFO_V1(bench_cstring_hash_unaligned); +Datum +bench_cstring_hash_unaligned(PG_FUNCTION_ARGS) +{ + int32 count = PG_GETARG_INT32(0); + uint32 hash = 0; + + char* p = (char*) palloc(5048); + memcpy(p, aligned_words, 5048); + + while (count-- > 0) + { + for (int i=0; i< SCANKEYWORDS_NUM_KEYWORDS; i++) + { + int idx = word_offsets[i]; + int s_len; + fasthash_state hs; + + fasthash_init(&hs, FH_UNKNOWN_LENGTH, 0); + s_len = fasthash_accum_cstring_unaligned(&hs, &p[idx]); + hash += fasthash_final32(&hs, s_len); + } + CHECK_FOR_INTERRUPTS(); + } + + PG_RETURN_INT32(hash); +} + + +PG_FUNCTION_INFO_V1(bench_cstring_hash_aligned); +Datum +bench_cstring_hash_aligned(PG_FUNCTION_ARGS) +{ + int32 count = PG_GETARG_INT32(0); + uint32 hash = 0; + + char* p = (char*) palloc(5048); + memcpy(p, aligned_words, 5048); + + while (count-- > 0) + { + for (int i=0; i< SCANKEYWORDS_NUM_KEYWORDS; i++) + { + int idx = word_offsets[i]; + int s_len; + fasthash_state hs; + + fasthash_init(&hs, FH_UNKNOWN_LENGTH, 0); + s_len = fasthash_accum_cstring_aligned(&hs, &p[idx]); + hash += fasthash_final32(&hs, s_len); + } + CHECK_FOR_INTERRUPTS(); + } + + PG_RETURN_INT32(hash); +} + +static inline uint32 +pgstat_hash_hash_key_orig(const void *d, size_t size, void *arg) +{ + const PgStat_HashKey *key = (PgStat_HashKey *) d; + uint32 hash; + + Assert(size == sizeof(PgStat_HashKey) && arg == NULL); + + hash = murmurhash32(key->kind); + hash = hash_combine(hash, murmurhash32(key->dboid)); + hash = hash_combine(hash, murmurhash32(key->objoid)); + + return hash; +} + +static inline uint32 +pgstat_hash_hash_key_FH(const void *d, size_t size, void *arg) +{ + const PgStat_HashKey *key = (PgStat_HashKey *) d; + + Assert(size == sizeof(PgStat_HashKey) && arg == NULL); + + return fasthash32((const char *) key, size, 0); +} + +PG_FUNCTION_INFO_V1(bench_pgstat_hash); +Datum +bench_pgstat_hash(PG_FUNCTION_ARGS) +{ + int32 count = PG_GETARG_INT32(0); + uint32 hash = 0; + + while (count-- > 0) + { + for (int i=0; i< SCANKEYWORDS_NUM_KEYWORDS - 3; i++) + { + int idx = word_offsets[i]; + hash += pgstat_hash_hash_key_orig((const void *) &aligned_words[idx], sizeof(PgStat_HashKey), NULL); + } + CHECK_FOR_INTERRUPTS(); + } + + PG_RETURN_INT32(hash); +} + +PG_FUNCTION_INFO_V1(bench_pgstat_hash_fh); +Datum +bench_pgstat_hash_fh(PG_FUNCTION_ARGS) +{ + int32 count = PG_GETARG_INT32(0); + uint32 hash = 0; + + while (count-- > 0) + { + for (int i=0; i< SCANKEYWORDS_NUM_KEYWORDS - 3; i++) + { + int idx = word_offsets[i]; + hash += pgstat_hash_hash_key_FH((const void *) &aligned_words[idx], sizeof(PgStat_HashKey), NULL); + } + CHECK_FOR_INTERRUPTS(); + } + + PG_RETURN_INT32(hash); +} diff --git a/contrib/bench_hash/bench_hash.control b/contrib/bench_hash/bench_hash.control new file mode 100644 index 00000000..ffc63858 --- /dev/null +++ b/contrib/bench_hash/bench_hash.control @@ -0,0 +1,5 @@ +# bench_hash extension +comment = 'benchmark some hash functions' +default_version = '1.0' +module_pathname = '$libdir/bench_hash' +relocatable = true diff --git a/contrib/bench_hash/meson.build b/contrib/bench_hash/meson.build new file mode 100644 index 00000000..f8d88d8b --- /dev/null +++ b/contrib/bench_hash/meson.build @@ -0,0 +1,19 @@ +# Copyright (c) 2022-2023, PostgreSQL Global Development Group + +bench_hash_sources = files( + 'bench_hash.c', +) + +bench_hash = shared_module('bench_hash', + bench_hash_sources, +# link_with: pgport_srv, + kwargs: contrib_mod_args, +) +contrib_targets += bench_hash + +install_data( + 'bench_hash.control', + 'bench_hash--1.0.sql', + kwargs: contrib_data_args, +) + diff --git a/contrib/meson.build b/contrib/meson.build index c0b267c6..0e991954 100644 --- a/contrib/meson.build +++ b/contrib/meson.build @@ -12,6 +12,7 @@ contrib_doc_args = { 'install_dir': contrib_doc_dir, } +subdir('bench_hash') subdir('adminpack') subdir('amcheck') subdir('auth_delay') diff --git a/src/backend/catalog/namespace.c b/src/backend/catalog/namespace.c index 37a69e90..43b406c3 100644 --- a/src/backend/catalog/namespace.c +++ b/src/backend/catalog/namespace.c @@ -41,7 +41,7 @@ #include "catalog/pg_ts_template.h" #include "catalog/pg_type.h" #include "commands/dbcommands.h" -#include "common/hashfn.h" +#include "common/hashfn_unstable.h" #include "funcapi.h" #include "mb/pg_wchar.h" #include "miscadmin.h" @@ -248,11 +248,31 @@ static bool MatchNamedCall(HeapTuple proctup, int nargs, List *argnames, static inline uint32 spcachekey_hash(SearchPathCacheKey key) { - const unsigned char *bytes = (const unsigned char *) key.searchPath; + fasthash_state hs; + int sp_len; + + /* WIP: maybe roleid should be mixed in normally */ + uint64 seed = key.roleid; + + // XXX not for commit +#ifdef USE_ASSERT_CHECKING + int blen = strlen(key.searchPath); - return hash_combine(hash_bytes(bytes, blen), - hash_uint32(key.roleid)); + uint64 h_orig = fasthash64(key.searchPath, blen, key.roleid); + + // Compare orig to optimized string interface + fasthash_init(&hs, blen, key.roleid); + (void) fasthash_accum_cstring(&hs, key.searchPath); + Assert(fasthash_final64(&hs, 0) == h_orig); +#endif + + fasthash_init(&hs, FH_UNKNOWN_LENGTH, seed); + + sp_len = fasthash_accum_cstring(&hs, key.searchPath); + + /* pass the length to tweak the final mix */ + return fasthash_final32(&hs, sp_len); } static inline bool diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h new file mode 100644 index 00000000..5bc1fc88 --- /dev/null +++ b/src/include/common/hashfn_unstable.h @@ -0,0 +1,309 @@ +/* +Building blocks for creating fast inlineable hash functions. The +unstable designation is in contrast to hashfn.h, which cannot break +compatibility because hashes can be writen to disk and so must produce +the same hashes between versions. + + * + * Portions Copyright (c) 2018-2023, PostgreSQL Global Development Group + * + * src/include/common/hashfn_unstable.c + */ + +#ifndef HASHFN_UNSTABLE_H +#define HASHFN_UNSTABLE_H + +#include "port/pg_bitutils.h" +#include "port/pg_bswap.h" + +/* + * fasthash is a modification of code taken from + * https://code.google.com/archive/p/fast-hash/source/default/source + * under the terms of the MIT licencse. The original copyright + * notice follows: + */ + +/* The MIT License + + Copyright (C) 2012 Zilong Tan (eric.zl...@gmail.com) + + Permission is hereby granted, free of charge, to any person + obtaining a copy of this software and associated documentation + files (the "Software"), to deal in the Software without + restriction, including without limitation the rights to use, copy, + modify, merge, publish, distribute, sublicense, and/or sell copies + of the Software, and to permit persons to whom the Software is + furnished to do so, subject to the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. +*/ + +/* + * There are two interfaces available. Examples assume a 32-bit hash: + * + * 1) When the length is known ahead of time, use fasthash32(). + * 2) When the length is not known, use the incremental interface. To + * ensure good results, keep track of the length and pass it to the finalizer: + +fasthash_state hs; +fasthash_init(&hs, FH_UNKNOWN_LENGTH, 0); +fasthash_accum(&hs, <pointer to a chunk of the input>, <chunk length, up to 8>); +return fasthash_final32(&hs, <final length>); + +*/ + + +typedef struct fasthash_state +{ + uint64 accum; + + uint64 hash; +} fasthash_state; + +#define FH_SIZEOF_ACCUM 8 +StaticAssertDecl(sizeof(((fasthash_state*) 0)->accum) == FH_SIZEOF_ACCUM, "wrong size for size macro"); + +#define FH_UNKNOWN_LENGTH 1 + +/* + * Initialize the hash state. + * + * "len" is the length of the input, if known ahead of time. + * If that is not known, pass FH_UNKNOWN_LENGTH. + * "seed" can be zero. + */ +static inline void +fasthash_init(fasthash_state *hs, int len, uint64 seed) +{ + memset(hs, 0, sizeof(fasthash_state)); + hs->hash = seed ^ (len * 0x880355f21e6d1965); +} + +/* Both the finalizer and part of the combining step */ +static inline uint64 +fasthash_mix(uint64 h, uint64 tweak) +{ + h ^= (h >> 23) + tweak; + h *= 0x2127599bf4325c37; + h ^= h >> 47; + return h; +} + +static inline void +fasthash_combine(fasthash_state *hs) +{ + hs->hash ^= fasthash_mix(hs->accum, 0); + hs->hash *= 0x880355f21e6d1965; + + /* reset hash state for next input */ + hs->accum = 0; +} + +/* Accumulate up to 8 bytes of input and combine it into the hash */ +static inline void +fasthash_accum(fasthash_state *hs, const char *k, int len) +{ + Assert(hs->accum == 0); + Assert(len <= FH_SIZEOF_ACCUM); + + switch (len) + { + case 8: + memcpy(&hs->accum, k, 8); + break; + case 7: + hs->accum |= (uint64) k[6] << 48; + /* FALLTHROUGH */ + case 6: + hs->accum |= (uint64) k[5] << 40; + /* FALLTHROUGH */ + case 5: + hs->accum |= (uint64) k[4] << 32; + /* FALLTHROUGH */ + case 4: + hs->accum |= (uint64) k[3] << 24; + /* FALLTHROUGH */ + case 3: + hs->accum |= (uint64) k[2] << 16; + /* FALLTHROUGH */ + case 2: + hs->accum |= (uint64) k[1] << 8; + /* FALLTHROUGH */ + case 1: + hs->accum |= (uint64) k[0]; + break; + case 0: + return; + } + + fasthash_combine(hs); +} + +/* From: https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord */ +#define haszero64(v) \ + (((v) - 0x0101010101010101UL) & ~(v) & 0x8080808080808080UL) + +/* + * With an aligned pointer, we consume the string a word at a time. Loading + * the word containing the NUL terminator cannot segfault since page boundaries + * are MAXALIGN'd. For that last word, only use bytes up to the NUL for the hash. + * The algorithm was adopted from NetBSD's strlen. + */ +static inline int +fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str) +{ + const char *const start = str; + const char *buf = start; + int remainder; + uint64 zero_bytes; + + Assert(PointerIsAligned(start, uint64)); + for (;;) + { + uint64 chunk = *(uint64 *)buf; + +#ifdef WORDS_BIGENDIAN + /* switch to little endian, to make later calculations easier */ + chunk = pg_bswap64(chunk); +#endif + + /* + * With little-endian representation, we can use this calculation, + * which sets bits in the first byte in the result word + * that corresponds to a zero byte in the original word. + * The rest of the bytes are indeterminate, so cannot be used + * on big-endian machines without either swapping or a bytewise check. + */ + zero_bytes = haszero64(chunk); + if (zero_bytes) + break; + + hs->accum = chunk; + fasthash_combine(hs); + buf += FH_SIZEOF_ACCUM; + } + + /* + * Bytes with set bits will be 0x80, so + * calculate the first occurrence of a zero byte within the input word + * by counting the number of trailing (for LE) + * zeros and dividing the result by 8. + */ + remainder = pg_rightmost_one_pos64(zero_bytes) / BITS_PER_BYTE; + fasthash_accum(hs, buf, remainder); + buf += remainder; + + return buf - start; +} + +static inline int +fasthash_accum_cstring_unaligned(fasthash_state *hs, const char *str) +{ + const char *const start = str; + const char *buf = str; + + while (*buf) + { + int chunk_len = 0; + + while (chunk_len < FH_SIZEOF_ACCUM && buf[chunk_len] != '\0') + chunk_len++; + + fasthash_accum(hs, buf, chunk_len); + buf += chunk_len; + } + + return buf - start; +} + +/* + * Accumulate the input into the hash state + * and return the length of the string. + */ +static inline int +fasthash_accum_cstring(fasthash_state *hs, const char *str) +{ +#if SIZEOF_VOID_P >= FH_SIZEOF_ACCUM + if (PointerIsAligned(str, uint64)) + return fasthash_accum_cstring_aligned(hs, str); + else +#endif + return fasthash_accum_cstring_unaligned(hs, str); +} + +/* + * The finalizer + * + * "tweak" is the input length when the caller doesn't know + * the length ahead of time, such as for NUL-terminated + * strings, otherwise zero. + */ +static inline uint64 +fasthash_final64(fasthash_state *hs, uint64 tweak) +{ + return fasthash_mix(hs->hash, tweak); +} + +/* + * Reduce a 64-bit hash to a 32-bit hash. + * + * This provides a bit more additional mixing compared to + * just taking the lower 32-bits. + */ +static inline uint32 +fasthash_reduce32(uint64 h) +{ + /* + * The following trick converts the 64-bit hashcode to Fermat residue, + * which shall retain information from both the higher and lower parts of + * hashcode. + */ + return h - (h >> 32); +} + +static inline uint32 +fasthash_final32(fasthash_state *hs, uint64 tweak) +{ + return fasthash_reduce32(fasthash_final64(hs, tweak)); +} + +/* + * The original fasthash64 function, re-implemented using + * the incremental interface. + */ +static inline uint64 +fasthash64(const char *k, int len, uint64 seed) +{ + fasthash_state hs; + + fasthash_init(&hs, len, seed); + + while (len >= FH_SIZEOF_ACCUM) + { + fasthash_accum(&hs, k, FH_SIZEOF_ACCUM); + k += FH_SIZEOF_ACCUM; + len -= FH_SIZEOF_ACCUM; + } + + fasthash_accum(&hs, k, len); + return fasthash_final64(&hs, 0); +} + +/* Like fasthash64, but returns a 32-bit hash */ +static inline uint64 +fasthash32(const char *k, int len, uint64 seed) +{ + return fasthash_reduce32(fasthash64(k, len, seed)); +} + +#endif /* HASHFN_UNSTABLE_H */ diff --git a/src/include/utils/pgstat_internal.h b/src/include/utils/pgstat_internal.h index 60fbf939..ecc46bef 100644 --- a/src/include/utils/pgstat_internal.h +++ b/src/include/utils/pgstat_internal.h @@ -14,7 +14,7 @@ #define PGSTAT_INTERNAL_H -#include "common/hashfn.h" +#include "common/hashfn_unstable.h" #include "lib/dshash.h" #include "lib/ilist.h" #include "pgstat.h" @@ -777,15 +777,10 @@ static inline uint32 pgstat_hash_hash_key(const void *d, size_t size, void *arg) { const PgStat_HashKey *key = (PgStat_HashKey *) d; - uint32 hash; Assert(size == sizeof(PgStat_HashKey) && arg == NULL); - hash = murmurhash32(key->kind); - hash = hash_combine(hash, murmurhash32(key->dboid)); - hash = hash_combine(hash, murmurhash32(key->objoid)); - - return hash; + return fasthash32((const char *) key, size, 0); } /* diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index e37ef9aa..f513d7fb 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -3326,6 +3326,7 @@ exec_thread_arg execution_state explain_get_index_name_hook_type f_smgr +fasthash_state fd_set fe_scram_state fe_scram_state_enum -- 2.34.1