Re: Port of Niels Provos's file descriptor allocation code
On Wed, Dec 03, 2003 at 11:54:45PM -0800, David Schultz wrote: On Thu, Nov 27, 2003, Tim Robbins wrote: I've ported Niels Provos's file descriptor allocation code to FreeBSD in case anyone wants to try it out run some benchmarks. If the performance boost turns out to be worth the added complexity, I might clean it up a bit and commit it. I've used a similar data structure for a special-purpose allocator before, and it had extremely low allocation time overhead--- basically a few memory references for every level of the tree in the common case. Unless for some strange reason it pessimizes processes with a small number of file descriptors significantly, it would be really great to have this in the tree! It doesn't seem to make a noticeable impact on execution time for processes with small numbers of descriptors. It's probably swamped by the overhead of mode switches, locking, and filesystem operations. What makes uneasy is the amount of extra memory it consumes when processes have a small number of descriptors: (32**2)/8 = 128 bytes (when int is 32 bits), or (64**2)/8 = 512 bytes (when int is 64 bits). I've been thinking of switching to a flat bitmap for small fd tables, possibly just using a single int, or falling back to the old way of scanning fd_ofiles directly. Once I decide what to do about that and find someone to test my latest patch on a 64-bit machine, I'll commit it. Tim ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Port of Niels Provos's file descriptor allocation code
On Thu, Nov 27, 2003, Tim Robbins wrote: I've ported Niels Provos's file descriptor allocation code to FreeBSD in case anyone wants to try it out run some benchmarks. If the performance boost turns out to be worth the added complexity, I might clean it up a bit and commit it. I've used a similar data structure for a special-purpose allocator before, and it had extremely low allocation time overhead--- basically a few memory references for every level of the tree in the common case. Unless for some strange reason it pessimizes processes with a small number of file descriptors significantly, it would be really great to have this in the tree! ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Port of Niels Provos's file descriptor allocation code
At 1:32 AM +0100 2003/11/29, Dag-Erling Smørgrav wrote: What exactly would be the point? If this is the OpenBSD fdalloc code, recent widely-publicized benchmarks have shown it to be inferior to ours. Perhaps you should concentrate on improving vm_map_find() and vm_map_findspace() performance instead? Perhaps the implementation on OpenBSD may be worse than ours, but it may add features that help improve our performance further. Certainly, both issues should be checked as broadly as possible. -- Brad Knowles, [EMAIL PROTECTED] They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. -Benjamin Franklin, Historical Review of Pennsylvania. GCS/IT d+(-) s:+(++): a C++(+++)$ UMBSHI$ P+++ L+ !E-(---) W+++(--) N+ !w--- O- M++ V PS++(+++) PE- Y+(++) PGP+++ t+(+++) 5++(+++) X++(+++) R+(+++) tv+(+++) b+() DI+() D+(++) G+() e++ h--- r---(+++)* z(+++) ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Port of Niels Provos's file descriptor allocation code
On Sat, Nov 29, 2003 at 01:32:01AM +0100, Dag-Erling Sm?rgrav wrote: Tim Robbins [EMAIL PROTECTED] writes: I've ported Niels Provos's file descriptor allocation code to FreeBSD in case anyone wants to try it out run some benchmarks. If the performance boost turns out to be worth the added complexity, I might clean it up a bit and commit it. What exactly would be the point? If this is the OpenBSD fdalloc code, recent widely-publicized benchmarks have shown it to be inferior to ours. Perhaps you should concentrate on improving vm_map_find() and vm_map_findspace() performance instead? It's also the NetBSD fdalloc code. They started with code similar to ours, in that it did a linear search of the file descriptor array to find an empty slot and used hints to speed up some common allocation patterns, then recently switched over to using the multi-level bitmap allocator. I can't think of any reason why we wouldn't see improvements similar to what they saw: http://www.citi.umich.edu/u/provos/benchmark/netbsd-fdalloc.jpg ... but I'm still working on benchmarking FreeBSD with without the new allocator; I just posted the patch so that other people could experiment with it if they were interested. I don't plan on committing it until I have good evidence that it's an improvement over the current code. Tim ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Port of Niels Provos's file descriptor allocation code
Tim Robbins [EMAIL PROTECTED] writes: It's also the NetBSD fdalloc code. They started with code similar to ours, in that it did a linear search of the file descriptor array to find an empty slot and used hints to speed up some common allocation patterns, then recently switched over to using the multi-level bitmap allocator. I can't think of any reason why we wouldn't see improvements similar to what they saw: http://www.citi.umich.edu/u/provos/benchmark/netbsd-fdalloc.jpg Having looked at the code, I believe that the graph is the result of an improperly designed benchmark. FreeBSD's performance *with a properly designed benchmark* should be similar to the red line (it's not as bad as it looks; the sharp rise caused by cache trashing occurs around 30k fds which is a pretty respectable number). The same benchmark would show a similar but less steep curve for the multi- level bitmap (which is just a fancy way of saying micro-optimized trie). A proper trie would result in a logarithmic curve. DES -- Dag-Erling Smørgrav - [EMAIL PROTECTED] ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Port of Niels Provos's file descriptor allocation code
I've run some benchmarks of my own with and without the patch, and it's a definite improvement... I expected it to go linear for large number of open file descriptors, and it does, but the slope is much less steep than I expected, which explains why it looked like O(1). I have two objections to the patch, however: the first is the use of NDENTRYSHIFT to obfuscate multiplications and divisions by NDENTRIES (which is a constant, so the compiler will optimize it anyway). The second is the use of uint32_t instead of unsigned long which should be more efficient on 64-bit machines (NDENTRIES would have to be made dependent on sizeof(unsigned long)) and it scares me a bit that the Banga Mogul paper has been floating around for five years and nobody took any notice... DES -- Dag-Erling Smørgrav - [EMAIL PROTECTED] ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-current To unsubscribe, send any mail to [EMAIL PROTECTED]
