I would like to contribute some performance optimization of the julia base search function: _searchindex. I have prepared a benchmark package and experiments with several code variants here:
My current suggestion is function SearchBenchmarks.bloom_best, which improves runtime performance in almost all tested scenarios by 20% and more. I put all details and benchmark results in the package. Before preparing a pull request, I would like to discuss my suggestions in this topic, hopefully resulting in further improvements by the community.
In addition to the performance-driven changes, I suggest to add an API which separates search initialization and search kernel into two methods. In many applications, the same string (or byte sequence) is searched again and again. In such a scenario, separating initialization and kernel further improves performance, and allows to use algorithms which have an initialization too expensive for a “one-shot search”. In particular, I have an implementation of a Boyer-Moore search variant in mind, which can double search throughput in many scenarios, compared to my experiments with bloom filter based implementations like the current one in julia base.
As a teaser, here the runtime in mSec in relation to pattern size for searches with the julia base implementation and some variations (bloom_*) and my Boyer-Moore variant. All details are in the package.