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 <marsmith at akamai.com>
---
lib/librte_acl/acl_bld.c | 104 +++++++++++++++++++++++++++++++++++----------
1 files changed, 81 insertions(+), 23 deletions(-)
diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c
index e6f4530..d78bc2d 100644
--- a/lib/librte_acl/acl_bld.c
+++ b/lib/librte_acl/acl_bld.c
@@ -1164,35 +1164,93 @@ rule_cmp_wildness(struct rte_acl_build_rule *r1, struct
rte_acl_build_rule *r2)
}
/*
+ * 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
--
1.7.1
