Re: Squid is becoming slow with 3000 ACL's ...

Duane Wessels wrote:

> The way the tree searching works is that if a comparison at one
> node returns "less than", then we know the match, if any, must
> be down one side of the tree, and cannot be down the other side.

Who said that trees needs to be used to do sorts? Use-frequency sorting
of "unsortable" things is much easier done by using doubly-linked lists
and some simple usage counters that triggers a move when a entry is used
more often than the one in front of it, or by having a couple of buchets
for things used by different frequency. Which one that is most effective
depends on how big jump the average priority shift is.

Frequency balancing of trees is another issue, but it requires that the
"things" is sortable into a tree, and thus does not apply to regexps
unless you filter out regexps with certain properties that make them
sortable, like prefix or suffix based regexps.

---
Henrik Nordström
Sparetime Squid Hacker