BIN_TREE vs SPLAY_TREE vs linked list

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.

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.

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)?

Also, in doing this simulation, I found a rather serious bug with some
modifications I'd made to lib/tree.c. A patch follows in a separate
message.

Duane W.
Received on Tue Jul 29 2003 - 13:15:47 MDT