From fd4b6f78adcb85b437450be0d560773bdbb71f69 Mon Sep 17 00:00:00 2001 From: Mark Smith Date: Wed, 26 Aug 2015 15:25:18 -0400 Subject: [PATCH] acl: improve rules sorting Replace O(n^2) list sort with an O(n log n) merge sort. The merge sort is based on the solution suggested in: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf Tested sort_rules() improvement: 100K rules: O(n^2): 31382 milliseconds; O(n log n): 10 milliseconds 259K rules: O(n^2): 133753 milliseconds; O(n log n): 22 milliseconds Signed-off-by: Mark Smith Acked-by: Konstantin Ananyev --- lib/librte_acl/acl_bld.c | 102 ++++++++++++++++++++++++++++++--------- 1 file changed, 80 insertions(+), 22 deletions(-) diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c index e6f4530a7c..d78bc2d4d1 100644 --- a/lib/librte_acl/acl_bld.c +++ b/lib/librte_acl/acl_bld.c @@ -1163,36 +1163,94 @@ rule_cmp_wildness(struct rte_acl_build_rule *r1, struct rte_acl_build_rule *r2) return 0; } +/* + * Split the rte_acl_build_rule list into two lists. + */ +static void +rule_list_split(struct rte_acl_build_rule *source, + struct rte_acl_build_rule **list_a, + struct rte_acl_build_rule **list_b) +{ + struct rte_acl_build_rule *fast; + struct rte_acl_build_rule *slow; + + if (source == NULL || source->next == NULL) { + /* length < 2 cases */ + *list_a = source; + *list_b = NULL; + } else { + slow = source; + fast = source->next; + /* Advance 'fast' two nodes, and advance 'slow' one node */ + while (fast != NULL) { + fast = fast->next; + if (fast != NULL) { + slow = slow->next; + fast = fast->next; + } + } + /* 'slow' is before the midpoint in the list, so split it in two + at that point. */ + *list_a = source; + *list_b = slow->next; + slow->next = NULL; + } +} + +/* + * Merge two sorted lists. + */ +static struct rte_acl_build_rule * +rule_list_sorted_merge(struct rte_acl_build_rule *a, + struct rte_acl_build_rule *b) +{ + struct rte_acl_build_rule *result = NULL; + struct rte_acl_build_rule **last_next = &result; + + while (1) { + if (a == NULL) { + *last_next = b; + break; + } else if (b == NULL) { + *last_next = a; + break; + } + if (rule_cmp_wildness(a, b) >= 0) { + *last_next = a; + last_next = &a->next; + a = a->next; + } else { + *last_next = b; + last_next = &b->next; + b = b->next; + } + } + return result; +} + /* * Sort list of rules based on the rules wildness. + * Use recursive mergesort algorithm. */ static struct rte_acl_build_rule * sort_rules(struct rte_acl_build_rule *head) { - struct rte_acl_build_rule *new_head; - struct rte_acl_build_rule *l, *r, **p; - - new_head = NULL; - while (head != NULL) { - - /* remove element from the head of the old list. */ - r = head; - head = r->next; - r->next = NULL; - - /* walk through new sorted list to find a proper place. */ - for (p = &new_head; - (l = *p) != NULL && - rule_cmp_wildness(l, r) >= 0; - p = &l->next) - ; + struct rte_acl_build_rule *a; + struct rte_acl_build_rule *b; - /* insert element into the new sorted list. */ - r->next = *p; - *p = r; - } + /* Base case -- length 0 or 1 */ + if (head == NULL || head->next == NULL) + return head; + + /* Split head into 'a' and 'b' sublists */ + rule_list_split(head, &a, &b); + + /* Recursively sort the sublists */ + a = sort_rules(a); + b = sort_rules(b); - return new_head; + /* answer = merge the two sorted lists together */ + return rule_list_sorted_merge(a, b); } static uint32_t -- 2.20.1