4 ms·
By reading the OP's comment here, I think it'd be better to update the article with some description on the requirement and why you choose a linear scan initial
by summerlight 8y ago
By reading the OP's comment here, I think it'd be better to update the article with some description on the requirement and why you choose a linear scan initially. Without this understanding, it's really easy to say "why not hash table?".
- erentz 8y agoNot certain but there are two advantages of using a trie in this case, 1) you don’t have to hash the IP address (that takes time too, and is for every packet remember), and 2) you can easily represent whole IP subnets in a trie as one node (though it doesn’t say in the article if they do this, it’s common to block a subnet in a blacklist).
- viraptor 8y ago> you don’t have to hash the IP address That's not necessarily slow. Or at least not as slow as multiple potential cache misses while traversing a tree. Once you know how many addresses you're expecting to have, you can make a hash indexing into a preallocated array which will never get smaller - if it fits into a few cache lines, it's great.
- ghayes 8y agoYeah, though I think the concern is that the article headline acts as if the default would ever have been linear scan. It's like saying "Microwave Ovens: How to make cooking 1,000 times faster" and then comparing to direct solar heating and cooking.
- groestl 8y agoI'm pretty sure it's number 2, as the prefix search requirement is probably the reason why they went with the linear search in the first place, and didn't just use a hash map.