matcher

After a tweet ( https://twitter.com/veorq/status/637616767058223104 ), I wanted
to see if my suggestion if generating a finite state machine with ragel was
actually faster.

Turns out it wasn't.

At least not for only 1000 keys anyway.  Ragel segfaulted when trying to create
a machine for 200,000 keys. :(

I also tested armon/go-radix and cloudflare/ahocorasick.

My test keys were the top 1000 email domains from the Linkedin leak a while ago.
I've been using it as a reasonable real-world test set every since I watched
John Graham-Cumming's talk https://www.youtube.com/watch?v=_41bkNr7eik

Anyways, searching 200000 inputs for the thousand keys 10 times; we see the ranking

(This version built with 1.8beta2)

<dgryski@kamek[matcher] ʕ╯◔ϖ◔ʔ╯ > for i in radix aho bsearch mafsa mph ragel map; do ./matcher  -f ./alldomains.txt -which $i; done
2016/12/28 11:37:25 using matcher=radix
2016/12/28 11:37:30 time.Since(t0)=4.863440361s
2016/12/28 11:37:30 found=15965200
2016/12/28 11:37:32 using matcher=aho
2016/12/28 11:37:36 time.Since(t0)=4.603819772s
2016/12/28 11:37:36 found=16274730
2016/12/28 11:37:38 using matcher=bsearch
2016/12/28 11:37:41 time.Since(t0)=3.437610561s
2016/12/28 11:37:41 found=15965200
2016/12/28 11:37:42 using matcher=mafsa
2016/12/28 11:37:46 time.Since(t0)=3.183283031s
2016/12/28 11:37:46 found=15965200
2016/12/28 11:37:47 using matcher=mph
2016/12/28 11:37:48 time.Since(t0)=1.060979543s
2016/12/28 11:37:48 found=15965200
2016/12/28 11:37:50 using matcher=ragel
2016/12/28 11:37:51 time.Since(t0)=959.092265ms
2016/12/28 11:37:51 found=15965200
2016/12/28 11:37:52 using matcher=map
2016/12/28 11:37:53 time.Since(t0)=698.283411ms
2016/12/28 11:37:53 found=15965200