[dpdk-dev] [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 r

[dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules()

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

[dpdk-dev] [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 mil