From 5d350d1e5032fed589739a87b30fc857e3ed2ee1 Mon Sep 17 00:00:00 2001
From: Willy Tarreau <w@1wt.eu>
Date: Sun, 15 Sep 2024 13:06:08 +0200
Subject: [PATCH] OPTIM: vars: use multiple name heads in the vars struct

Given that the original list-based version was using a list head as the
root of the variables, while the tree is using a single pointer, it made
sense to reuse that space to place multiple roots, indexed on the lower
bits of the name hash. Two roots slightly increase the performance level,
but the best gain is obtained with 4 roots. The performance is now always
above that of the list, even with small counts, and with 100 vars, it's
21% higher than before, or 67% higher than with the list.

We keep the same lock (it could have made sense to use one lock per head),
because most of the variables in large configs are attached to a stream
or a session, hence are not shared between threads. Thus there's no point
in sharding the pointer.
---
 include/haproxy/vars-t.h |  3 ++-
 include/haproxy/vars.h   |  9 ++++++---
 src/vars.c               | 17 ++++++++++-------
 3 files changed, 18 insertions(+), 11 deletions(-)

diff --git a/include/haproxy/vars-t.h b/include/haproxy/vars-t.h
index 3ad8c73ac6..7a709bda20 100644
--- a/include/haproxy/vars-t.h
+++ b/include/haproxy/vars-t.h
@@ -48,8 +48,9 @@ enum vars_scope {
 	SCOPE_CHECK,
 };
 
+#define VAR_NAME_ROOTS	4
 struct vars {
-	struct ceb_node *name_root;
+	struct ceb_node *name_root[VAR_NAME_ROOTS];
 	enum vars_scope scope;
 	unsigned int size;
 	__decl_thread(HA_RWLOCK_T rwlock);
diff --git a/include/haproxy/vars.h b/include/haproxy/vars.h
index 86dcf2d46e..bfadee5edb 100644
--- a/include/haproxy/vars.h
+++ b/include/haproxy/vars.h
@@ -83,10 +83,13 @@ static inline void vars_prune(struct vars *vars, struct session *sess, struct st
 	struct ceb_node *node;
 	struct var *var;
 	unsigned int size = 0;
+	int i;
 
-	while ((node = cebu64_first(&vars->name_root))) {
-		var = container_of(node, struct var, node);
-		size += var_clear(vars, var, 1);
+	for (i = 0; i < VAR_NAME_ROOTS; i++) {
+		while ((node = cebu64_first(&vars->name_root[i]))) {
+			var = container_of(node, struct var, node);
+			size += var_clear(vars, var, 1);
+		}
 	}
 
 	if (!size)
diff --git a/src/vars.c b/src/vars.c
index 6ba82b7e05..7c4bdd4bad 100644
--- a/src/vars.c
+++ b/src/vars.c
@@ -190,7 +190,7 @@ unsigned int var_clear(struct vars *vars, struct var *var, int force)
 	var->data.type = SMP_T_ANY;
 
 	if (!(var->flags & VF_PERMANENT) || force) {
-		cebu64_delete(&vars->name_root, &var->node);
+		cebu64_delete(&vars->name_root[var->name_hash % VAR_NAME_ROOTS], &var->node);
 		pool_free(var_pool, var);
 		size += sizeof(struct var);
 	}
@@ -205,10 +205,13 @@ void vars_prune_per_sess(struct vars *vars)
 	struct ceb_node *node;
 	struct var *var;
 	unsigned int size = 0;
+	int i;
 
-	while ((node = cebu64_first(&vars->name_root))) {
-		var = container_of(node, struct var, node);
-		size += var_clear(vars, var, 1);
+	for (i = 0; i < VAR_NAME_ROOTS; i++) {
+		while ((node = cebu64_first(&vars->name_root[i]))) {
+			var = container_of(node, struct var, node);
+			size += var_clear(vars, var, 1);
+		}
 	}
 
 	if (!size)
@@ -223,7 +226,7 @@ void vars_prune_per_sess(struct vars *vars)
 /* This function initializes a variables list head */
 void vars_init_head(struct vars *vars, enum vars_scope scope)
 {
-	vars->name_root = NULL;
+	memset(vars->name_root, 0, sizeof(vars->name_root));
 	vars->scope = scope;
 	vars->size = 0;
 	HA_RWLOCK_INIT(&vars->rwlock);
@@ -333,7 +336,7 @@ static struct var *var_get(struct vars *vars, uint64_t name_hash)
 {
 	struct ceb_node *node;
 
-	node = cebu64_lookup(&vars->name_root, name_hash);
+	node = cebu64_lookup(&vars->name_root[name_hash % VAR_NAME_ROOTS], name_hash);
 	if (node)
 		return container_of(node, struct var, node);
 
@@ -436,7 +439,7 @@ int var_set(const struct var_desc *desc, struct sample *smp, uint flags)
 		var->name_hash = desc->name_hash;
 		var->flags = flags & VF_PERMANENT;
 		var->data.type = SMP_T_ANY;
-		cebu64_insert(&vars->name_root, &var->node);
+		cebu64_insert(&vars->name_root[var->name_hash % VAR_NAME_ROOTS], &var->node);
 	}
 
 	/* A variable of type SMP_T_ANY is considered as unset (either created
-- 
2.39.5