rushmorem / publicsuffix

An implementation of Mozilla's Public Suffix List in Rust
MIT License
96 stars 17 forks source link

Implement more effective search #20

Closed hiratara closed 5 years ago

hiratara commented 5 years ago

The current implementation uses a linear search of the list when searching for domains. However, it is too slow when it contains a lot of elements like the .jp domain.

This PR uses a tree data structure to speed up searches by 1,500% - 2,500% . These are benchmarks:

on https://github.com/rushmorem/publicsuffix/commit/832f35c9bac54c54d0ae4c38e821f29ce985a322 :

$ git checkout 832f35c9bac54c54d0ae4c38e821f29ce985a322
$ cargo +nightly bench
(..snip..)

     Running target/release/deps/bench-0b47487490889b4f

running 2 tests
test bench_com ... bench:      87,428 ns/iter (+/- 113,157)
test bench_jp  ... bench:     257,717 ns/iter (+/- 24,112)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out

on https://github.com/rushmorem/publicsuffix/commit/fe2fc1e4d9615eb40bf7a72a0d444bf770de22b8 :

$ git checkout fe2fc1e4d9615eb40bf7a72a0d444bf770de22b8
$ cargo +nightly bench
(..snip..)

     Running target/release/deps/bench-0b47487490889b4f

running 2 tests
test bench_com ... bench:       5,180 ns/iter (+/- 2,850)
test bench_jp  ... bench:      10,722 ns/iter (+/- 4,465)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out
rushmorem commented 5 years ago

Thanks!