commit eecec8ceba7dcd572ff557726e7e253488b13656
author Damjan Marion <damarion@cisco.com> Wed Apr 06 12:06:41 2022 +0200
committer Ole Tr�an <otroan@employees.org> Wed Apr 06 11:25:03 2022 +0000
tree e7964d2e0798bf9248acc9a1ef3c0ae055a3aee4
parent 8271dfdff3cf65e3b077e149d4600bd90d2b4b03

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

diff --git a/src/vlib/stats/init.c b/src/vlib/stats/init.c
index 3cfbd2d..2a7b6f5 100644
--- a/src/vlib/stats/init.c
+++ b/src/vlib/stats/init.c
@@ -98,6 +98,7 @@
 
   /* 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;
 

src/vlib/stats/stats.c

diff --git a/src/vlib/stats/stats.c b/src/vlib/stats/stats.c
index 9063fa3..cb29dda 100644
--- a/src/vlib/stats/stats.c
+++ b/src/vlib/stats/stats.c
@@ -106,20 +106,21 @@
 {
   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 @@
 
   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

src/vlib/stats/stats.h

diff --git a/src/vlib/stats/stats.h b/src/vlib/stats/stats.h
index ef43510..09a9aef 100644
--- a/src/vlib/stats/stats.h
+++ b/src/vlib/stats/stats.h
@@ -75,6 +75,7 @@
   /* statistics segment */
   uword *directory_vector_by_name;
   vlib_stats_entry_t *directory_vector;
+  u32 dir_vector_first_free_elt;
   u8 **nodes;
 
   /* Update interval */