diff mbox series

[ovs-dev,3/3] Unroll operations inside shash_find_and_delete

Message ID 20200731092323.763-4-anton.ivanov@cambridgegreys.com
State Changes Requested
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_find_and_delete at present looks up an item using
shash_find then uses hmap_delete to delete it.

As a result it computes the hash twice and does two walks of
the linked list in the bucket.

This change unrolls the first walk to preserve extra information
making the second computation and walk unnecessary.

Signed-off-by: Anton Ivanov <anton.ivanov@cambridgegreys.com>
---
 lib/shash.c | 36 ++++++++++++++++++++++++++++++------
 1 file changed, 30 insertions(+), 6 deletions(-)

Comments

Dumitru Ceara Aug. 7, 2020, 11:22 a.m. UTC | #1 
On 7/31/20 11:23 AM, anton.ivanov@cambridgegreys.com wrote:
> From: Anton Ivanov <anton.ivanov@cambridgegreys.com>
> 
> shash_find_and_delete at present looks up an item using
> shash_find then uses hmap_delete to delete it.
> 
> As a result it computes the hash twice and does two walks of
> the linked list in the bucket.
> 
> This change unrolls the first walk to preserve extra information
> making the second computation and walk unnecessary.
> 
> Signed-off-by: Anton Ivanov <anton.ivanov@cambridgegreys.com>
> ---
>  lib/shash.c | 36 ++++++++++++++++++++++++++++++------
>  1 file changed, 30 insertions(+), 6 deletions(-)
> 
> diff --git a/lib/shash.c b/lib/shash.c
> index f378d1656..d2793c2e7 100644
> --- a/lib/shash.c
> +++ b/lib/shash.c
> @@ -276,14 +276,38 @@ shash_find_data(const struct shash *sh, const char *name)
>  void *
>  shash_find_and_delete(struct shash *sh, const char *name)
>  {
> -    struct shash_node *node = shash_find(sh, name);
> -    if (node) {
> -        void *data = node->data;
> -        shash_delete(sh, node);
> -        return data;
> -    } else {
> +    struct shash_node *node;
> +
> +    /* unroll shash_find and hmap_find */
> +
> +    struct hmap_node
> +        **bucket = &sh->map.buckets[hash_name(name) & sh->map.mask];
> +    ssize_t name_len = strlen(name);
> +
> +    while (*bucket != NULL) {
> +        node = CONTAINER_OF(*bucket, struct shash_node, node);
> +        if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
> +            break;
> +        }
> +        bucket = &(*bucket)->next;
> +    }
> +
> +    if (*bucket == NULL) {
>          return NULL;
>      }
> +
> +    void *data = node->data;
> +
> +    /* use the underlying hmap node to do a direct hmap remove */
> +
> +    *bucket = node->node.next;
> +    sh->map.n--;
> +
> +    /* unroll smap_steal and smap_delete */
> +
> +    free(node->name);
> +    free(node);
> +    return data;
>  }
>  
>  void *
> 

Same as for patch1, shouldn't most of this be implemented in hmap? E.g.,
hmap_find_and_delete() which would return the node that was removed from
the hmap?

Thanks,
Dumitru
diff mbox series

Patch

diff --git a/lib/shash.c b/lib/shash.c
index f378d1656..d2793c2e7 100644
--- a/lib/shash.c
+++ b/lib/shash.c
@@ -276,14 +276,38 @@  shash_find_data(const struct shash *sh, const char *name)
 void *
 shash_find_and_delete(struct shash *sh, const char *name)
 {
-    struct shash_node *node = shash_find(sh, name);
-    if (node) {
-        void *data = node->data;
-        shash_delete(sh, node);
-        return data;
-    } else {
+    struct shash_node *node;
+
+    /* unroll shash_find and hmap_find */
+
+    struct hmap_node
+        **bucket = &sh->map.buckets[hash_name(name) & sh->map.mask];
+    ssize_t name_len = strlen(name);
+
+    while (*bucket != NULL) {
+        node = CONTAINER_OF(*bucket, struct shash_node, node);
+        if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
+            break;
+        }
+        bucket = &(*bucket)->next;
+    }
+
+    if (*bucket == NULL) {
         return NULL;
     }
+
+    void *data = node->data;
+
+    /* use the underlying hmap node to do a direct hmap remove */
+
+    *bucket = node->node.next;
+    sh->map.n--;
+
+    /* unroll smap_steal and smap_delete */
+
+    free(node->name);
+    free(node);
+    return data;
 }
 
 void *