On Wednesday 21 February 2007 10:27, Evgeniy Polyakov wrote: > On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet ([EMAIL PROTECTED]) wrote: > > On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote: > > > I shown that numbers 4 times already, do you read mails and links? > > > Did you see an artifact Eric showed with his data? > > > > I showed all your thinking is wrong. > > You mix all the time distribution fairness and complexity of searching > for collisions. Jenkins hash is unfair - having Linux random generator > as attacker's tool we end up in the case, when jenkins hash has some > chains with 5 times longer length. > > Short history: > I showed that jenkins is unfair, you confirmed that with your data. > Another question is about complexity of searching for collisions - you > showed that with xor it is quite easy and with jenkins it is complex, > then I showed that it is not that complex to find collisions in jenkins > too.
Again here is your 'test' enter_hash(u32 val) { counter[val & mask]++; } for (i = 0 ; i < 1000 ; i++) enter_hash(CONSTANT1) for (i = 0 ; i < 1000 ; i++) enter_hash(CONSTANT2) Oh my god, I have two chains with 1000 elems in it. Real data are : 1) XOR hash, with a load factor of 0.41 Distribution of sockets/chain length [chain length]:number of sockets [0]:752255 0% [1]:208850 47.455% [2]:54281 72.1225% [3]:19236 85.235% [4]:8199 92.6869% [5]:3487 96.6485% [6]:1489 98.6785% [7]:515 99.4976% [8]:192 99.8466% [9]:53 99.955% [10]:14 99.9868% [11]:3 99.9943% [12]:1 99.997% [13]:1 100% total : 440101 sockets, Avg lookup cost=3.07896 cache lines 2) Jenkins hash, same load factor [0]:688813 0% [1]:289874 65.8653% [2]:60452 93.3372% [3]:8493 99.1266% [4]:879 99.9255% [5]:62 99.9959% [6]:3 100% total : 440101 sockets, Avg lookup cost=2.4175 cache lines - 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