From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ig0-f178.google.com (mail-ig0-f178.google.com [209.85.213.178]) by dpdk.org (Postfix) with ESMTP id A1FFB5698 for ; Wed, 26 Aug 2015 21:26:10 +0200 (CEST) Received: by igui7 with SMTP id i7so45273975igu.1 for ; Wed, 26 Aug 2015 12:26:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:date:message-id; bh=LyN3uOSTgRi+gEFQxL5HFshn3WP1k5foe4JT8+cIkf0=; b=sjLZGX5sciC2rvZicO0j2aNPRK9CGb7OJbP7icdCoDvNxn0HlJryF/W1FIaD/xU9FR V79y5Mo/9H1kuLa2ucAUcOSPbgqSfZZoymg5Iy4UTFZTN8JaM7v2poc7SJwmaz86qDNy KyQ3rUpedQOCL5vBkY1EJHtbctDwuRUV/e0HU7Wk5x6tbYlm0BQD30w+yhcR/nSRykCe SqMa63A+PYRjBNoHMCrV+zOFhoyPdDnq4mN6dq/Xk/V06Fxp0mth1VacOkUPzhT9VugE lF2Rlw9thvOMb46NhMnLdmJ4O8N1R4UEXyxCLObAJf2Vrl+gqab+45XVRllMEhpPscVN yEyw== X-Received: by 10.50.36.101 with SMTP id p5mr6475363igj.58.1440617170015; Wed, 26 Aug 2015 12:26:10 -0700 (PDT) Received: from localhost.localdomain ([66.11.255.14]) by smtp.gmail.com with ESMTPSA id cr1sm14093igb.15.2015.08.26.12.26.09 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 26 Aug 2015 12:26:09 -0700 (PDT) From: Mark Smith X-Google-Original-From: Mark Smith To: konstantin.ananyev@intel.com, dev@dpdk.org Date: Wed, 26 Aug 2015 15:25:18 -0400 Message-Id: <1440617118-1583-1-git-send-email-marsmith@akamai.com> X-Mailer: git-send-email 1.7.1 Subject: [dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules() X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 26 Aug 2015 19:26:11 -0000 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 --- 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