Re: [patch 1/13] Qsort

[Jesper Juhl]

On Sun, 23 Jan 2005, Andi Kleen wrote:

> Felipe Alfaro Solana <lkml@xxxxxxx> 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)
> 
How about a shell sort?  if the data is mostly sorted shell sort beats 
qsort lots of times, and since the data sets are often small in-kernel, 
shell sorts O(n^2) behaviour won't harm it too much, shell sort is also 
faster if the data is already completely sorted. Shell sort is certainly 
not the simplest algorithm around, but I think (without having done any 
tests) that it would probably do pretty well for in-kernel use... Then 
again, I've known to be wrong :)


-- 
Jesper Juhl

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/