On Mon, Jan 24, 2005 at 11:21:29AM +1100, Nathan Scott wrote: > On Sat, Jan 22, 2005 at 08:29:30PM -0800, Matt Mackall wrote: > > On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote: > > > > c) the three-way median selection does help avoid worst-case O(n^2) > > behavior, which might potentially be triggerable by users in places > > like XFS where this is used > > XFS's needs are simple - we're just sorting dirents within a > single directory block or smaller, and sorting EA lists/ACLs - > all of which are small arrays, so a qsort optimised for small > arrays suits XFS well.
Ok, I've worked up a much smaller, cleaner version that wins on lists of 10000 entries or less and is still within 5% at 1M entries (ie well past what any kernel code has any business doing). More after I've fiddled around a bit more with the benchmarks. > Take care not to put any arrays on the > stack though, else the CONFIG_4KSTACKS punters won't be happy. I'm afraid I'm one of those punters - 4k stacks were getting cleaned up and tested in my -tiny tree long before mainline. -- Mathematics is the supreme nostalgia of our time. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/