DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules()
@ 2015-08-26 19:25 Mark Smith
  2015-09-02  9:05 ` Ananyev, Konstantin
  0 siblings, 1 reply; 3+ messages in thread
From: Mark Smith @ 2015-08-26 19:25 UTC (permalink / raw)
  To: konstantin.ananyev, dev

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

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules()
  2015-08-26 19:25 [dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules() Mark Smith
@ 2015-09-02  9:05 ` Ananyev, Konstantin
  2015-10-24 20:54   ` Thomas Monjalon
  0 siblings, 1 reply; 3+ messages in thread
From: Ananyev, Konstantin @ 2015-09-02  9:05 UTC (permalink / raw)
  To: Mark Smith, dev



> -----Original Message-----
> From: Mark Smith [mailto:marks439@gmail.com]
> Sent: Wednesday, August 26, 2015 8:25 PM
> To: Ananyev, Konstantin; dev@dpdk.org
> Cc: rsanford@akamai.com; marsmith@akamai.com
> Subject: [PATCH] acl: Improve acl_bld.c sort_rules()
> 
> 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>

> ---

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules()
  2015-09-02  9:05 ` Ananyev, Konstantin
@ 2015-10-24 20:54   ` Thomas Monjalon
  0 siblings, 0 replies; 3+ messages in thread
From: Thomas Monjalon @ 2015-10-24 20:54 UTC (permalink / raw)
  To: Mark Smith; +Cc: dev

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

Applied, thanks

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2015-10-24 20:55 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-08-26 19:25 [dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules() Mark Smith
2015-09-02  9:05 ` Ananyev, Konstantin
2015-10-24 20:54   ` Thomas Monjalon

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