OPTIM: startup: fast unique_id allocation for acl.
pattern_finalize_config() uses an inefficient algorithm which is a
problem with very large configuration files. This affects startup, and
therefore reload time. When haproxy is deployed as a router in a
Kubernetes cluster the generated configuration file may be large and
reloads are frequently occuring, which makes this a significant issue.
The old algorithm is O(n^2)
* allocate missing uids - O(n^2)
* sort linked list - O(n^2)
The new algorithm is O(n log n):
* find the user allocated uids - O(n)
* store them for efficient lookup - O(n log n)
* allocate missing uids - n times O(log n)
* sort all uids - O(n log n)
* convert back to linked list - O(n)
Performance examples, startup time in seconds:
pat_refs old new
1000 0.02 0.01
10000 2.1 0.04
20000 12.3 0.07
30000 27.9 0.10
40000 52.5 0.14
50000 77.5 0.17
Please backport to 1.8, 2.0 and 2.1.
(cherry picked from commit f91ac19299fe216a793ba6550dca06b688b31549)
Signed-off-by: Willy Tarreau <w@1wt.eu>
(cherry picked from commit af7f63f7df98c72f749acdff9682aa0872de7537)
Signed-off-by: Willy Tarreau <w@1wt.eu>
diff --git a/include/proto/pattern.h b/include/proto/pattern.h
index 5b99296..73d3cdc 100644
--- a/include/proto/pattern.h
+++ b/include/proto/pattern.h
@@ -37,7 +37,7 @@
extern struct pattern *(*pat_match_fcts[PAT_MATCH_NUM])(struct sample *, struct pattern_expr *, int);
extern int pat_match_types[PAT_MATCH_NUM];
-void pattern_finalize_config(void);
+int pattern_finalize_config(void);
/* return the PAT_MATCH_* index for match name "name", or < 0 if not found */
static inline int pat_find_match_name(const char *name)