Re: [code] [for discussion] map-trie

On 12/06/2014 10:43 a.m., Kinkie wrote:
> Hi,
> I've done some benchmarking, here are the results so far:
> The proposal I'm suggesting for dstdomain acl is at
> lp:~kinkie/squid/flexitrie . It uses the level-compact trie approach
> I've described in this thread (NOT a Patricia trie). As a comparison,
> lp:~kinkie/squid/domaindata-benchmark implements the same benchmark
> using the current splay-based implementation.
>
> I've implemented a quick-n-dirty benchmarking tool
> (src/acl/testDomainDataPerf); it takes as input an acl definition -
> one dstdomain per line, as if it was included in squid.conf, and a
> hostname list file (one destination hostname per line).
>
> I've run both variants of the code against the same dataset: a 4k
> entries domain list, containing both hostnames and domain names, and a
> 18M entries list of destination hostnames, both matching and not
> matching entries in the domain list (about 7.5M hits, 10.5M misses).
>
> Tested 10 times on a Core 2 PC with plenty of RAM - source datasets
> are in the fs cache.
> level-compact-trie: the mean time is 11 sec; all runs take between
> 10.782 and 11.354 secs; 18 Mb of core used
> full-trie: mean is 7.5 secs +- 0.2secs; 85 Mb of core.
> splay-based: mean time is 16.3sec; all runs take between 16.193 and
> 16.427 secs; 14 Mb of core
>
> I expect compact-trie to scale better as the number of entries in the
> list grows and with the number of clients and requests per second;
> furthermore using it removes 50-100 LOC, and makes code more readable.
>
> IMO it is the best compromise in terms of performance, resources
> useage and expected scalability; before pursuing this further however
> I'd like to have some feedback.

Does making compact vs full trie configurable affect compexity much? I
think we have sufficiently wide customer base that people will want to
go further now that its known there is a much faster version.

Amos
Received on Thu Jun 12 2014 - 09:28:37 MDT