On Tuesday 06 March 2007 14:42, Robert Olsson wrote: > Eric Dumazet writes: > > Well, maybe... but after looking robert's trash, I discovered its model > > is essentially a big (2^18 slots) root node (our hash table), and very > > few order:1,2,3 nodes. > > It's getting "hashlike" yes. I guess all effective algorithms today is > doing some sort of "index" lookup and for large number of entries we cannot > expect to find the next node in the same cache line so the "tree depth" > becomes a crucial performance factor. IMO nothing can beat a prefect > distributed and perfect sized hash. The trash work is an effort to get > close with dynamic data structure.
Indeed. It would be nice to see how it performs with say 2^20 elements... Because with your data, I wonder if the extra complexity of the trash is worth it (since most lookups are going to only hit the hash and give the answer without intermediate nodes) - 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
