DPDK patches and discussions
 help / color / mirror / Atom feed
From: Mark Smith <marks439@gmail.com>
To: konstantin.ananyev@intel.com, dev@dpdk.org
Subject: [dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules()
Date: Wed, 26 Aug 2015 15:25:18 -0400	[thread overview]
Message-ID: <1440617118-1583-1-git-send-email-marsmith@akamai.com> (raw)

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>
---
 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

             reply	other threads:[~2015-08-26 19:26 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-08-26 19:25 Mark Smith [this message]
2015-09-02  9:05 ` Ananyev, Konstantin
2015-10-24 20:54   ` Thomas Monjalon

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1440617118-1583-1-git-send-email-marsmith@akamai.com \
    --to=marks439@gmail.com \
    --cc=dev@dpdk.org \
    --cc=konstantin.ananyev@intel.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).