tree 15ee52eaddd87d67335ba1cbc901f7600943bcdf
parent 750bb0c6bc93ed51ceb9968c8d31756ff6a5036f
author Carl Henrik Lunde <carl.henrik.lunde@sparebank1.no> 1582818350 +0100
committer Willy Tarreau <w@1wt.eu> 1585670923 +0200
encoding latin1

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>