On 10/16/13 6:04 AM, sanjeev bagewadi wrote: > Joining in late into this discussion.... > > I would tend to agree with Richard. I think it is worth trying out AVL > for the entries in a bucket. > That should make the search O(log (n)) instead of O(n) where 'n' is the > chain length.
Not quite. For AVL trees it's O(log(X)) where X is the number of buffers in the tree, but for hash tables it's O(Y) where Y is the chain length. As long as Y < log(X), then hash tables will be faster, and in my testing they are. What's worse, AVL trees are even more expensive in memory, since sizeof (avl_node_t) == 24, whereas hash tables only keep one arc_buf_hdr_t * per buffer (to point to the next one in the chain) plus one start arc_buf_hdr_t * in the hash table per chain. Cheers, -- Saso _______________________________________________ developer mailing list [email protected] http://lists.open-zfs.org/mailman/listinfo/developer
