On Monday 19 February 2007 16:14, Eric Dumazet wrote: > > Because O(1) is different of O(log(N)) ? > if N = 2^20, it certainly makes a difference. > Yes, 1% of chains might have a length > 10, but yet 99% of the lookups are > touching less than 4 cache lines. > With a binary tree, log(2^20) is 20. or maybe not ? If you tell me it's 4, > I will be very pleased. >
Here is the tcp ehash chain length distribution on a real server : ehash_addr=0xffff810476000000 ehash_size=1048576 333835 used chains, 3365 used twchains Distribution of sockets/chain length [chain length]:number of sockets [1]:221019 37.4645% [2]:56590 56.6495% [3]:21250 67.4556% [4]:12534 75.9541% [5]:8677 83.3082% [6]:5862 89.2701% [7]:3640 93.5892% [8]:2219 96.5983% [9]:1083 98.2505% [10]:539 99.1642% [11]:244 99.6191% [12]:112 99.8469% [13]:39 99.9329% [14]:16 99.9708% [15]:6 99.9861% [16]:3 99.9942% [17]:2 100% total : 589942 sockets So even with a lazy hash function, 89 % of lookups are satisfied with less than 6 compares. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
