[ovs-dev] [PATCH 1/3] Optimise shash disposal
Dumitru Ceara
dceara at redhat.com
Fri Aug 7 11:09:36 UTC 2020
On 7/31/20 11:23 AM, anton.ivanov at cambridgegreys.com wrote:
> 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
>
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
More information about the dev
mailing list