2.1.xxx makes Electric Fence 22x slower
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 10 lines · David S. Miller
Date: Thu, 10 Sep 1998 22:22:32 +0100
From: "Stephen C. Tweedie" <[email protected]>David, not only is the fuzzy hash O(n) (with low constant) for lookup, it is also O(n) for insert, requiring insertion onto two separate ordered lists...
No it isn't, for the insert case you have to find the neighbours anyways so the cost of a lookup is what you eat and this is an unavoidable overhead no matter what algorithm you use.
I don't think your arguments make sense. I think you can avoid finding the neighbors (explicitly) in insert by coding it differently. Unfortunately, I'm to busy to produce any code right now.
One the other hand, the argument that the algorithm is O(n) (instead of O(log n)) doesn't say that much unless we are talking of really big n:s (because of the low constant), which as I understood was not the case here.
By the way, I just found out that the very first Forth implementation also used a "fuzzy hashing" data structure to implement its dictionary. See http://www.dnai.com/~jfox/f70c5.html.
Regards,
Patrik Hägglund
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
Please read the FAQ at http://www.tux.org/lkml/faq.html