hash list optimisation

Signed-off-by: Mattias Andrée <maandree@operamail.com>

2 files changed, 142 insertions, 24 deletions

diff --git a/doc/info/mds.texinfo b/doc/info/mds.texinfo
index 62210a9..9fe6382 100644
--- a/doc/info/mds.texinfo
+++ b/doc/info/mds.texinfo
@@ -7800,6 +7800,19 @@ The number of slots that have been used, even if
 no longer used. This element is transparent to the
 user of the class.
 
+@item @code{last} [@code{size_t}]
+@vrindex @code{last}
+@vrindex @code{hash_list_t.last}
+@fnindex @code{hash_list_get}
+@fnindex @code{hash_list_put}
+@fnindex @code{hash_list_remove}
+This variable is used for optimisation, any
+time @code{hash_list_get} finds an element, its
+will be stored, and it will be the first
+inspected element by @code{hash_list_put} and
+@code{hash_list_remove}. This element is
+transparent to the user of the class.
+
 @item @code{slots} [@code{hash_list_entry_t*}]
 @vrindex @code{slots}
 @vrindex @code{hash_list_t.slots}
@@ -7864,13 +7877,15 @@ on error. Errors are however non-fatal and can be ignored,
 it only means that the capacity could not be reduces, because
 a called to @code{realloc} failed.
 
-@item @code{hash_list_get} [(@code{const this, const KEY_T key, VALUE_T* restrict value}) @arrow{} @code{int}]
+@item @code{hash_list_get} [(@code{this, const KEY_T key, VALUE_T* restrict value}) @arrow{} @code{int}]
 @fnindex @code{hash_list_get}
 Look up a value, with the key @code{key}, in the hash list
 @code{this}. The found value will be stored in @code{*value}.
 This method cannot fail, therefore it cannot return a value
 indicating that it failed. Instead it returns one if the
 entry was found and nought if it was not found.
+Note that @code{this} is not specified with @code{const};
+this is because internal caching is done.
 
 @item @code{hash_list_put} [(@code{this, KEY_T key, const VALUE_T* restrict value}) @arrow{} @code{int}]
 @fnindex @code{hash_list_put}
@@ -7954,8 +7969,8 @@ will it would return after the unmarshalling.
 The function shall return zero on error.
 @end table
 
-@file{<libmdsserver/hash-list.h>} also defines a
-macro that is uneffected by @code{CREATE_HASH_LIST_SUBCLASS}.
+@file{<libmdsserver/hash-list.h>} also defines two
+macros that is uneffected by @code{CREATE_HASH_LIST_SUBCLASS}.
 
 @table @asis
 @item @code{foreach_hash_list_entry} [(@code{hash_list_t this, size_t i, hash_list_entry_t* entry})]
@@ -7992,6 +8007,34 @@ void print_hash_list(hash_list_t* table)
 
 Note thay the data type for the parameter @code{this}
 is not a pointer.
+
+@item @code{HASH_LIST_EXPECTED} [(@code{...})]
+This macro is defined as @code{__builtin_expect(__VA_ARGS__, 1)}.
+This means that the input value is evaluated, and may
+contain the sequence-operator (comma-operator), and the
+the value is expected to evaluate to @code{1}.
+
+It is encourage to run @code{hash_list_get} before
+@code{hash_list_put} and @code{hash_list_remove}.
+This way, you know exactly what is happening.
+There is an optimisation in place to let
+@code{hash_list_put} and @code{hash_list_remove}
+skip the search for the item (unless it is the first
+element) if @code{hash_list_get} was used directly
+prior to @code{hash_list_put} or @code{hash_list_remove}
+to find the element. This macro used to tell the
+compiler that position of the element is most likely
+already known but is not zero.
+
+If you however choose to not call @code{hash_list_get}
+before @code{hash_list_put} and @code{hash_list_remove}
+you should define this macro before including the header
+file, but with the @code{1} changed to a @code{0}. If
+you on the other hand do not know if you are going to
+call @code{hash_list_get} before @code{hash_list_put}
+and @code{hash_list_remove} you should define it to
+expand to the input verbatim, that is, have the value
+@code{__VA_ARGS__}.
 @end table
 
 
diff --git a/src/libmdsserver/hash-list.h b/src/libmdsserver/hash-list.h
index fcd9eb4..a9ae256 100644
--- a/src/libmdsserver/hash-list.h
+++ b/src/libmdsserver/hash-list.h
@@ -37,6 +37,33 @@
 # define HASH_LIST_DEFAULT_INITIAL_CAPACITY  128
 #endif
 
