Re: [PATCH 3/3] Solving scalability issue: for chain list "name" searching.

[Patrick McHardy <kaber@trash.net>]

Jesper Dangaard Brouer wrote:
> Solving scalability issue: for chain list "name" searching.
> Functions: iptcc_find_label(), iptc_is_chain().
>
> Testing if a chain exist, requires a linearly walk of linked list with
> chain-names (doing a strcmp(3) in each step). Giving a worst-case
> runtime of O(n) where n is the number of chains.
>
> Why is this important to fix?! If only called once, this should not be
> a big concern, even-though the string compares are expensive.
>
> The performance issue arise with many chains for example; when using
> "iptables-restore", or when listing all "iptables -nL" rules, or when
> using CPAN IPTables::libiptc.
>
> Having 50k chains, the rule listing, with the command:
>  "./iptables -nL > /dev/null",
> Without patch it takes approximately 5 minutes,
> With the patch it takes 0.5 seconds.
>
> Listing without patch:
>  real    4m49.426s
>  user    4m37.993s
>  sys     0m0.280s
>
> Listing with patch:
>  real    0m0.558s
>  user    0m0.484s
>  sys     0m0.064s
>
> How is it solved?!
>
> The issue is solved introducing a new data structure, that allow us to
> do binary search of chain names. Thus, reducing the worst-case runtime
> to O(log n).
>
> Being more specific:
>
>  The new data structure is called "chain index", which is an array with
>  pointers into the chain list, with CHAIN_INDEX_BUCKET_LEN spacing.
>  This facilitates the ability to speedup chain list searching, by find
>  a more optimal starting points when searching the linked list.
>
>  The runtime complexity is actually also affected by this "bucket" size
>  concept. Thus, O(log(n/k) + k) where k is CHAIN_INDEX_BUCKET_LEN.
>
>  A nice property of the chain index, is that the "bucket" list
>  length is max CHAIN_INDEX_BUCKET_LEN (when just build, inserts will
>  change this). Oppose to hashing, where the "bucket" list length can
>  vary a lot.
>
> Signed-off-by: Jesper Dangaard Brouer <hawk@comx.dk>

This looks fine and survives some basic testing, so I've applied it.
Thanks a lot Jesper.