[ovs-dev] [PATCH 1/3] Optimise shash disposal

anton.ivanov at cambridgegreys.com anton.ivanov at cambridgegreys.com
Fri Jul 31 09:23:21 UTC 2020


From: Anton Ivanov <anton.ivanov at cambridgegreys.com>

SHASH as written at present relies on HMAP and iterator macros
to dispose of all of its elements.

This results in a lot of unnecessary hash comparisons and walk
attempts which simply return the next item.

This patch switches this to direct removal where the whole shash
is cleared at once in O(N) without any hash recomputations and
comparisons.

Signed-off-by: Anton Ivanov <anton.ivanov at cambridgegreys.com>
---
 lib/shash.c | 48 +++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 37 insertions(+), 11 deletions(-)

diff --git a/lib/shash.c b/lib/shash.c
index a8433629a..09505b73d 100644
--- a/lib/shash.c
+++ b/lib/shash.c
@@ -68,27 +68,53 @@ shash_moved(struct shash *sh)
 void
 shash_clear(struct shash *sh)
 {
-    struct shash_node *node, *next;
+    struct shash_node *node;
+    struct hmap_node *hn;
+
+    int i;
 
-    SHASH_FOR_EACH_SAFE (node, next, sh) {
-        hmap_remove(&sh->map, &node->node);
-        free(node->name);
-        free(node);
+    if (sh->map.n == 0) {
+        return;
+    }
+
+    for (i = 0; i <= sh->map.mask; i++) {
+        hn = sh->map.buckets[i];
+        while (hn != NULL) {
+            node = CONTAINER_OF(hn, struct shash_node, node);
+            hn = hn->next;
+            free(node->name);
+            free(node);
+        }
+        sh->map.buckets[i] = NULL;
     }
+    sh->map.n = 0;
 }
 
 /* Like shash_clear(), but also free() each node's 'data'. */
 void
 shash_clear_free_data(struct shash *sh)
 {
-    struct shash_node *node, *next;
+    struct shash_node *node;
+    struct hmap_node *hn;
+
+    int i;
 
-    SHASH_FOR_EACH_SAFE (node, next, sh) {
-        hmap_remove(&sh->map, &node->node);
-        free(node->data);
-        free(node->name);
-        free(node);
+    if (sh->map.n == 0) {
+        return;
+    }
+
+    for (i = 0; i <= sh->map.mask; i++) {
+        hn = sh->map.buckets[i];
+        while (hn != NULL) {
+            node = CONTAINER_OF(hn, struct shash_node, node);
+            hn = hn->next;
+            free(node->data);
+            free(node->name);
+            free(node);
+        }
+        sh->map.buckets[i] = NULL;
     }
+    sh->map.n = 0;
 }
 
 bool
-- 
2.20.1



More information about the dev mailing list