+/**
+ * It is encourage to run `hash_list_get` before
+ * `hash_list_put` and `hash_list_remove`. This
+ * way, you know exactly what is happening.
+ * There is an optimisation in place to let
+ * `hash_list_put` and `hash_list_remove` skip
+ * the search for the item (unless it is the first
+ * element) if `hash_list_get` was used directly
+ * prior to `hash_list_put` or `hash_list_remove`
+ * to find the element. This macro used to tell
+ * the compiler that position of the element is
+ * most likely already known but is not zero.
+ * 
+ * If you however choose to not call `hash_list_get`
+ * before `hash_list_put` and `hash_list_remove`
+ * you should define this macro before including
+ * this header file, but with the `1` changed to
+ * a `0`. If you on the other hand do not know
+ * if you are going to call `hash_list_get` before
+ * `hash_list_put` and `hash_list_remove` you
+ * should define it to expand to the input verbatim,
+ * that is, have the value `__VA_ARGS__`.
+ */
+#ifndef HASH_LIST_EXPECTED
+# define HASH_LIST_EXPECTED(...)  __builtin_expect((__VA_ARGS__), 1)
+#endif
+
 
 #define HASH_LIST_HASH(key)  (this->hasher != NULL ? this->hasher(key) : (size_t)key)
 
@@ -171,6 +198,15 @@ typedef struct T\
   size_t used;\
   \
   /**
+   * This variable is used for optimisation, any
+   * time `hash_list_get` finds an element, its
+   * will be stored, and it will be the first
+   * inspected element by `hash_list_put` and
+   * `hash_list_remove`
+   */\
+  size_t last;\
+  \
+  /**
    * The slots
    */\
   T##_entry_t* slots;\
@@ -215,6 +251,7 @@ T##_create(T##_t* restrict this, size_t capacity)\
   this->allocated = 0;\
   this->unused = 0;\
   this->used = 0;\
