Re: Macro customizable hashtable / bitmapscan & aggregation perf

<div dir="ltr"><div class="gmail_extra"><br /><div class="gmail_quote">On Sat, Oct 1, 2016 at 2:44 AM, Andres Freund
<spandir="ltr"><<a href="mailto:andres@anarazel.de" target="_blank">andres@anarazel.de</a>></span> wrote:<br
/><blockquoteclass="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">Hi,<br/><br /> On 2016-07-26 17:43:33 -0700, Andres Freund wrote:<br /> > In the
attachedpatch I've attached simplehash.h, which can be<br /> > customized by a bunch of macros, before being
inlined. There's also a<br /> > patch using this for tidbitmap.c and nodeAgg/nodeSubplan/... via<br /> >
execGrouping.c.<br/><br /> Attached is a significantly improved version of this series.  The main<br /> changes are:<br
/><br/> - The hash table now uses robin-hood style hash collision handling. See the<br />   commit message of 0002 (or
simplehash.h)for an introduction. That<br />   significantly reduces the impact of "clustering" due to linear<br />  
addressing.<br/> - Significant comment and correctness fixes, both in simplehash.h<br /> - itself, and 0003/0004.<br />
-a lot of other random performance improvements for the hashing code.<br /><br /><br /> Unfortunately I'm running out
batteryright now, so I don't want to<br /> re-run the benchmarks posted upthread (loading takes a while). But the<br />
lasttime I ran them all the results after the patches were better than<br /> before.<br /><br /><br /> This patch
seriescurrently consists out of four patches:<br /> - 0001 - add unlikely/likely() macros. The use here is not
entirely<br/>   mandatory, but they do provide a quite consistent improvement. There<br />   are other threads where
theyproved to be beneficial, so I see little<br />   reason not to introduce them.<br /> - 0002 - the customizable
hashtableitself. It now contains documentation.<br /> - 0003 - convert tidbitmap.c to use the new hashmap. This
includesa fix<br />   for the issue mentioned in [1], to improve peformance in heavily lossy<br />   scenarios
(otherwisewe could regress in some extreme cases)<br /> - 0004 - convert execGrouping.c, e.g. used by hash
aggregates<br/><br /><br /> While not quite perfect yet, I do think this is at a state where input<br /> is needed.  I
don'twant to go a lot deeper into this rabbit hole,<br /> before we have some agreement that this is a sensible course
ofaction.<br /><br /><br /> I think there's several possible additional users of simplehash.h,<br /> e.g. catcache.c -
whichhas an open coded, not particularly fast hash<br /> table and frequently shows up in profiles - but I think the
abovetwo<br /> conversions are plenty to start with.<br /><br /><br /> Comments?<br /><br /><br /> Greetings,<br /><br
/>Andres Freund<br /><br /> [1] <a
href="http://archives.postgresql.org/message-id/20160923205843.zcs533sqdzlh4cpo%40alap3.anarazel.de"rel="noreferrer"
target="_blank">http://archives.postgresql.org<wbr/>/message-id/20160923205843.zcs<wbr
/>533sqdzlh4cpo%40alap3.anarazel<wbr/>.de</a><br /><br /><br /> --<br /> Sent via pgsql-hackers mailing list (<a
href="mailto:pgsql-hackers@postgresql.org"target="_blank">pgsql-hackers@postgresql.org</a>)<br /> To make changes to
yoursubscription:<br /><a href="http://www.postgresql.org/mailpref/pgsql-hackers" rel="noreferrer"
target="_blank">http://www.postgresql.org/mail<wbr/>pref/pgsql-hackers</a><br /><br /></blockquote></div><br
/></div><divclass="gmail_extra">This is a great addition.<br /><br /></div><div class="gmail_extra">A couple of
comments.<br/></div><div class="gmail_extra"><br /></div><div class="gmail_extra">* 80% occupancy is a bit conservative
forRH hashing, it works well up to 90% if you use the early stops due to distance. So that TODO is worth pursuing.<br
/><br/>* An optimized memory layout for RH hashmap is along the lines of HHHKVKVKV, using one bit of the hash as the
present/absentflag. That plays specially well with large occupancies (~90%). Due to RH the probings on the H array are
veryshort and within a single cache line. Even with a 31bit hash it's reallyyy rare to have to probe more than 1 entry
inthe KV array. Essentially guaranteeing that the 99% percentile of lookups will only hit a couple of cache lines (if
youignore crossing cache lines and other details).<br /></div><br /></div>