path: root/include
diff options
author/C=EU/ST=EU/CN=Patrick McHardy/ </C=EU/ST=EU/CN=Patrick McHardy/>2008-01-15 17:18:15 +0000
committer/C=EU/ST=EU/CN=Patrick McHardy/ </C=EU/ST=EU/CN=Patrick McHardy/>2008-01-15 17:18:15 +0000
commit73ff92a2b0f338374a1f9830009d38b1f0ccaf42 (patch)
tree0f28dcefc52358d396bdf3e92d8023df3079f3c2 /include
parent9c5b6d5d14647a0caf5244619a1a2306e2f4e8ac (diff)
[PATCH 3/3] Solving scalability issue: for chain list "name" searching.
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 <>
Diffstat (limited to 'include')
0 files changed, 0 insertions, 0 deletions