Re: BIN_TREE vs SPLAY_TREE vs linked list

Duane Wessels:

>There are currently three data structures (splay trees, binary trees,
>and linked lists) which can be used for storing certain ACL entries (IP
>addresses, hostnames). In order to simplify the code, I've decided to
>only keep one of these methods.
>
>To see which one performed the best I ran a test with IP access
>controls. I used an access list of 388 hosts/networks and
>an input list of 4,146,495 IP addresses from 1 day's worth
>of the NLANR cache logs. Here are my results:
>
> TOTAL CPU TIME # OF COMPARISONS PER CHECK
> (seconds) MEDIAN MEAN
>-------------- -------------- -------- ------
> SPLAY 192.09 7 6.77
> BTREE 194.69 8 7.47
>LINKED LIST 200.21 12 16.9
>
>
>In terms of CPU time, the results are pretty close. The linked-list
>case took less than 5% more CPU time than the SPLAY case.

You're testing the case here that you have to find whether an item is in a
list/tree and with my LRU patch for the linked list method the results are
quite similar.

The reason I introduced BTREE (and at the same time somebody else SPLAY) was
for large blocking lists where you have to find that an item is *not* in the
list/tree; in case of LINKED LIST you have to traverse the whole list and
the tree algorithms should work much better here. So the test above doesn't
give a good comparison.

A good test would be to make a blocking list (dstdomain type) for e.g.
1000-5000 sites and do the test run again.

>My first preference would be to keep the linked-list approach because
>it is much simpler to implement and maintain, but I am also open to
>keeping SPLAY instead.

I'm afraid linked lists cannot handle big blocking lists.

>Does anyone care to make an argument for one or the other? Or perhaps
>provide some simulation data which shows SPLAY significantly beats
>linked-list in other cases (more ACL entries, a differnt type)?

I assume you used a stand-alone version of acl.c with some modifications. If
you publish the necessary information/patches I can do some test runs with
other ACLs this weekend.

Arjan

-- 
Arjan de Vet, Eindhoven, The Netherlands            <Arjan.deVet@adv.IAEhv.nl>
URL: http://www.IAEhv.nl/users/devet/       for PGP key: finger devet@IAEhv.nl