Messages in this thread | | | Date | Sat, 22 Jan 2005 20:29:30 -0800 | From | Matt Mackall <> | Subject | Re: [patch 1/13] Qsort |
| |
On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote: > Felipe Alfaro Solana <lkml@mac.com> writes: > > > > AFAIK, XOR is quite expensive on IA32 when compared to simple MOV > > operatings. Also, since the original patch uses 3 MOVs to perform the > > swapping, and your version uses 3 XOR operations, I don't see any > > gains. > > Both are one cycle latency for register<->register on all x86 cores > I've looked at. What makes you think differently? > > -Andi (who thinks the glibc qsort is vast overkill for kernel purposes > where there are only small data sets and it would be better to use a > simpler one optimized for code size)
Mostly agreed. Except:
a) the glibc version is not actually all that optimized b) it's nice that it's not recursive 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
I'll probably whip up a simpler version tomorrow or Monday and do some size/space benchmarking. I've been meaning to contribute a qsort for doubly-linked lists I've got lying around as well.
-- 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 majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |