From eecec8ceba7dcd572ff557726e7e253488b13656 Mon Sep 17 00:00:00 2001
From: Damjan Marion <damarion@cisco.com>
Date: Wed, 6 Apr 2022 12:06:41 +0200
Subject: stats: avoid linear search for empty entry

Type: improvement
Change-Id: Ie4cdc6d8906da3d1cd18a8f1d7076283546d3003
Signed-off-by: Damjan Marion <damarion@cisco.com>
---
 src/vlib/stats/init.c  |  1 +
 src/vlib/stats/stats.c | 24 ++++++++++++++----------
 src/vlib/stats/stats.h |  1 +
 3 files changed, 16 insertions(+), 10 deletions(-)

diff --git a/src/vlib/stats/init.c b/src/vlib/stats/init.c
index 3cfbd2dbd66..2a7b6f53c53 100644
--- a/src/vlib/stats/init.c
+++ b/src/vlib/stats/init.c
@@ -98,6 +98,7 @@ vlib_stats_init (vlib_main_t *vm)
 
   /* Set up the name to counter-vector hash table */
   sm->directory_vector = 0;
+  sm->dir_vector_first_free_elt = CLIB_U32_MAX;
 
   shared_header->epoch = 1;
 
diff --git a/src/vlib/stats/stats.c b/src/vlib/stats/stats.c
index 9063fa375e6..cb29ddaf378 100644
--- a/src/vlib/stats/stats.c
+++ b/src/vlib/stats/stats.c
@@ -106,20 +106,21 @@ vlib_stats_create_counter (vlib_stats_entry_t *e)
 {
   vlib_stats_segment_t *sm = vlib_stats_get_segment ();
   void *oldheap;
-  u32 index = ~0;
-  int i;
+  u32 index;
 
   oldheap = clib_mem_set_heap (sm->heap);
-  vec_foreach_index_backwards (i, sm->directory_vector)
-    if (sm->directory_vector[i].type == STAT_DIR_TYPE_EMPTY)
-      {
-	index = i;
-	break;
-      }
 
-  index = index == ~0 ? vec_len (sm->directory_vector) : index;
+  if (sm->dir_vector_first_free_elt != CLIB_U32_MAX)
+    {
+      index = sm->dir_vector_first_free_elt;
+      sm->dir_vector_first_free_elt = sm->directory_vector[index].index;
+    }
+  else
+    {
+      index = vec_len (sm->directory_vector);
+      vec_validate (sm->directory_vector, index);
+    }
 
-  vec_validate (sm->directory_vector, index);
   sm->directory_vector[index] = *e;
 
   clib_mem_set_heap (oldheap);
@@ -183,6 +184,9 @@ vlib_stats_remove_entry (u32 entry_index)
 
   memset (e, 0, sizeof (*e));
   e->type = STAT_DIR_TYPE_EMPTY;
+
+  e->value = sm->dir_vector_first_free_elt;
+  sm->dir_vector_first_free_elt = entry_index;
 }
 
 static void
diff --git a/src/vlib/stats/stats.h b/src/vlib/stats/stats.h
index ef43510b255..09a9aef002d 100644
--- a/src/vlib/stats/stats.h
+++ b/src/vlib/stats/stats.h
@@ -75,6 +75,7 @@ typedef struct
   /* statistics segment */
   uword *directory_vector_by_name;
   vlib_stats_entry_t *directory_vector;
+  u32 dir_vector_first_free_elt;
   u8 **nodes;
 
   /* Update interval */
-- 
cgit 1.2.3-korg