> -----Original Message----- > From: Mark Smith [mailto:marks439 at gmail.com] > Sent: Wednesday, August 26, 2015 8:25 PM > To: Ananyev, Konstantin; dev at dpdk.org > Cc: rsanford at akamai.com; marsmith at 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 at akamai.com>
Acked-by: Konstantin Ananyev <konstantin.ananyev at intel.com> > ---