Re: SplayTrees/Updated patch for long srcdomain and dstdomain ACLs

G'day Arjan!

On Feb 9, 9:33pm, Arjan de Vet wrote:
> Subject: SplayTrees/Updated patch for long srcdomain and dstdomain ACLs
> In article <9702081735.ZM6708@fatboy.geog.unsw.edu.au> you write:
>
> >> the Changelog of Squid 1.1.6 mentions Splay tree for fast IP access
> >> checking.
> >
> >The structure used to hold the src type acl's has been changed from a linked
> >list, that places the last requested acl into the second place of the list,
> >into a splay tree.
>
> Was there any reason why you didn't use splay trees for srcdomain and
> dstdomain too?

*chuckle*

It's done ... the patch just didn't make it to Duane in time for 1.1.6 :(( They
are a little easier than the IP stuff, as the compare procedure is simpler, a
strcmp vs fiddling with IP ranges.

> >A splay tree is a type of balanced tree, but it is self adjusting. The last
> >requested acl is placed at the root of the tree. A neat Java demo and
further
> >explanation can be found at:
> >
> >http://langevin.usc.edu/~ierardi/classes/SplayTree/
>
> I've been playing with the applets a little bit but a Splay Tree can
> become unbalanced fairly easy, in worst case it can become a linked list
> again.

If this is the form that the tree takes after self-adjusting, sobeit. The
overall efficiency of the tree is still O(log n). Given that we assume access
is not made evenly by all sites listed in the acl at one time, the tree will be
reorganised to give the best lookup for those clients that are using the proxy
at the time. Least checked clients will be at the end of the tree. Balance is
not a concern.

Even if the tree did adjust into a linked list, a search for the last element
would cause the most adjustment of the tree. It would only be a linked list for
one search.

> >It has been #ifdef out as there appeares to be an, as yet, unsolved bug :(
>
> What kind of bug? I've been working on similar things and putting Squid's
> IP lists into binary trees is not trivial I think (see URL above).

I'm not sure :((

The code worked on the small lists that I made up for testing, but Duane said
he run into some problems when he put it on the NLANR caches. I am unable to
test acl checks from many clients as not too many clients use my proxy.

It should work. Have you defined it in and had problems?

> I hope we can merge our efforts into one solution for fast ACLs in Squid.

Splay trees seem ideal to meet Squid's requirements. Hopefully faster access
than a balanced tree and simpler to implement than hashing.

Later
Ed

-- 
Ed Knowles aka Jasper				   Phone : +61 2 9385 4962
E-mail: ed@fatboy.geog.unsw.edu.au	           Fax   : +61 2 9313 7878
            What I lack in morals I make up for in principles.