+  this->last = 0;\
   \
   this->slots = malloc(capacity * sizeof(T##_t));\
   if (this->slots == NULL)\
@@ -241,6 +278,7 @@ T##_destroy(T##_t* restrict this)\
   this->used = 0;\
   this->unused = 0;\
   this->allocated = 0;\
+  this->last = 0;\
   free(this->slots);\
   this->slots = NULL;\
 }\
@@ -260,6 +298,7 @@ T##_clone(const T##_t* restrict this, T##_t* restrict out)\
     return -1;\
   out->used = this->used;\
   out->unused = this->unused;\
+  out->last = this->last;\
   memcpy(out->slots, this->slots, this->used * sizeof(T##_entry_t));\
 }\
 \
@@ -289,6 +328,7 @@ T##_pack(T##_t* restrict this)\
       \
       this->used -= this->unused;\
       this->unused = 0;\
+      this->last = 0;\
     }\
   \
   if (this->used < this->allocated)\
@@ -313,14 +353,14 @@ T##_pack(T##_t* restrict this)\
  * @return         Whether the key was found, error is impossible
  */\
 static inline int __attribute__((unused))\
-T##_get(const T##_t* restrict this, CKEY_T key, T##_value_t* restrict value)\
+T##_get(T##_t* restrict this, CKEY_T key, T##_value_t* restrict value)\
 {\
   size_t i, n, hash = HASH_LIST_HASH(key);\
   for (i = 0, n = this->used; i < n; i++)\
     if ((this->slots[i].key_hash == hash) && this->slots[i].key)\
       if (T##_key_comparer(this->slots[i].key, key))\
-	return *value = this->slots[i].value, 1;\
-  return 0;\
+	return *value = this->slots[this->last = i].value, 1;\
+  return this->last = 0, 0;\
 }\
 \
 \
@@ -333,20 +373,37 @@ T##_get(const T##_t* restrict this, CKEY_T key, T##_value_t* restrict value)\
 static inline void __attribute__((unused))\
 T##_remove(T##_t* restrict this, CKEY_T key)\
 {\
-  size_t i, n, hash = HASH_LIST_HASH(key);\
+  size_t i = this->last, n, hash = HASH_LIST_HASH(key);\
   T##_entry_t* slots = this->slots;\
+  \
+  /* First, try cached index */\
+  if (HASH_LIST_EXPECTED(i && (slots[i].key_hash == hash) && (slots[i].key != NULL)))\
+    if (HASH_LIST_EXPECTED(T##_key_comparer(slots[i].key, key)))\
+      goto do_remove;\
+  /* It is discouraged to use put or remove without
+   * doing a get before it, otherwise you do not know
+   * what is happening. So we do not expect to get
+   * get to the next line. However, if do not expect to
+   * run get before put or remove, you should modify the
+   * HASH_LIST_EXPECTED macro. However, this is single
+   * case where will will get to the next line, when the
+   * index of the item is zero. */\
+  \
+  /* Then, search */\
   for (i = 0, n = this->used; i < n; i++)\
     if ((slots[i].key_hash == hash) && (slots[i].key != NULL))\
       if (T##_key_comparer(slots[i].key, key))\
-	{\
-	  if (this->freer != NULL)\
-	    this->freer(slots + i);\
-	  slots[i].key = NULL;\
-	  this->unused++;\
-	  if ((this->unused >> 1) >= this->used)\
-	    T##_pack(this);\
-	  return;\
-	}\
+	goto do_remove;\
+  \
+  return;\
+ do_remove:\
+  if (this->freer != NULL)\
+    this->freer(slots + i);\
+  slots[i].key = NULL;\
+  this->unused++;\
+  if ((this->unused >> 1) >= this->used)\
+    T##_pack(this);\
+  this->last = 0;\
 }\
 \
 \
@@ -362,7 +419,7 @@ T##_remove(T##_t* restrict this, CKEY_T key)\
 static inline int __attribute__((unused))\
 T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* restrict value)\
 {\
-  size_t i, n, empty, hash;\
+  size_t i = this->last, n, empty = this->used, hash;\
   T##_entry_t* slots = this->slots;\
   \
   /* Remove entry if no value is passed */\
@@ -372,18 +429,30 @@ T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* restrict value)\
       return 0;\
     }\
   \
+  /* Hash the input key */\
+  hash = HASH_LIST_HASH(key);\
+  \
+  /* Try cached index */\
+  if (HASH_LIST_EXPECTED(i && (slots[i].key != NULL)))\
+    if (HASH_LIST_EXPECTED(slots[i].key_hash == hash))\
+      if (HASH_LIST_EXPECTED(T##_key_comparer(slots[i].key, key)))\
+	goto put;\
+  /* It is discouraged to use put or remove without
+   * doing a get before it, otherwise you do not know
+   * what is happening. So we do not expect to get
+   * get to the next line. However, if do not expect to
+   * run get before put or remove, you should modify the
+   * HASH_LIST_EXPECTED macro. However, this is single
+   * case where will will get to the next line, when the
+   * index of the item is zero. */\
+  \
   /* Find an unused slot or the current slot */\
-  empty = this->used, hash = HASH_LIST_HASH(key);\
   for (i = 0, n = this->used; i < n; i++)\
     if (slots[i].key == NULL)\
       empty = i;\
     else if (slots[i].key_hash == hash)\
       if (T##_key_comparer(slots[i].key, key))\
-	{\
-	  if (this->freer != NULL)\
-	    this->freer(slots + i);\
-	  goto put;\
-	}\
+	goto put;\
   \
   /* Grow slot allocation is required */\
   if (empty == this->allocated)\
@@ -399,7 +468,11 @@ T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* restrict value)\
   \
   /* Store entry */\
   i = empty;\
+  goto put_no_free;\
  put:\
+  if (this->freer != NULL)\
+    this->freer(slots + i);\
+ put_no_free:\
   slots[i].key = key;\
   slots[i].key_hash = hash;\
   slots[i].value = *value;\
@@ -417,7 +490,7 @@ static inline size_t __attribute__((unused))\
 T##_marshal_size(const T##_t* restrict this)\
 {\
   size_t i, n = this->used;\
-  size_t rc = sizeof(int) + 3 * sizeof(size_t);\
+  size_t rc = sizeof(int) + 4 * sizeof(size_t);\
   for (i = 0; i < n; i++)\
     if (this->slots[i].key != NULL)\
       rc += T##_submarshal_size(this->slots + i);\
@@ -440,6 +513,7 @@ T##_marshal(const T##_t* restrict this, char* restrict data)\
   buf_set_next(data, size_t, this->allocated);\
   buf_set_next(data, size_t, this->unused);\
   buf_set_next(data, size_t, this->used);\
+  buf_set_next(data, size_t, this->last);\
   \
   for (i = 0; i < n; i++)\
     if (this->slots[i].key != NULL)\
@@ -477,6 +551,7 @@ T##_unmarshal(T##_t* restrict this, char* restrict data)\
   buf_get_next(data, size_t, this->allocated);\
   buf_get_next(data, size_t, this->unused);\
   buf_get_next(data, size_t, this->used);\
+  buf_get_next(data, size_t, this->last);\
   \
   this->slots = calloc(this->allocated, sizeof(T##_entry_t));\
   if (this->slots == NULL)\