lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Date: Tue, 20 Feb 2007 15:11:25 +0300 From: Evgeniy Polyakov <johnpol@....mipt.ru> To: Eric Dumazet <dada1@...mosbay.com> Cc: akepner@....com, linux@...izon.com, davem@...emloft.net, netdev@...r.kernel.org, bcrl@...ck.org Subject: Re: Extensible hashing and RCU On Tue, Feb 20, 2007 at 12:25:23PM +0300, Evgeniy Polyakov (johnpol@....mipt.ru) wrote: > And there is _no_ O(1) - O(1) is just a hash entry selection, then you > need to add the whole chain path, which can be long enough. > For example for the length 9 you have 1000 entries - it is exactly size > of the tree - sum of all entries upto and including 2^9. > One third of the table is accessible within 17 lookups (hash chain > length is 1), but given into account size of the entry - let's say it > is equal to > 32+32+32 - size of the key > 32+32+32 - size of the left/right/parent pointer > so 192 bytes per entry - given into acount that 1/4 of the 1-2 MB cache is I just realized that it is in _BITS_, not in bytes, so typical trie/tree entry is about 24 bytes - less than one cache line! -- Evgeniy Polyakov - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists