Andres Freund писал 2021-08-06 06:49:
Hi,
On 2021-08-06 06:43:55 +0300, Yura Sokolov wrote:
Why don't use simplehash or something like that? Open-addressing
schemes
show superior cache locality.
I thought about that as well - but it doesn't really resolve the
question of
what we want to store in-line in the hashtable and what not. We can't
store
the tuples themselves in the hashtable for a myriad of reasons (need
pointer
stability, they're variably sized, way too large to move around
frequently).
Well, simplehash entry will be 24 bytes this way. If simplehash
template
supports external key/element storage, then it could be shrunk to 16
bytes,
and syscache entries will not need dlist_node. (But it doesn't at the
moment).
I think storing keys outside of the hashtable entry defeats the purpose
of the
open addressing, given that they are always checked and that our
conflict
ratio should be fairly low.
It's opposite: if conflict ratio were high, then key outside of
hashtable will
be expensive, since lookup to non-matched key will cost excess memory
access.
But with low conflict ratio we will usually hit matched entry at first
probe.
And since we will use entry soon, it doesn't matter when it will go to
CPU L1
cache: during lookup or during actual usage.
regards,
Yura Sokolov
