Patch attached.
The caller could do something similar, so this option is not necessary,
but it seems like it could be generally useful. It speeds things up for
the search_path cache (and is an alternative to another patch I have
that implements the same thing in the caller).
Thoughts?
Regards,
Jeff Davis
From b878af835da794f3384f870db57b34e236b1efba Mon Sep 17 00:00:00 2001
From: Jeff Davis <[email protected]>
Date: Mon, 20 Nov 2023 17:42:07 -0800
Subject: [PATCH] Add SH_OPTIMIZE_REPEAT option to simplehash.h.
Callers which expect to look up the same value repeatedly can specify
SH_OPTIMIZE_REPEAT. That option causes simplehash to quickly check if
the last entry returned has a the same key, and return it immediately
if so (before calculating the hash).
---
src/include/lib/simplehash.h | 34 ++++++++++++++++++++++++++++++++--
1 file changed, 32 insertions(+), 2 deletions(-)
diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index b1a3d7f927..9a3dbfecfa 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -49,6 +49,7 @@
* - SH_EQUAL(table, a, b) - compare two table keys
* - SH_HASH_KEY(table, key) - generate hash for the key
* - SH_STORE_HASH - if defined the hash is stored in the elements
+ * - SH_OPTIMIZE_REPEAT - optimize for repeated lookups of the same key
* - SH_GET_HASH(tb, a) - return the field to store the hash in
*
* The element type is required to contain a "status" member that can store
@@ -163,6 +164,11 @@ typedef struct SH_TYPE
/* hash buckets */
SH_ELEMENT_TYPE *data;
+#ifdef SH_OPTIMIZE_REPEAT
+ /* last element found */
+ SH_ELEMENT_TYPE *previous;
+#endif
+
#ifndef SH_RAW_ALLOCATOR
/* memory context to use for allocations */
MemoryContext ctx;
@@ -777,7 +783,16 @@ restart:
SH_SCOPE SH_ELEMENT_TYPE *
SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
{
- uint32 hash = SH_HASH_KEY(tb, key);
+ uint32 hash;
+
+#ifdef SH_OPTIMIZE_REPEAT
+ if (tb->previous != NULL &&
+ tb->previous->status == SH_STATUS_IN_USE &&
+ SH_EQUAL(tb, key, tb->previous->SH_KEY))
+ return tb->previous;
+#endif
+
+ hash = SH_HASH_KEY(tb, key);
return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);
}
@@ -815,7 +830,12 @@ SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
Assert(entry->status == SH_STATUS_IN_USE);
if (SH_COMPARE_KEYS(tb, hash, key, entry))
+ {
+#ifdef SH_OPTIMIZE_REPEAT
+ tb->previous = entry;
+#endif
return entry;
+ }
/*
* TODO: we could stop search based on distance. If the current
@@ -834,7 +854,16 @@ SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
SH_SCOPE SH_ELEMENT_TYPE *
SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key)
{
- uint32 hash = SH_HASH_KEY(tb, key);
+ uint32 hash;
+
+#ifdef SH_OPTIMIZE_REPEAT
+ if (tb->previous != NULL &&
+ tb->previous->status == SH_STATUS_IN_USE &&
+ SH_EQUAL(tb, key, tb->previous->SH_KEY))
+ return tb->previous;
+#endif
+
+ hash = SH_HASH_KEY(tb, key);
return SH_LOOKUP_HASH_INTERNAL(tb, key, hash);
}
@@ -1152,6 +1181,7 @@ SH_STAT(SH_TYPE * tb)
#undef SH_DEFINE
#undef SH_GET_HASH
#undef SH_STORE_HASH
+#undef SH_OPTIMIZE_REPEAT
#undef SH_USE_NONDEFAULT_ALLOCATOR
#undef SH_EQUAL
--
2.34.1
