On Tue, 2005-01-25 at 20:33, Trond Myklebust wrote:
> ty den 25.01.2005 Klokka 19:12 (+0100) skreiv Andreas Gruenbacher:
>
> > Ah, I see now what you mean. The setxattr syscall only accepts
> > well-formed acls (that is, sorted plus a few other restrictions), and
> > user-space is expected to
ty den 25.01.2005 Klokka 19:12 (+0100) skreiv Andreas Gruenbacher:
> Ah, I see now what you mean. The setxattr syscall only accepts
> well-formed acls (that is, sorted plus a few other restrictions), and
> user-space is expected to take care of that. In turn, getxattr returns
> only well-formed
On Tue, 2005-01-25 at 18:37, Trond Myklebust wrote:
> ty den 25.01.2005 Klokka 18:16 (+0100) skreiv Andreas Gruenbacher:
>
> > > Whatever Sun chooses to do or not do changes nothing to the question of
> > > why our client would want to do a quicksort in the kernel.
> >
> > Well, it determines
ty den 25.01.2005 Klokka 18:16 (+0100) skreiv Andreas Gruenbacher:
> > Whatever Sun chooses to do or not do changes nothing to the question of
> > why our client would want to do a quicksort in the kernel.
>
> Well, it determines what we must accept, both on the server side and the
> client
On Tue, 2005-01-25 at 18:03, Trond Myklebust wrote:
> ty den 25.01.2005 Klokka 17:53 (+0100) skreiv Andreas Gruenbacher:
> > On Tue, 2005-01-25 at 17:52, Trond Myklebust wrote:
> > > So here's an iconoclastic question or two:
> > >
> > > Why can't clients sort the list in userland, before they
ty den 25.01.2005 Klokka 17:53 (+0100) skreiv Andreas Gruenbacher:
> On Tue, 2005-01-25 at 17:52, Trond Myklebust wrote:
> > So here's an iconoclastic question or two:
> >
> > Why can't clients sort the list in userland, before they call down to
> > the kernel?
>
> Tell that to Sun
On Tue, 2005-01-25 at 17:52, Trond Myklebust wrote:
> So here's an iconoclastic question or two:
>
> Why can't clients sort the list in userland, before they call down to
> the kernel?
Tell that to Sun Microsystems.
Regards,
--
Andreas Gruenbacher <[EMAIL PROTECTED]>
SUSE Labs, SUSE LINUX
ty den 25.01.2005 Klokka 13:05 (+0100) skreiv Olaf Kirch:
> On Tue, Jan 25, 2005 at 01:00:23PM +0100, Andi Kleen wrote:
> > group initialization is not time critical, it typically only happens
> > at login. Also it's doubleful you'll even be able to measure the
> > difference.
>
> nfsd updates
On Tue, Jan 25, 2005 at 01:00:23PM +0100, Andi Kleen wrote:
> group initialization is not time critical, it typically only happens
> at login. Also it's doubleful you'll even be able to measure the difference.
nfsd updates its group list for every request it processes, so you don't want
to make
> It would slow down the groups case (unless we leave the specialized version
> in). Gcc doesn't inline a cmp function pointer, and a C preprocessor
> templatized version would be really ugly. A variant with of this routine with
> qsort like interface should be good enough for nfsacl and xfs
On Tuesday 25 January 2005 07:51, Andi Kleen wrote:
> > FWIW, we already have a Shell sort for the ngroups stuff in
> > kernel/sys.c:groups_sort() that could be made generic.
>
> Sounds like a good plan. Any takers?
It would slow down the groups case (unless we leave the specialized version
in).
On Tuesday 25 January 2005 07:51, Andi Kleen wrote:
FWIW, we already have a Shell sort for the ngroups stuff in
kernel/sys.c:groups_sort() that could be made generic.
Sounds like a good plan. Any takers?
It would slow down the groups case (unless we leave the specialized version
in). Gcc
It would slow down the groups case (unless we leave the specialized version
in). Gcc doesn't inline a cmp function pointer, and a C preprocessor
templatized version would be really ugly. A variant with of this routine with
qsort like interface should be good enough for nfsacl and xfs
On Tue, Jan 25, 2005 at 01:00:23PM +0100, Andi Kleen wrote:
group initialization is not time critical, it typically only happens
at login. Also it's doubleful you'll even be able to measure the difference.
nfsd updates its group list for every request it processes, so you don't want
to make
ty den 25.01.2005 Klokka 13:05 (+0100) skreiv Olaf Kirch:
On Tue, Jan 25, 2005 at 01:00:23PM +0100, Andi Kleen wrote:
group initialization is not time critical, it typically only happens
at login. Also it's doubleful you'll even be able to measure the
difference.
nfsd updates its group
On Tue, 2005-01-25 at 17:52, Trond Myklebust wrote:
So here's an iconoclastic question or two:
Why can't clients sort the list in userland, before they call down to
the kernel?
Tell that to Sun Microsystems.
Regards,
--
Andreas Gruenbacher [EMAIL PROTECTED]
SUSE Labs, SUSE LINUX GMBH
-
ty den 25.01.2005 Klokka 17:53 (+0100) skreiv Andreas Gruenbacher:
On Tue, 2005-01-25 at 17:52, Trond Myklebust wrote:
So here's an iconoclastic question or two:
Why can't clients sort the list in userland, before they call down to
the kernel?
Tell that to Sun Microsystems.
On Tue, 2005-01-25 at 18:03, Trond Myklebust wrote:
ty den 25.01.2005 Klokka 17:53 (+0100) skreiv Andreas Gruenbacher:
On Tue, 2005-01-25 at 17:52, Trond Myklebust wrote:
So here's an iconoclastic question or two:
Why can't clients sort the list in userland, before they call down to
ty den 25.01.2005 Klokka 18:16 (+0100) skreiv Andreas Gruenbacher:
Whatever Sun chooses to do or not do changes nothing to the question of
why our client would want to do a quicksort in the kernel.
Well, it determines what we must accept, both on the server side and the
client side.
I
On Tue, 2005-01-25 at 18:37, Trond Myklebust wrote:
ty den 25.01.2005 Klokka 18:16 (+0100) skreiv Andreas Gruenbacher:
Whatever Sun chooses to do or not do changes nothing to the question of
why our client would want to do a quicksort in the kernel.
Well, it determines what we must
ty den 25.01.2005 Klokka 19:12 (+0100) skreiv Andreas Gruenbacher:
Ah, I see now what you mean. The setxattr syscall only accepts
well-formed acls (that is, sorted plus a few other restrictions), and
user-space is expected to take care of that. In turn, getxattr returns
only well-formed acls.
On Tue, 2005-01-25 at 20:33, Trond Myklebust wrote:
ty den 25.01.2005 Klokka 19:12 (+0100) skreiv Andreas Gruenbacher:
Ah, I see now what you mean. The setxattr syscall only accepts
well-formed acls (that is, sorted plus a few other restrictions), and
user-space is expected to take care
> FWIW, we already have a Shell sort for the ngroups stuff in
> kernel/sys.c:groups_sort() that could be made generic.
Sounds like a good plan. Any takers?
-Andi
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo
On Mon, 2005-01-24 at 21:43 -0300, Horst von Brand wrote:
> AFAICS, this is just a badly implemented Shellsort (the 10/13 increment
> sequence starting with the number of elements is probably not very good,
> besides swapping stuff is inefficient (just juggling like Shellsort does
> gives you
[EMAIL PROTECTED] (H. Peter Anvin) said:
[...]
> In klibc, I use combsort:
>
> /*
> * qsort.c
> *
> * This is actually combsort. It's an O(n log n) algorithm with
> * simplicity/small code size being its main virtue.
> */
>
> #include
> #include
>
> static inline size_t newgap(size_t
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
Andi Kleen wrote:
>>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
On Mon, Jan 24, 2005 at 01:02:44AM -0300, Horst von Brand wrote:
> Matt Mackall <[EMAIL PROTECTED]> said:
> > On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:
>
> [...]
>
> > > -Andi (who thinks the glibc qsort is vast overkill for kernel purposes
> > > where there are only small data
On Mon, 24 Jan 2005, Matt Mackall wrote:
> On Sun, Jan 23, 2005 at 05:58:00AM +0100, Felipe Alfaro Solana wrote:
> > On 23 Jan 2005, at 03:39, Andi Kleen wrote:
> >
> > >Felipe Alfaro Solana <[EMAIL PROTECTED]> writes:
> > >>
> > >>AFAIK, XOR is quite expensive on IA32 when compared to simple MOV
On Sun, Jan 23, 2005 at 05:58:00AM +0100, Felipe Alfaro Solana wrote:
> On 23 Jan 2005, at 03:39, Andi Kleen wrote:
>
> >Felipe Alfaro Solana <[EMAIL PROTECTED]> writes:
> >>
> >>AFAIK, XOR is quite expensive on IA32 when compared to simple MOV
> >>operatings. Also, since the original patch uses
Followup to: <[EMAIL PROTECTED]>
By author:Jesper Juhl <[EMAIL PROTECTED]>
In newsgroup: linux.dev.kernel
>
> On Sun, 23 Jan 2005, Andi Kleen wrote:
>
> > > 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
On Sul, 2005-01-23 at 05:05, Jesper Juhl wrote:
> On Sun, 23 Jan 2005, Andi Kleen wrote:
> Even with large data sets that are mostly unsorted shell sorts performance
> is close to qsort, and there's an optimization that gives it O(n^(3/2))
> runtime (IIRC), and another nice property is that it's
On Sul, 2005-01-23 at 05:05, Jesper Juhl wrote:
On Sun, 23 Jan 2005, Andi Kleen wrote:
Even with large data sets that are mostly unsorted shell sorts performance
is close to qsort, and there's an optimization that gives it O(n^(3/2))
runtime (IIRC), and another nice property is that it's
Followup to: [EMAIL PROTECTED]
By author:Jesper Juhl [EMAIL PROTECTED]
In newsgroup: linux.dev.kernel
On Sun, 23 Jan 2005, Andi Kleen wrote:
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
On Sun, Jan 23, 2005 at 05:58:00AM +0100, Felipe Alfaro Solana wrote:
On 23 Jan 2005, at 03:39, Andi Kleen wrote:
Felipe Alfaro Solana [EMAIL PROTECTED] writes:
AFAIK, XOR is quite expensive on IA32 when compared to simple MOV
operatings. Also, since the original patch uses 3 MOVs to
On Mon, 24 Jan 2005, Matt Mackall wrote:
On Sun, Jan 23, 2005 at 05:58:00AM +0100, Felipe Alfaro Solana wrote:
On 23 Jan 2005, at 03:39, Andi Kleen wrote:
Felipe Alfaro Solana [EMAIL PROTECTED] writes:
AFAIK, XOR is quite expensive on IA32 when compared to simple MOV
operatings.
On Mon, Jan 24, 2005 at 01:02:44AM -0300, Horst von Brand wrote:
Matt Mackall [EMAIL PROTECTED] said:
On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:
[...]
-Andi (who thinks the glibc qsort is vast overkill for kernel purposes
where there are only small data sets and it
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
Andi Kleen wrote:
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
[EMAIL PROTECTED] (H. Peter Anvin) said:
[...]
In klibc, I use combsort:
/*
* qsort.c
*
* This is actually combsort. It's an O(n log n) algorithm with
* simplicity/small code size being its main virtue.
*/
#include stddef.h
#include string.h
static inline size_t
On Mon, 2005-01-24 at 21:43 -0300, Horst von Brand wrote:
AFAICS, this is just a badly implemented Shellsort (the 10/13 increment
sequence starting with the number of elements is probably not very good,
besides swapping stuff is inefficient (just juggling like Shellsort does
gives you almost a
FWIW, we already have a Shell sort for the ngroups stuff in
kernel/sys.c:groups_sort() that could be made generic.
Sounds like a good plan. Any takers?
-Andi
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo
"Rafael J. Wysocki" <[EMAIL PROTECTED]> said:
[...]
> To be precise, one needs ~(log N) of stack space for qsort, and frankly, one
> should use something like the shell (or should I say Shell?)
Shell. It is named for a person.
> sort
Matt Mackall <[EMAIL PROTECTED]> said:
> On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:
[...]
> > -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)
Andreas Gruenbacher <[EMAIL PROTECTED]> said:
> Signed-off-by: Andreas Gruenbacher <[EMAIL PROTECTED]>
> Acked-by: Olaf Kirch <[EMAIL PROTECTED]>
[...]
> +/* Order size using quicksort. This implementation incorporates
> + four optimizations discussed in Sedgewick:
> +
> + 1. Non-recursive,
Here are semi-templated versions of quicksort and heapsort, just for
completeness. The quicksort uses the median of three.
Chuck
void quicksort0( *pl, *pr)
{
vp, SWAP_temp;
*stack[100], **sptr = stack, *pm, *pi, *pj, *pt;
for(;;) {
while ((pr
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
> On Sunday, January 23, 2005, Rafael J. Wysocki wrote:
> > On Sunday, 23 of January 2005 06:05, Jesper Juhl wrote:
> > > On Sun, 23 Jan 2005, Andi Kleen wrote:
> > Even with large data sets that are mostly unsorted shell sorts performance
> > is close to qsort, and there's an optimization that
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
On Sat, Jan 22, 2005 at 01:00:24PM -0800, vlobanov wrote:
> #define SWAP(a, b, size) \
> do { \
> register size_t __size = (size);\
> register char * __a = (a), * __b = (b); \
> do {
On Sun, Jan 23, 2005 at 01:22:13PM +0100, Andreas Gruenbacher wrote:
> On Sunday 23 January 2005 06:32, Matt Mackall wrote:
> > Yes, indeed. Though I think even here, we'd prefer to use kmalloc
> > because gcc generates suboptimal code for variable-sized stack vars.
>
> That's ridiculous. kmalloc
On Sunday 23 January 2005 06:32, Matt Mackall wrote:
> Yes, indeed. Though I think even here, we'd prefer to use kmalloc
> because gcc generates suboptimal code for variable-sized stack vars.
That's ridiculous. kmalloc isn't even close to whatever suboptimal code gcc
might produce here. Also I'm
On Sunday, 23 of January 2005 06:05, Jesper Juhl wrote:
> On Sun, 23 Jan 2005, Andi Kleen wrote:
>
> > > 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
On Sunday, 23 of January 2005 06:05, Jesper Juhl wrote:
On Sun, 23 Jan 2005, Andi Kleen wrote:
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
On Sunday 23 January 2005 06:32, Matt Mackall wrote:
Yes, indeed. Though I think even here, we'd prefer to use kmalloc
because gcc generates suboptimal code for variable-sized stack vars.
That's ridiculous. kmalloc isn't even close to whatever suboptimal code gcc
might produce here. Also I'm
On Sun, Jan 23, 2005 at 01:22:13PM +0100, Andreas Gruenbacher wrote:
On Sunday 23 January 2005 06:32, Matt Mackall wrote:
Yes, indeed. Though I think even here, we'd prefer to use kmalloc
because gcc generates suboptimal code for variable-sized stack vars.
That's ridiculous. kmalloc isn't
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
On Sunday, January 23, 2005, Rafael J. Wysocki wrote:
On Sunday, 23 of January 2005 06:05, Jesper Juhl wrote:
On Sun, 23 Jan 2005, Andi Kleen wrote:
Even with large data sets that are mostly unsorted shell sorts performance
is close to qsort, and there's an optimization that gives it
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
Here are semi-templated versions of quicksort and heapsort, just for
completeness. The quicksort uses the median of three.
Chuck
void quicksort0typename(typename *pl, typename *pr)
{
typename vp, SWAP_temp;
typename *stack[100], **sptr = stack, *pm, *pi, *pj, *pt;
Andreas Gruenbacher [EMAIL PROTECTED] said:
Signed-off-by: Andreas Gruenbacher [EMAIL PROTECTED]
Acked-by: Olaf Kirch [EMAIL PROTECTED]
[...]
+/* Order size using quicksort. This implementation incorporates
+ four optimizations discussed in Sedgewick:
+
+ 1. Non-recursive, using an
Matt Mackall [EMAIL PROTECTED] said:
On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:
[...]
-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
Rafael J. Wysocki [EMAIL PROTECTED] said:
[...]
To be precise, one needs ~(log N) of stack space for qsort, and frankly, one
should use something like the shell (or should I say Shell?)
Shell. It is named for a person.
sort for
Hi,
On Sun, Jan 23, 2005 at 03:03:32AM +0100, Felipe Alfaro Solana wrote:
> On 22 Jan 2005, at 22:00, vlobanov wrote:
> >#define SWAP(a, b, size) \
> >do { \
> > register size_t __size = (size);\
> > register char * __a =
On Sun, Jan 23, 2005 at 06:08:36AM +0100, Andreas Gruenbacher wrote:
> On Sunday 23 January 2005 00:28, Matt Mackall wrote:
> > So the stack is going to be either 256 or 1024 bytes. Seems like we
> > ought to kmalloc it.
>
> This will do. I didn't check if the +1 is strictly needed.
>
> -
On Sunday 23 January 2005 00:28, Matt Mackall wrote:
> So the stack is going to be either 256 or 1024 bytes. Seems like we
> ought to kmalloc it.
This will do. I didn't check if the +1 is strictly needed.
- stack_node stack[STACK_SIZE];
+ stack_node stack[fls(size) - fls(MAX_THRESH) +
On Sun, 23 Jan 2005, Andi Kleen wrote:
> > 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
On 23 Jan 2005, at 03:39, Andi Kleen wrote:
Felipe Alfaro Solana <[EMAIL PROTECTED]> 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
> 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
On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:
> Felipe Alfaro Solana <[EMAIL PROTECTED]> 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
On Sun, Jan 23, 2005 at 03:03:32AM +0100, Felipe Alfaro Solana wrote:
> On 22 Jan 2005, at 22:00, vlobanov wrote:
>
> >Hi,
> >
> >I was just reading over the patch, and had a quick question/comment
> >upon
> >the SWAP macro defined below. I think it's possible to do a tiny bit
> >better (better,
On Sun, 23 Jan 2005, Andi Kleen wrote:
> Felipe Alfaro Solana <[EMAIL PROTECTED]> 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
Felipe Alfaro Solana <[EMAIL PROTECTED]> 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
On 22 Jan 2005, at 22:00, vlobanov wrote:
Hi,
I was just reading over the patch, and had a quick question/comment
upon
the SWAP macro defined below. I think it's possible to do a tiny bit
better (better, of course, being subjective), as follows:
#define SWAP(a, b, size)\
On Sat, Jan 22, 2005 at 03:28:14PM -0800, Matt Mackall wrote:
> On Sat, Jan 22, 2005 at 09:34:01PM +0100, Andreas Gruenbacher wrote:
> > Add a quicksort from glibc as a kernel library function, and switch
> > xfs over to using it. The implementations are equivalent. The nfsacl
> > protocol also
On Sat, Jan 22, 2005 at 09:34:01PM +0100, Andreas Gruenbacher wrote:
> Add a quicksort from glibc as a kernel library function, and switch
> xfs over to using it. The implementations are equivalent. The nfsacl
> protocol also requires a sort function, so it makes more sense in
> the common code.
On Sat, 2005-01-22 at 23:06, Arjan van de Ven wrote:
> since you took the glibc one.. the glibc authors have repeatedly asked
> if glibc code that goes into the kernel will be export_symbol_gpl only
> due to their view of the gpl and lgpl
Sure, no big deal. We could equally well take the xfs one
Hi,
I was just reading over the patch, and had a quick question/comment upon
the SWAP macro defined below. I think it's possible to do a tiny bit
better (better, of course, being subjective), as follows:
#define SWAP(a, b, size)\
do {
Hi,
I was just reading over the patch, and had a quick question/comment upon
the SWAP macro defined below. I think it's possible to do a tiny bit
better (better, of course, being subjective), as follows:
#define SWAP(a, b, size)\
do {
On Sat, 2005-01-22 at 23:06, Arjan van de Ven wrote:
since you took the glibc one.. the glibc authors have repeatedly asked
if glibc code that goes into the kernel will be export_symbol_gpl only
due to their view of the gpl and lgpl
Sure, no big deal. We could equally well take the xfs one
On Sat, Jan 22, 2005 at 09:34:01PM +0100, Andreas Gruenbacher wrote:
Add a quicksort from glibc as a kernel library function, and switch
xfs over to using it. The implementations are equivalent. The nfsacl
protocol also requires a sort function, so it makes more sense in
the common code.
On Sat, Jan 22, 2005 at 03:28:14PM -0800, Matt Mackall wrote:
On Sat, Jan 22, 2005 at 09:34:01PM +0100, Andreas Gruenbacher wrote:
Add a quicksort from glibc as a kernel library function, and switch
xfs over to using it. The implementations are equivalent. The nfsacl
protocol also requires
On 22 Jan 2005, at 22:00, vlobanov wrote:
Hi,
I was just reading over the patch, and had a quick question/comment
upon
the SWAP macro defined below. I think it's possible to do a tiny bit
better (better, of course, being subjective), as follows:
#define SWAP(a, b, size)\
Felipe Alfaro Solana [EMAIL PROTECTED] 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
On Sun, 23 Jan 2005, Andi Kleen wrote:
Felipe Alfaro Solana [EMAIL PROTECTED] 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
On Sun, Jan 23, 2005 at 03:03:32AM +0100, Felipe Alfaro Solana wrote:
On 22 Jan 2005, at 22:00, vlobanov wrote:
Hi,
I was just reading over the patch, and had a quick question/comment
upon
the SWAP macro defined below. I think it's possible to do a tiny bit
better (better, of course,
On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote:
Felipe Alfaro Solana [EMAIL PROTECTED] 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
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
On 23 Jan 2005, at 03:39, Andi Kleen wrote:
Felipe Alfaro Solana [EMAIL PROTECTED] 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
On Sun, 23 Jan 2005, Andi Kleen wrote:
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
On Sunday 23 January 2005 00:28, Matt Mackall wrote:
So the stack is going to be either 256 or 1024 bytes. Seems like we
ought to kmalloc it.
This will do. I didn't check if the +1 is strictly needed.
- stack_node stack[STACK_SIZE];
+ stack_node stack[fls(size) - fls(MAX_THRESH) +
On Sun, Jan 23, 2005 at 06:08:36AM +0100, Andreas Gruenbacher wrote:
On Sunday 23 January 2005 00:28, Matt Mackall wrote:
So the stack is going to be either 256 or 1024 bytes. Seems like we
ought to kmalloc it.
This will do. I didn't check if the +1 is strictly needed.
- stack_node
Hi,
On Sun, Jan 23, 2005 at 03:03:32AM +0100, Felipe Alfaro Solana wrote:
On 22 Jan 2005, at 22:00, vlobanov wrote:
#define SWAP(a, b, size) \
do { \
register size_t __size = (size);\
register char * __a = (a), *
91 matches
Mail list logo
