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
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 ac
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 wha
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.
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 c
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 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 GMB
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 i
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 t
> 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 tho
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).
> 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 almos
[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 g
-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 i
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 3
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 sma
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
"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 potent
> 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 gi
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
X
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 h
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.
>
> - st
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) + 1
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 alr
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
gain
> 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 XO
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 don'
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 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 req
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.
P
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 i
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 {
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.
Signed-off-by: Andreas Gruenbacher <[EMAIL PROTECTED]>
Acked-by: Olaf Kirch <[
47 matches
Mail list logo
