On 10/16/2013 04:01 PM, Prakash Surya wrote: > On Wed, Oct 16, 2013 at 11:55:10AM -0700, [email protected] wrote: >> In a nutshell Richard -- you're looking at this from a computer science >> theory perspective, without understanding the pragmatic issues. The >> pragmatic engineering solution is to keep the chains small, and optimize a >> solution for small chains. That's what Sašo has done. This is the >> difference between an engineer and a scientist. In this particular case, my >> KISS values definitely lead me more towards the engineering approach. >> >> Its true in the very worst case AVL trees will win, and have a much less bad >> worst case. But its also true that if Sašo's work at keeping the chain >> sizes is small is effective, then the AVL trees introduce substantial >> complexity and hurt performance in the typical case. The worst case should >> be sufficiently exceedingly rarer that we can simply discount it. If it >> isn't, then we need to go back and rethink our hash algorithm. > > I agree. We *need* to keep the chains short. Period. Thus, asymptotic > analysis doesn't really apply here.
If we are going to be concerned about further tuning to keep the chains short, then I should say that I do not think the chains are short enough. I would expect the AVL trees to start winning above an average chain size of 4. My point is that we could use AVL trees to handle collisions and not worry about chain length so much. I find letting AVL trees handle collisions preferable to: 1. Increasing the hash table to the point where a system not even using ZFS (but having it loaded) uses more space to store an empty hash table than it uses to store the ZFS source code. 2. The complexity of implementing extendible hash tables. Alternatively, we could just stop worrying about chain length and go with what Saso has. It is clearly better than what we have now.
signature.asc
Description: OpenPGP digital signature
_______________________________________________ developer mailing list [email protected] http://lists.open-zfs.org/mailman/listinfo/developer
