On Fri, 2015-10-23 at 15:20 +0200, casper....@oracle.com wrote: > > >Yet another POSIX deficiency. > > > >When a server deals with 10,000,000+ socks, we absolutely do not care of > >this requirement. > > > >O(log(n)) is still crazy if it involves O(log(n)) cache misses. > > You miss the fire point of the algorithm; you *always* find an available > file descriptor in O(log(N)) (where N is the size of the table). > > Does your algorithm guarantee that?
Its a simple bit map. Each cache line contains 64*8 = 512 bits. Lookup is actually quite fast thanks to hardware prefetches. Main problem we had until recently was that we used to acquire fd table lock 3 times per accept()/close() pair This patch took care of the issue : http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=8a81252b774b53e628a8a0fe18e2b8fc236d92cc Then, adding a O_RANDOMFD flag (or O_DO_NOT_REQUIRE_POSIX_FD_RULES) is helping a lot, as it allows us to pick a random starting point during the bitmap search. In practice, finding a slot in fd array is O(1) : one cache line miss exactly. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
