Re: BIN_TREE vs SPLAY_TREE vs linked list

From: Arjan de Vet <>
Date: Fri, 27 Mar 1998 08:29:44 +0100 (CET)

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:
> (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 de Vet, Eindhoven, The Netherlands            <>
URL:       for PGP key: finger
Received on Thu Mar 26 1998 - 23:41:06 MST

This archive was generated by hypermail pre-2.1.9 : Tue Dec 09 2003 - 16:39:28 MST