Hello, attached is a patch to improve startup/reload time for
OpenShift and large configuration files in general.

We have an issue in our OpenShift cluster with slow router
(HAProxy) reloads when we have many routes. This patch solved
our issue and reduces reload time from 45 seconds to 0.7
seconds. The cluster has 11 000 routes.

Please review the attached patch. There are some minor
optimizations possible, but considering the resulting performance
improvement with the generic algorithm I have not added anything
for this initial patch.

To generate a large configuration file, you can use the following
script:

#!/usr/bin/env python
import sys
print("""listen foo
        bind 0.0.0.0:8443
        mode http""")

for a in range(int(sys.argv[1])):
    if a % 2 == 0:
        print(" http-request set-header X-Forwarded-Port %d if { path_beg -i 
foo%d }" % (a, a))
    else:
        print(" http-request set-header X-Forwarded-Port %d if { path_beg -i 
foo%d -u %d }" % (a, a, a))

-- 
Best regards,
Carl Henrik Lunde
From 541a1b0a026730ec1fc7c43e4f4c48f3442a66ec Mon Sep 17 00:00:00 2001
From: Carl Henrik Lunde <carl.henrik.lu...@sparebank1.no>
Date: Wed, 5 Feb 2020 21:28:26 +0100
Subject: [PATCH] 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 and 2.0.
---
 src/pattern.c | 86 +++++++++++++++++++++++++++++++++------------------
 1 file changed, 56 insertions(+), 30 deletions(-)

diff --git a/src/pattern.c b/src/pattern.c
index 90067cd23..0c516d482 100644
--- a/src/pattern.c
+++ b/src/pattern.c
@@ -2643,53 +2643,79 @@ int pattern_delete(struct pattern_expr *expr, struct pat_ref_elt *ref)
 	return 1;
 }
 
-/* This function finalize the configuration parsing. Its set all the
+/* This function compares two pat_ref** on unique_id */
+static int cmp_pat_ref(const void *_a, const void *_b)
+{
+	struct pat_ref * const *a = _a;
+	struct pat_ref * const *b = _b;
+
+	if ((*a)->unique_id < (*b)->unique_id)
+		return -1;
+	else if ((*a)->unique_id > (*b)->unique_id)
+		return 1;
+	return 0;
+}
+
+/* This function finalize the configuration parsing. It sets all the
  * automatic ids
  */
 void pattern_finalize_config(void)
 {
-	int i = 0;
-	struct pat_ref *ref, *ref2, *ref3;
+	int len = 0;
+	int unassigned_pos = 0;
+	int next_unique_id = 0;
+	int i, j;
+	struct pat_ref *ref, **arr;
 	struct list pr = LIST_HEAD_INIT(pr);
 
 	pat_lru_seed = random();
 
+	/* Count pat_refs with user defined unique_id and totalt count */
 	list_for_each_entry(ref, &pattern_reference, list) {
-		if (ref->unique_id == -1) {
-			/* Look for the first free id. */
-			while (1) {
-				list_for_each_entry(ref2, &pattern_reference, list) {
-					if (ref2->unique_id == i) {
-						i++;
-						break;
-					}
-				}
-				if (&ref2->list == &pattern_reference)
-					break;
-			}
+		len++;
+		if (ref->unique_id != -1)
+			unassigned_pos++;
+	}
 
-			/* Uses the unique id and increment it for the next entry. */
-			ref->unique_id = i;
-			i++;
-		}
+	arr = calloc(len, sizeof(struct pat_ref *));
+	if (arr == NULL) {
+		ha_alert("Out of memory error\n");
+		exit(EXIT_FAILURE);
 	}
 
-	/* This sort the reference list by id. */
-	list_for_each_entry_safe(ref, ref2, &pattern_reference, list) {
-		LIST_DEL(&ref->list);
-		list_for_each_entry(ref3, &pr, list) {
-			if (ref->unique_id < ref3->unique_id) {
-				LIST_ADDQ(&ref3->list, &ref->list);
-				break;
-			}
-		}
-		if (&ref3->list == &pr)
-			LIST_ADDQ(&pr, &ref->list);
+	i = 0;
+	j = unassigned_pos;
+	list_for_each_entry(ref, &pattern_reference, list) {
+		if (ref->unique_id != -1)
+			arr[i++] = ref;
+		else
+			arr[j++] = ref;
 	}
 
+	/* Sort first segment of array with user-defined unique ids for
+	 * fast lookup when generating unique ids
+	 */
+	qsort(arr, unassigned_pos, sizeof(struct pat_ref *), cmp_pat_ref);
+
+	/* Assign unique ids to the rest of the elements */
+	for (i = unassigned_pos; i < len; i++) {
+		do {
+			arr[i]->unique_id = next_unique_id++;
+		} while (bsearch(&arr[i], arr, unassigned_pos, sizeof(struct pat_ref *), cmp_pat_ref));
+	}
+
+	/* Sort complete array */
+	qsort(arr, len, sizeof(struct pat_ref *), cmp_pat_ref);
+
+	/* Convert back to linked list */
+	for (i = 0; i < len; i++)
+		LIST_ADDQ(&pr, &arr[i]->list);
+
 	/* swap root */
 	LIST_ADD(&pr, &pattern_reference);
 	LIST_DEL(&pr);
+
+	free(arr);
 }
 
 static int pattern_per_thread_lru_alloc()
-- 
2.18.1

Reply via email to