[dpdk-dev] [PATCH] acl: Improve acl_bld.c sort_rules()
Thomas Monjalon
thomas.monjalon at 6wind.com
Sat Oct 24 22:54:09 CEST 2015
> > 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>
Applied, thanks
More information about the dev
mailing list