summaryrefslogtreecommitdiff
path: root/lib/librte_acl
diff options
context:
space:
mode:
authorMark Smith <marsmith@akamai.com>2015-08-26 15:25:18 -0400
committerThomas Monjalon <thomas.monjalon@6wind.com>2015-10-24 22:52:53 +0200
commitfd4b6f78adcb85b437450be0d560773bdbb71f69 (patch)
tree1084f3ed71b1676922fae1d8abf741a9df02afea /lib/librte_acl
parent7acf894d07d1cfbab50c525300e5c61fce2468d6 (diff)
downloaddpdk-fd4b6f78adcb85b437450be0d560773bdbb71f69.zip
dpdk-fd4b6f78adcb85b437450be0d560773bdbb71f69.tar.gz
dpdk-fd4b6f78adcb85b437450be0d560773bdbb71f69.tar.xz
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 <marsmith@akamai.com> Acked-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
Diffstat (limited to 'lib/librte_acl')
-rw-r--r--lib/librte_acl/acl_bld.c102
1 files changed, 80 insertions, 22 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