diff mbox series

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

Message ID 20200731092323.763-2-anton.ivanov@cambridgegreys.com
State New
Headers show
Series [ovs-dev,1/3] Optimise shash disposal | expand

Commit Message

Anton Ivanov July 31, 2020, 9:23 a.m. UTC
From: Anton Ivanov <anton.ivanov@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@cambridgegreys.com>
---
 lib/shash.c | 48 +++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 37 insertions(+), 11 deletions(-)

Comments

Dumitru Ceara Aug. 7, 2020, 11:09 a.m. UTC | #1
On 7/31/20 11:23 AM, anton.ivanov@cambridgegreys.com wrote:
> From: Anton Ivanov <anton.ivanov@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@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
> 

Hi Anton,

With this we're now using hmap internals in shash.c. Wouldn't it be
better for hmap to expose an API to clear (maybe with a handler per node)?

Thanks,
Dumitru
diff mbox series

Patch

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