summaryrefslogtreecommitdiffstats
path: root/libiptc/linux_stddef.h
diff options
context:
space:
mode:
authorJesper Dangaard Brouer <hawk@comx.dk>2008-01-15 17:18:15 +0000
committerPatrick McHardy <kaber@trash.net>2008-01-15 17:18:15 +0000
commit01444da4cb70417d2dc2643e2d48c70de7ff8e96 (patch)
tree0f28dcefc52358d396bdf3e92d8023df3079f3c2 /libiptc/linux_stddef.h
parent48bde40e73b45ad134d32cde88b779fe509faf64 (diff)
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 <hawk@comx.dk>
Diffstat (limited to 'libiptc/linux_stddef.h')
0 files changed, 0 insertions, 0 deletions