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

[Ananyev, Konstantin]

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

> ---