Need multiple pubkeys load by file and search...
Why I never add a list of targets in any of my apps ?
When youre searching for 1 target public key, your app only does 1 comparison per candidate key.
But if youre searching for 10 target keys, now its gotta do 10 comparisons per candidate key.
This is called linear time complexity (O(n)), where:
n = number of target keys
Runtime scales directly with the number of keys
Heres how different methods stack up:
Brute-Force (O(n)) = ~10x slower
Hash Prefix (O(1)) = ~3.5x slower
Bloom Filter (O(1)) = ~2.5x slower
Multi-Key AVX2 = ~5x slower
Even with AVX2, you still gotta loop through all targets:
cpp
for (int i = 0; i < 100; i++) {
__m256i target = load_key(targets[i]);
__m256i cmp = _mm256_cmpeq_epi8(candidate, target);
if (_mm256_movemask_epi8(cmp) == 0xFFFFFFFF) {
/ Match found for targets[i]
}
}
100x more comparisons = 100x slower in the worst case.
Yeah, the CPU tries to predict the loop, but with 100 targets, it messes up more often, pipeline stalls happen.
Whats your Bloomfilter implementation like ? 2.5x seems like a lot ?
