OPTIM: startup: fast unique_id allocation for acl.
authorCarl Henrik Lunde <carl.henrik.lunde@sparebank1.no>
Thu, 27 Feb 2020 15:45:50 +0000 (16:45 +0100)
committerWilly Tarreau <w@1wt.eu>
Fri, 6 Mar 2020 07:11:58 +0000 (08:11 +0100)
commitf91ac19299fe216a793ba6550dca06b688b31549
treead7f19bdcc5304951f869f544ec27ffece2322ce
parenta17e66289c08a5bfadc1bb5b5f2c618c9299fe1b
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.
include/proto/pattern.h
src/haproxy.c
src/pattern.c