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/src/haproxy.c b/src/haproxy.c
index c878518..138b54e 100644
--- a/src/haproxy.c
+++ b/src/haproxy.c
@@ -1858,7 +1858,11 @@
exit(1);
}
- pattern_finalize_config();
+ err_code |= pattern_finalize_config();
+ if (err_code & (ERR_ABORT|ERR_FATAL)) {
+ ha_alert("Failed to finalize pattern config.\n");
+ exit(1);
+ }
/* recompute the amount of per-process memory depending on nbproc and
* the shared SSL cache size (allowed to exist in all processes).