Re: [patch 1/13] Qsort
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 of that. In turn, getxattr returns > > only well-formed acls. We could lift that guarantee specifically for > > nfs, but I don't think it would be a good idea. > > Note that if you really want to add a qsort to the kernel you might as > well drop the setxattr sorting requirement too. If the kernel can qsort > for getxattr, then might as well do it for the case of setxattr too. There is no need to sort anything in the kernel for acls except for the NFSACL case, so that's where we need it, and nowhere else. What would be the point in making setxattr accept unsorted acls? It's just not necessary; userspace can do it just as well. > > Entry order in POSIX acls doesn't convey a meaning by the way. > > Precisely. Are there really any existing programs out there that are > using the raw xattr output and making assumptions about entry order? I don't know. Anyway, it's a nice feature to have a unique canonical form. > > The server must have sorted lists. > > So, I realize that the on-disk format is already defined, but looking at > routines like posix_acl_permission(), it looks like the only order the > kernel (at least) actually cares about is that of the "e_tag" field. > Unless I missed something, nothing there cares about the order of the > "e_id" fields. Correct. But posix_acl_valid() does care about the i_id order as well. > Given that you only have 6 possible values there, it seems a shame in > hindsight that we didn't choose to just use a 6 bucket hashtable (the > value of e_id being the hash value), and leave the order of the e_id > fields undefined. 8-( Checking for duplicate e_id fields would become expensive. I really don't see any benefit. Cheers, -- Andreas Gruenbacher <[EMAIL PROTECTED]> SUSE Labs, SUSE LINUX GMBH - 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/
Re: [patch 1/13] Qsort
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. We could lift that guarantee specifically for > nfs, but I don't think it would be a good idea. Note that if you really want to add a qsort to the kernel you might as well drop the setxattr sorting requirement too. If the kernel can qsort for getxattr, then might as well do it for the case of setxattr too. > Entry order in POSIX acls doesn't convey a meaning by the way. Precisely. Are there really any existing programs out there that are using the raw xattr output and making assumptions about entry order? > The server must have sorted lists. So, I realize that the on-disk format is already defined, but looking at routines like posix_acl_permission(), it looks like the only order the kernel (at least) actually cares about is that of the "e_tag" field. Unless I missed something, nothing there cares about the order of the "e_id" fields. Given that you only have 6 possible values there, it seems a shame in hindsight that we didn't choose to just use a 6 bucket hashtable (the value of e_id being the hash value), and leave the order of the e_id fields undefined. 8-( Cheers, Trond -- Trond Myklebust <[EMAIL PROTECTED]> - 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/
Re: [patch 1/13] Qsort
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 accept, both on the server side and the > > client side. > > I can see why you might want it on the server side, but I repeat: why > does the client need to do this in the kernel? The client code should > not be overriding the server when it comes to what is acceptable or not > acceptable. That's just wrong... 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. We could lift that guarantee specifically for nfs, but I don't think it would be a good idea. Entry order in POSIX acls doesn't convey a meaning by the way, and the nfs client never rejects what the server sends. > I can also see that if the server _must_ have a sorted list, then doing > a sort on the client is a good thing since it will cut down on the work > that said server will need to do, and so it will scale better with the > number of clients (though note that, conversely, this server will scale > poorly with the Sun clients or others if they do not sort the lists). The server must have sorted lists. Linux clients send well-formed acls except when they fake up a mask entry; they insert the mask entry at the end instead of in the right position (this is the three-entry acl problem I described in [patch 0/13]). We could insert the mask in the right position, but the protocol doesn't require it. We must sort on the server anyway, and the server can as easily swap the two entries. > I'm asking 'cos if the client doesn't need this code, then it seems to > me you can move helper routines like the quicksort and posix checking > routines into the nfsd module rather than having to keeping it in the > VFS (unless you foresee that other modules will want to use the same > routines???). That would cause getxattr to return an "invalid" result. libacl doesn't care, but other users might exist that rely on the current format. In addition, comparing acls becomes non-trivial: currently xattr values are equal iff acls are equal. Cheers, -- Andreas Gruenbacher <[EMAIL PROTECTED]> SUSE Labs, SUSE LINUX GMBH - 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/
Re: [patch 1/13] Qsort
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 can see why you might want it on the server side, but I repeat: why does the client need to do this in the kernel? The client code should not be overriding the server when it comes to what is acceptable or not acceptable. That's just wrong... I can also see that if the server _must_ have a sorted list, then doing a sort on the client is a good thing since it will cut down on the work that said server will need to do, and so it will scale better with the number of clients (though note that, conversely, this server will scale poorly with the Sun clients or others if they do not sort the lists). I'm asking 'cos if the client doesn't need this code, then it seems to me you can move helper routines like the quicksort and posix checking routines into the nfsd module rather than having to keeping it in the VFS (unless you foresee that other modules will want to use the same routines???). Cheers, Trond -- Trond Myklebust <[EMAIL PROTECTED]> - 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/
Re: [patch 1/13] Qsort
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 > > > the kernel? > > > > Tell that to Sun Microsystems. > > 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. Cheers, -- Andreas Gruenbacher <[EMAIL PROTECTED]> SUSE Labs, SUSE LINUX GMBH - 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/
Re: [patch 1/13] Qsort
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. 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. Cheers, Trond -- Trond Myklebust <[EMAIL PROTECTED]> - 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/
Re: [patch 1/13] Qsort
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 - 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/
Re: [patch 1/13] Qsort
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 list for every request it processes, so you don't want > to make that too slow. So here's an iconoclastic question or two: Why can't clients sort the list in userland, before they call down to the kernel? If clients are sorting their lists, why would we need to sort the same list on the server side. Detecting out-of-order list entries is much less of a hassle than actually sorting, so if the protocol calls for sorted elements, you can return an EINVAL or something in the case where some client sends an unsorted list. Cheers, Trond -- Trond Myklebust <[EMAIL PROTECTED]> - 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/
Re: [patch 1/13] Qsort
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 that too slow. Olaf -- Olaf Kirch | Things that make Monday morning interesting, #2: [EMAIL PROTECTED] |"We have 8,000 NFS mount points, why do we keep ---+ running out of privileged ports?" - 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/
Re: [patch 1/13] Qsort
> 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 though. 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. -Andi - 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/
Re: [patch 1/13] Qsort
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 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 though. Nevertheless, xfs and nfsacl have very similar requirements: nfsacl: at most 1024 elements; 8-byte elements (16 on 64-bit archs) xfs (from Nathan): at most 1024 elements (with 64K blocksize); 8-byte or larger elements Cheers. -- Andreas Gruenbacher <[EMAIL PROTECTED]> SUSE Labs, SUSE LINUX PRODUCTS GMBH - 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/
Re: [patch 1/13] Qsort
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 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 though. Nevertheless, xfs and nfsacl have very similar requirements: nfsacl: at most 1024 elements; 8-byte elements (16 on 64-bit archs) xfs (from Nathan): at most 1024 elements (with 64K blocksize); 8-byte or larger elements Cheers. -- Andreas Gruenbacher [EMAIL PROTECTED] SUSE Labs, SUSE LINUX PRODUCTS GMBH - 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/
Re: [patch 1/13] Qsort
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 though. 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. -Andi - 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/
Re: [patch 1/13] Qsort
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 that too slow. Olaf -- Olaf Kirch | Things that make Monday morning interesting, #2: [EMAIL PROTECTED] |We have 8,000 NFS mount points, why do we keep ---+ running out of privileged ports? - 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/
Re: [patch 1/13] Qsort
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 list for every request it processes, so you don't want to make that too slow. So here's an iconoclastic question or two: Why can't clients sort the list in userland, before they call down to the kernel? If clients are sorting their lists, why would we need to sort the same list on the server side. Detecting out-of-order list entries is much less of a hassle than actually sorting, so if the protocol calls for sorted elements, you can return an EINVAL or something in the case where some client sends an unsorted list. Cheers, Trond -- Trond Myklebust [EMAIL PROTECTED] - 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/
Re: [patch 1/13] Qsort
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 - 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/
Re: [patch 1/13] Qsort
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. 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. Cheers, Trond -- Trond Myklebust [EMAIL PROTECTED] - 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/
Re: [patch 1/13] Qsort
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 the kernel? Tell that to Sun Microsystems. 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. Cheers, -- Andreas Gruenbacher [EMAIL PROTECTED] SUSE Labs, SUSE LINUX GMBH - 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/
Re: [patch 1/13] Qsort
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 can see why you might want it on the server side, but I repeat: why does the client need to do this in the kernel? The client code should not be overriding the server when it comes to what is acceptable or not acceptable. That's just wrong... I can also see that if the server _must_ have a sorted list, then doing a sort on the client is a good thing since it will cut down on the work that said server will need to do, and so it will scale better with the number of clients (though note that, conversely, this server will scale poorly with the Sun clients or others if they do not sort the lists). I'm asking 'cos if the client doesn't need this code, then it seems to me you can move helper routines like the quicksort and posix checking routines into the nfsd module rather than having to keeping it in the VFS (unless you foresee that other modules will want to use the same routines???). Cheers, Trond -- Trond Myklebust [EMAIL PROTECTED] - 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/
Re: [patch 1/13] Qsort
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 accept, both on the server side and the client side. I can see why you might want it on the server side, but I repeat: why does the client need to do this in the kernel? The client code should not be overriding the server when it comes to what is acceptable or not acceptable. That's just wrong... 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. We could lift that guarantee specifically for nfs, but I don't think it would be a good idea. Entry order in POSIX acls doesn't convey a meaning by the way, and the nfs client never rejects what the server sends. I can also see that if the server _must_ have a sorted list, then doing a sort on the client is a good thing since it will cut down on the work that said server will need to do, and so it will scale better with the number of clients (though note that, conversely, this server will scale poorly with the Sun clients or others if they do not sort the lists). The server must have sorted lists. Linux clients send well-formed acls except when they fake up a mask entry; they insert the mask entry at the end instead of in the right position (this is the three-entry acl problem I described in [patch 0/13]). We could insert the mask in the right position, but the protocol doesn't require it. We must sort on the server anyway, and the server can as easily swap the two entries. I'm asking 'cos if the client doesn't need this code, then it seems to me you can move helper routines like the quicksort and posix checking routines into the nfsd module rather than having to keeping it in the VFS (unless you foresee that other modules will want to use the same routines???). That would cause getxattr to return an invalid result. libacl doesn't care, but other users might exist that rely on the current format. In addition, comparing acls becomes non-trivial: currently xattr values are equal iff acls are equal. Cheers, -- Andreas Gruenbacher [EMAIL PROTECTED] SUSE Labs, SUSE LINUX GMBH - 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/
Re: [patch 1/13] Qsort
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. We could lift that guarantee specifically for nfs, but I don't think it would be a good idea. Note that if you really want to add a qsort to the kernel you might as well drop the setxattr sorting requirement too. If the kernel can qsort for getxattr, then might as well do it for the case of setxattr too. Entry order in POSIX acls doesn't convey a meaning by the way. Precisely. Are there really any existing programs out there that are using the raw xattr output and making assumptions about entry order? The server must have sorted lists. So, I realize that the on-disk format is already defined, but looking at routines like posix_acl_permission(), it looks like the only order the kernel (at least) actually cares about is that of the e_tag field. Unless I missed something, nothing there cares about the order of the e_id fields. Given that you only have 6 possible values there, it seems a shame in hindsight that we didn't choose to just use a 6 bucket hashtable (the value of e_id being the hash value), and leave the order of the e_id fields undefined. 8-( Cheers, Trond -- Trond Myklebust [EMAIL PROTECTED] - 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/
Re: [patch 1/13] Qsort
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 of that. In turn, getxattr returns only well-formed acls. We could lift that guarantee specifically for nfs, but I don't think it would be a good idea. Note that if you really want to add a qsort to the kernel you might as well drop the setxattr sorting requirement too. If the kernel can qsort for getxattr, then might as well do it for the case of setxattr too. There is no need to sort anything in the kernel for acls except for the NFSACL case, so that's where we need it, and nowhere else. What would be the point in making setxattr accept unsorted acls? It's just not necessary; userspace can do it just as well. Entry order in POSIX acls doesn't convey a meaning by the way. Precisely. Are there really any existing programs out there that are using the raw xattr output and making assumptions about entry order? I don't know. Anyway, it's a nice feature to have a unique canonical form. The server must have sorted lists. So, I realize that the on-disk format is already defined, but looking at routines like posix_acl_permission(), it looks like the only order the kernel (at least) actually cares about is that of the e_tag field. Unless I missed something, nothing there cares about the order of the e_id fields. Correct. But posix_acl_valid() does care about the i_id order as well. Given that you only have 6 possible values there, it seems a shame in hindsight that we didn't choose to just use a 6 bucket hashtable (the value of e_id being the hash value), and leave the order of the e_id fields undefined. 8-( Checking for duplicate e_id fields would become expensive. I really don't see any benefit. Cheers, -- Andreas Gruenbacher [EMAIL PROTECTED] SUSE Labs, SUSE LINUX GMBH - 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/
Re: [patch 1/13] Qsort
> 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 info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch 1/13] Qsort
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 third less copies)). > > Have you found a proof for the O(n log n) claim? "Why a Comb Sort is NOT a Shell Sort A shell sort completely sorts the data for each gap size. A comb sort takes a more optimistic approach and doesn't require data be completely sorted at a gap size. The comb sort assumes that out-of-order data will be cleaned-up by smaller gap sizes as the sort proceeds. " Reference: http://world.std.com/~jdveale/combsort.htm Another good reference: http://yagni.com/combsort/index.php Personally, i've used it in the past because of it's small size. With C++ templates you can have a copy of the routine generated for a specific datatype, thus skipping the costly function call used for each compare. With some C macro magic, i presume something similar can be done, for time-critical applications. Best regards, Eric St-Laurent - 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/
Re: [patch 1/13] Qsort
[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 gap)
> {
> gap = (gap*10)/13;
> if ( gap == 9 || gap == 10 )
> gap = 11;
>
> if ( gap < 1 )
> gap = 1;
> return gap;
> }
>
> void qsort(void *base, size_t nmemb, size_t size,
>int (*compar)(const void *, const void *))
> {
> size_t gap = nmemb;
> size_t i, j;
> char *p1, *p2;
> int swapped;
>
> do {
> gap = newgap(gap);
> swapped = 0;
>
> for ( i = 0, p1 = base ; i < nmemb-gap ; i++, p1 += size ) {
> j = i+gap;
> if ( compar(p1, p2 = (char *)base+j*size) > 0 ) {
> memswap(p1, p2, size);
> swapped = 1;
> }
> }
> } while ( gap > 1 || swapped );
> }
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 third less copies)).
Have you found a proof for the O(n log n) claim?
I'd write as attached (careful, a local element on stack!)
/*
* shellsort.c: Shell sort
*
* Copyright (c) 2005, Horst H. von Brand <[EMAIL PROTECTED]>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
* * Neither the name of Horst H. von Brand nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
int i, j, h;
char tmp[size];
for(h = 1; h < nmemb; h = 3 * h + 1)
;
do {
h /= 3;
for(i = h; i < nmemb; i++) {
memcpy(tmp, base + i * size, size);
for(j = i - h; j >= 0 && compar(tmp, base + j * size); j -= h)
memcpy(base + (j + h) * size, base + j * size, size);
memcpy(base + (j + h) * size, tmp, size);
}
} while(h > 1);
}
--
Dr. Horst H. von Brand User #22616 counter.li.org
Departamento de Informatica Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria +56 32 654239
Casilla 110-V, Valparaiso, ChileFax: +56 32 797513
Re: [patch 1/13] Qsort
-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 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 :) > > > I like shell sort for small data sets too. And I agree it would be > appropiate for the kernel. > FWIW, we already have a Shell sort for the ngroups stuff in kernel/sys.c:groups_sort() that could be made generic. - -- Mike Waychison Sun Microsystems, Inc. 1 (650) 352-5299 voice 1 (416) 202-8336 voice ~~ NOTICE: The opinions expressed in this email are held by me, and may not represent the views of Sun Microsystems, Inc. ~~ -BEGIN PGP SIGNATURE- Version: GnuPG v1.2.5 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org iD8DBQFB9XDzdQs4kOxk3/MRAs2ZAJ4if1XRFAiWsgb1wvTInFLUVGHesgCfWxCJ Efyrr4PkG/KrqefAVAQjt+c= =/OPh -END PGP SIGNATURE- - 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/
Re: [patch 1/13] Qsort
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 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
>
> Shellsort is much simpler, and not much slower for small datasets. Plus no
> extra space for stacks.
>
> > 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.
>
> Qsort is OK as long as you have direct access to each element. In case of
> lists, it is better to just use mergesort.
Qsort does not need to do random access. I posted an efficient
doubly-linked list version here four years ago:
template
void list::qsort(iter l, iter r, cmpfunc *cmp, void *data)
{
if(l==r) return;
iter i(l), p(l);
for(i++; i!=r; i++)
if(cmp(*i, *l, data)<0)
i.swap(++p);
l.swap(p);
qsort(l, p, cmp, data);
qsort(++p, r, cmp, data);
}
--
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/
Re: [patch 1/13] Qsort
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. 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? > > > > I thought XOR was more expensie. Anyways, I still don't see any > > advantage in replacing 3 MOVs with 3 XORs. > > Again, no temporaries needed. > > But I benched it and it was quite a bit slower. > > -- > Mathematics is the supreme nostalgia of our time. Yep, it's a difference of four instructions (when using one or two temporary variables and swapping using assignments) versus six instructions (when using xors, since IA32 can't do an xor with both arguments in memory). I originally pitched this idea out to the list just for discussion purposes. Most considered it, and said that the advantages don't outweigh the disadvantages. And that's fine -- it means that the chosen way is that much better considered. Always a good thing. :) -Vadim Lobanov > - > 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/ > - 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/
Re: [patch 1/13] Qsort
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 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? > > I thought XOR was more expensie. Anyways, I still don't see any > advantage in replacing 3 MOVs with 3 XORs. Again, no temporaries needed. But I benched it and it was quite a bit slower. -- 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/
Re: [patch 1/13] Qsort
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 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 :)
> >
> > I like shell sort for small data sets too. And I agree it would be
> > appropiate for the kernel.
> >
> 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 iterative so it
> doesn't eat up stack space (as oposed to qsort which is recursive and eats
> stack like )...
> Yeah, I think shell sort would be good for the kernel.
>
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 gap)
{
gap = (gap*10)/13;
if ( gap == 9 || gap == 10 )
gap = 11;
if ( gap < 1 )
gap = 1;
return gap;
}
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t gap = nmemb;
size_t i, j;
char *p1, *p2;
int swapped;
do {
gap = newgap(gap);
swapped = 0;
for ( i = 0, p1 = base ; i < nmemb-gap ; i++, p1 += size ) {
j = i+gap;
if ( compar(p1, p2 = (char *)base+j*size) > 0 ) {
memswap(p1, p2, size);
swapped = 1;
}
}
} while ( gap > 1 || swapped );
}
-
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/
Re: [patch 1/13] Qsort
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 iterative so it > doesn't eat up stack space (as oposed to qsort which is recursive and eats > stack like )... qsort also has bad worst case performance which matters if you are sorting data provided by a hostile source. - 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/
Re: [patch 1/13] Qsort
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 iterative so it doesn't eat up stack space (as oposed to qsort which is recursive and eats stack like )... qsort also has bad worst case performance which matters if you are sorting data provided by a hostile source. - 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/
Re: [patch 1/13] Qsort
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 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 :)
I like shell sort for small data sets too. And I agree it would be
appropiate for the kernel.
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 iterative so it
doesn't eat up stack space (as oposed to qsort which is recursive and eats
stack like )...
Yeah, I think shell sort would be good for the kernel.
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 newgap(size_t gap)
{
gap = (gap*10)/13;
if ( gap == 9 || gap == 10 )
gap = 11;
if ( gap 1 )
gap = 1;
return gap;
}
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t gap = nmemb;
size_t i, j;
char *p1, *p2;
int swapped;
do {
gap = newgap(gap);
swapped = 0;
for ( i = 0, p1 = base ; i nmemb-gap ; i++, p1 += size ) {
j = i+gap;
if ( compar(p1, p2 = (char *)base+j*size) 0 ) {
memswap(p1, p2, size);
swapped = 1;
}
}
} while ( gap 1 || swapped );
}
-
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/
Re: [patch 1/13] Qsort
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 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? I thought XOR was more expensie. Anyways, I still don't see any advantage in replacing 3 MOVs with 3 XORs. Again, no temporaries needed. But I benched it and it was quite a bit slower. -- 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/
Re: [patch 1/13] Qsort
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. 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? I thought XOR was more expensie. Anyways, I still don't see any advantage in replacing 3 MOVs with 3 XORs. Again, no temporaries needed. But I benched it and it was quite a bit slower. -- Mathematics is the supreme nostalgia of our time. Yep, it's a difference of four instructions (when using one or two temporary variables and swapping using assignments) versus six instructions (when using xors, since IA32 can't do an xor with both arguments in memory). I originally pitched this idea out to the list just for discussion purposes. Most considered it, and said that the advantages don't outweigh the disadvantages. And that's fine -- it means that the chosen way is that much better considered. Always a good thing. :) -Vadim Lobanov - 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/ - 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/
Re: [patch 1/13] Qsort
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 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
Shellsort is much simpler, and not much slower for small datasets. Plus no
extra space for stacks.
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.
Qsort is OK as long as you have direct access to each element. In case of
lists, it is better to just use mergesort.
Qsort does not need to do random access. I posted an efficient
doubly-linked list version here four years ago:
templateclass T
void listT::qsort(iter l, iter r, cmpfunc *cmp, void *data)
{
if(l==r) return;
iter i(l), p(l);
for(i++; i!=r; i++)
if(cmp(*i, *l, data)0)
i.swap(++p);
l.swap(p);
qsort(l, p, cmp, data);
qsort(++p, r, cmp, data);
}
--
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/
Re: [patch 1/13] Qsort
-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 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 :) I like shell sort for small data sets too. And I agree it would be appropiate for the kernel. FWIW, we already have a Shell sort for the ngroups stuff in kernel/sys.c:groups_sort() that could be made generic. - -- Mike Waychison Sun Microsystems, Inc. 1 (650) 352-5299 voice 1 (416) 202-8336 voice ~~ NOTICE: The opinions expressed in this email are held by me, and may not represent the views of Sun Microsystems, Inc. ~~ -BEGIN PGP SIGNATURE- Version: GnuPG v1.2.5 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org iD8DBQFB9XDzdQs4kOxk3/MRAs2ZAJ4if1XRFAiWsgb1wvTInFLUVGHesgCfWxCJ Efyrr4PkG/KrqefAVAQjt+c= =/OPh -END PGP SIGNATURE- - 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/
Re: [patch 1/13] Qsort
[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 newgap(size_t gap)
{
gap = (gap*10)/13;
if ( gap == 9 || gap == 10 )
gap = 11;
if ( gap 1 )
gap = 1;
return gap;
}
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t gap = nmemb;
size_t i, j;
char *p1, *p2;
int swapped;
do {
gap = newgap(gap);
swapped = 0;
for ( i = 0, p1 = base ; i nmemb-gap ; i++, p1 += size ) {
j = i+gap;
if ( compar(p1, p2 = (char *)base+j*size) 0 ) {
memswap(p1, p2, size);
swapped = 1;
}
}
} while ( gap 1 || swapped );
}
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 third less copies)).
Have you found a proof for the O(n log n) claim?
I'd write as attached (careful, a local element on stack!)
/*
* shellsort.c: Shell sort
*
* Copyright (c) 2005, Horst H. von Brand [EMAIL PROTECTED]
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
* * Neither the name of Horst H. von Brand nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* AS IS AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include string.h
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
int i, j, h;
char tmp[size];
for(h = 1; h nmemb; h = 3 * h + 1)
;
do {
h /= 3;
for(i = h; i nmemb; i++) {
memcpy(tmp, base + i * size, size);
for(j = i - h; j = 0 compar(tmp, base + j * size); j -= h)
memcpy(base + (j + h) * size, base + j * size, size);
memcpy(base + (j + h) * size, tmp, size);
}
} while(h 1);
}
--
Dr. Horst H. von Brand User #22616 counter.li.org
Departamento de Informatica Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria +56 32 654239
Casilla 110-V, Valparaiso, ChileFax: +56 32 797513
Re: [patch 1/13] Qsort
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 third less copies)). Have you found a proof for the O(n log n) claim? Why a Comb Sort is NOT a Shell Sort A shell sort completely sorts the data for each gap size. A comb sort takes a more optimistic approach and doesn't require data be completely sorted at a gap size. The comb sort assumes that out-of-order data will be cleaned-up by smaller gap sizes as the sort proceeds. Reference: http://world.std.com/~jdveale/combsort.htm Another good reference: http://yagni.com/combsort/index.php Personally, i've used it in the past because of it's small size. With C++ templates you can have a copy of the routine generated for a specific datatype, thus skipping the costly function call used for each compare. With some C macro magic, i presume something similar can be done, for time-critical applications. Best regards, Eric St-Laurent - 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/
Re: [patch 1/13] Qsort
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 info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch 1/13] Qsort
"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 sorting > small sets of elements in qsort as well. It makes no sense for smallish sets, insertion sort is better. -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, ChileFax: +56 32 797513 - 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/
Re: [patch 1/13] Qsort
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 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 Shellsort is much simpler, and not much slower for small datasets. Plus no extra space for stacks. > 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. Qsort is OK as long as you have direct access to each element. In case of lists, it is better to just use mergesort. -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, ChileFax: +56 32 797513 - 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/
Re: [patch 1/13] Qsort
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 explicit stack of pointer that store the > + next array partition to sort. To save time, this maximum amount > + of space required to store an array of SIZE_MAX is allocated on the > + stack. Assuming a 32-bit (64 bit) integer for size_t, this needs > + only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). > + Pretty cheap, actually. Not really, given the strict size restrictions in-kernel. Has there been any comparison between the original and this one? Code size, stack use, speed, ...? -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, ChileFax: +56 32 797513 - 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/
Re: [patch 1/13] Qsort
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 - pl) > 15) {
/* quicksort partition */
pm = pl + ((pr - pl) >> 1);
if ((*pm,*pl)) SWAP(*pm,*pl);
if ((*pr,*pm)) SWAP(*pr,*pm);
if ((*pm,*pl)) SWAP(*pm,*pl);
vp = *pm;
pi = pl;
pj = pr - 1;
SWAP(*pm,*pj);
for(;;) {
do ++pi; while ((*pi,vp));
do --pj; while ((vp,*pj));
if (pi >= pj) break;
SWAP(*pi,*pj);
}
SWAP(*pi,*(pr-1));
/* push largest partition on stack */
if (pi - pl < pr - pi) {
*sptr++ = pi + 1;
*sptr++ = pr;
pr = pi - 1;
}else{
*sptr++ = pl;
*sptr++ = pi - 1;
pl = pi + 1;
}
}
/* insertion sort */
for(pi = pl + 1; pi <= pr; ++pi) {
vp = *pi;
for(pj = pi, pt = pi - 1; pj > pl && (vp,
*pt);) {
*pj-- = *pt--;
}
*pj = vp;
}
if (sptr == stack) break;
pr = *(--sptr);
pl = *(--sptr);
}
}
void heapsort0( *a, long n)
{
tmp;
long i,j,l;
/* The array needs to be offset by one for heapsort indexing */
a -= 1;
for (l = n>>1; l > 0; --l) {
tmp = a[l];
for (i = l, j = l<<1; j <= n;) {
if (j < n && (a[j], a[j+1]))
j += 1;
if ((tmp, a[j])) {
a[i] = a[j];
i = j;
j += j;
}else
break;
}
a[i] = tmp;
}
for (; n > 1;) {
tmp = a[n];
a[n] = a[1];
n -= 1;
for (i = 1, j = 2; j <= n;) {
if (j < n && (a[j], a[j+1]))
j++;
if ((tmp, a[j])) {
a[i] = a[j];
i = j;
j += j;
}else
break;
}
a[i] = tmp;
}
}
-
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/
Re: [patch 1/13] Qsort
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 1 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/
Re: [patch 1/13] Qsort
> 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 O(n^(3/2))
> > runtime (IIRC),
>
> Yes, there is.
After doing a small amount of research into this, according to the abstract at
http://www.cs.princeton.edu/~rs/shell/paperF.pdf you can get O(n^(4/3))
with different increment sequences. (1, 8, 23, 77, 281 ...)
So I guess the sort function could look something like this for XFS use
(for reference only!):
void shellsort(void *array, size_t total_elems, size_t size,
int (*cmp)(const void *, const void *))
{
size_t i, j;
int k, h;
register char *a = array;
const int incs[3] = {23, 8, 1};
for (k = 0; k < 3; k++) {
for (h = incs[k], i = h; i < total_elems; i++) {
j = i;
while (j >= h && cmp(a + (j-h) * size, a + j * size) > 0) {
swap(a + j * size, a + (j-h) * size);
j -= h;
}
}
}
}
-- James Lamanna
-
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/
Re: [patch 1/13] Qsort
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. Take care not to put any arrays on the stack though, else the CONFIG_4KSTACKS punters won't be happy. cheers. -- Nathan - 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/
Re: [patch 1/13] Qsort
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 {\
> *__a ^= *__b; \
> *__b ^= *__a; \
> *__a ^= *__b; \
> __a++; \
> __b++; \
> } while ((--__size) > 0); \
> } while (0)
>
> What do you think? :)
I think you'll confuse the compiler and get worse results.
r~
-
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/
Re: [patch 1/13] Qsort
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 even close to whatever suboptimal > code gcc might produce here. Also I'm not convinced that gcc > generates bad code in the first place. The code I get makes perfect > sense. Fixed-sized slab-based kmalloc is O(1) (and pretty darn fast). If we take a constant overhead for every local variable lookup in qsort, that's O(n log n). Putting the stack vars last might fix that, but I think it needs testing. I'll try it. -- 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/
Re: [patch 1/13] Qsort
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 not convinced that gcc generates bad code in the first place. The code I get makes perfect sense. -- Andreas. - 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/
Re: [patch 1/13] Qsort
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 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 :) > > > > I like shell sort for small data sets too. And I agree it would be > > appropiate for the kernel. > > > 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), Yes, there is. > and another nice property is that it's iterative so it > doesn't eat up stack space (as oposed to qsort which is recursive and eats > stack like )... 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?) sort for sorting small sets of elements in qsort as well. > Yeah, I think shell sort would be good for the kernel. I agree. Greets, RJW -- - Would you tell me, please, which way I ought to go from here? - That depends a good deal on where you want to get to. -- Lewis Carroll "Alice's Adventures in Wonderland" - 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/
Re: [patch 1/13] Qsort
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 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 :) I like shell sort for small data sets too. And I agree it would be appropiate for the kernel. 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), Yes, there is. and another nice property is that it's iterative so it doesn't eat up stack space (as oposed to qsort which is recursive and eats stack like )... 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?) sort for sorting small sets of elements in qsort as well. Yeah, I think shell sort would be good for the kernel. I agree. Greets, RJW -- - Would you tell me, please, which way I ought to go from here? - That depends a good deal on where you want to get to. -- Lewis Carroll Alice's Adventures in Wonderland - 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/
Re: [patch 1/13] Qsort
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 not convinced that gcc generates bad code in the first place. The code I get makes perfect sense. -- Andreas. - 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/
Re: [patch 1/13] Qsort
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 even close to whatever suboptimal code gcc might produce here. Also I'm not convinced that gcc generates bad code in the first place. The code I get makes perfect sense. Fixed-sized slab-based kmalloc is O(1) (and pretty darn fast). If we take a constant overhead for every local variable lookup in qsort, that's O(n log n). Putting the stack vars last might fix that, but I think it needs testing. I'll try it. -- 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/
Re: [patch 1/13] Qsort
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. Take care not to put any arrays on the stack though, else the CONFIG_4KSTACKS punters won't be happy. cheers. -- Nathan - 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/
Re: [patch 1/13] Qsort
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 O(n^(3/2))
runtime (IIRC),
Yes, there is.
After doing a small amount of research into this, according to the abstract at
http://www.cs.princeton.edu/~rs/shell/paperF.pdf you can get O(n^(4/3))
with different increment sequences. (1, 8, 23, 77, 281 ...)
So I guess the sort function could look something like this for XFS use
(for reference only!):
void shellsort(void *array, size_t total_elems, size_t size,
int (*cmp)(const void *, const void *))
{
size_t i, j;
int k, h;
register char *a = array;
const int incs[3] = {23, 8, 1};
for (k = 0; k 3; k++) {
for (h = incs[k], i = h; i total_elems; i++) {
j = i;
while (j = h cmp(a + (j-h) * size, a + j * size) 0) {
swap(a + j * size, a + (j-h) * size);
j -= h;
}
}
}
}
-- James Lamanna
-
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/
Re: [patch 1/13] Qsort
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 1 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/
Re: [patch 1/13] Qsort
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;
for(;;) {
while ((pr - pl) 15) {
/* quicksort partition */
pm = pl + ((pr - pl) 1);
if (lessthan(*pm,*pl)) SWAP(*pm,*pl);
if (lessthan(*pr,*pm)) SWAP(*pr,*pm);
if (lessthan(*pm,*pl)) SWAP(*pm,*pl);
vp = *pm;
pi = pl;
pj = pr - 1;
SWAP(*pm,*pj);
for(;;) {
do ++pi; while (lessthan(*pi,vp));
do --pj; while (lessthan(vp,*pj));
if (pi = pj) break;
SWAP(*pi,*pj);
}
SWAP(*pi,*(pr-1));
/* push largest partition on stack */
if (pi - pl pr - pi) {
*sptr++ = pi + 1;
*sptr++ = pr;
pr = pi - 1;
}else{
*sptr++ = pl;
*sptr++ = pi - 1;
pl = pi + 1;
}
}
/* insertion sort */
for(pi = pl + 1; pi = pr; ++pi) {
vp = *pi;
for(pj = pi, pt = pi - 1; pj pl lessthan(vp,
*pt);) {
*pj-- = *pt--;
}
*pj = vp;
}
if (sptr == stack) break;
pr = *(--sptr);
pl = *(--sptr);
}
}
void heapsort0typename(typename *a, long n)
{
typename tmp;
long i,j,l;
/* The array needs to be offset by one for heapsort indexing */
a -= 1;
for (l = n1; l 0; --l) {
tmp = a[l];
for (i = l, j = l1; j = n;) {
if (j n lessthan(a[j], a[j+1]))
j += 1;
if (lessthan(tmp, a[j])) {
a[i] = a[j];
i = j;
j += j;
}else
break;
}
a[i] = tmp;
}
for (; n 1;) {
tmp = a[n];
a[n] = a[1];
n -= 1;
for (i = 1, j = 2; j = n;) {
if (j n lessthan(a[j], a[j+1]))
j++;
if (lessthan(tmp, a[j])) {
a[i] = a[j];
i = j;
j += j;
}else
break;
}
a[i] = tmp;
}
}
-
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/
Re: [patch 1/13] Qsort
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 explicit stack of pointer that store the + next array partition to sort. To save time, this maximum amount + of space required to store an array of SIZE_MAX is allocated on the + stack. Assuming a 32-bit (64 bit) integer for size_t, this needs + only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). + Pretty cheap, actually. Not really, given the strict size restrictions in-kernel. Has there been any comparison between the original and this one? Code size, stack use, speed, ...? -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, ChileFax: +56 32 797513 - 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/
Re: [patch 1/13] Qsort
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 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 Shellsort is much simpler, and not much slower for small datasets. Plus no extra space for stacks. 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. Qsort is OK as long as you have direct access to each element. In case of lists, it is better to just use mergesort. -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, ChileFax: +56 32 797513 - 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/
Re: [patch 1/13] Qsort
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 sorting small sets of elements in qsort as well. It makes no sense for smallish sets, insertion sort is better. -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, ChileFax: +56 32 797513 - 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/
Re: [patch 1/13] Qsort
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), * __b = (b); \
> > do {\
> > *__a ^= *__b; \
> > *__b ^= *__a; \
> > *__a ^= *__b; \
> > __a++; \
> > __b++; \
> > } while ((--__size) > 0); \
> >} while (0)
> >
> >What do you think? :)
>
> 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.
It will even be worse because we are accessing memory, and most architectures
will not be able to use a memory reference for both operands of the XOR.
Basically, what will be generated will look like this :
tmp = *b
*a ^= tmp
tmp ^= *a
*b = tmp
*a ^= tmp
which is 5 cycles, or 4 if the two last instructions get merged. And there's
3 memory reads + 3 memory writes (assuming that the CPU will be smart enough
to reuse *a without accessing memory at instruction 3).
The move is quite faster :
tmp1 = *a
tmp2 = *b
*a = tmp2
*b = tmp1
This is 4 cycles on simple CPUs, or even 2 cycles on most of todays CPUs
which can do the first two fetches at once, and the last two writes at once.
And there are only two reads and two writes.
Clearly this one is better.
Regards,
Willy
-
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/
Re: [patch 1/13] Qsort
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 stack[STACK_SIZE]; > + stack_node stack[fls(size) - fls(MAX_THRESH) + 1]; Yes, indeed. Though I think even here, we'd prefer to use kmalloc because gcc generates suboptimal code for variable-sized stack vars. -- 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/
Re: [patch 1/13] Qsort
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]; -- Andreas Gruenbacher <[EMAIL PROTECTED]> SUSE Labs, SUSE LINUX PRODUCTS GMBH - 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/
Re: [patch 1/13] Qsort
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 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 :) > > I like shell sort for small data sets too. And I agree it would be > appropiate for the kernel. > 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 iterative so it doesn't eat up stack space (as oposed to qsort which is recursive and eats stack like )... Yeah, I think shell sort would be good for the kernel. -- Jesper Juhl - 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/
Re: [patch 1/13] Qsort
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 gains. Both are one cycle latency for register<->register on all x86 cores I've looked at. What makes you think differently? I thought XOR was more expensie. Anyways, I still don't see any advantage in replacing 3 MOVs with 3 XORs. - 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/
Re: [patch 1/13] Qsort
> 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 :) I like shell sort for small data sets too. And I agree it would be appropiate for the kernel. -Andi - 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/
Re: [patch 1/13] Qsort
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 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 [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch 1/13] Qsort
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, being subjective), as follows:
> >
> >#define SWAP(a, b, size) \
> >do { \
> > register size_t __size = (size);\
> > register char * __a = (a), * __b = (b); \
> > do {\
> > *__a ^= *__b; \
> > *__b ^= *__a; \
> > *__a ^= *__b; \
> > __a++; \
> > __b++; \
> > } while ((--__size) > 0); \
> >} while (0)
> >
> >What do you think? :)
>
> 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.
>
> Am I missing something?
No temporary variable needed in the xor version. mov and xor are
roughly the same speed, but xor modifies flags.
--
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/
Re: [patch 1/13] Qsort
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 > > 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 [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch 1/13] Qsort
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 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) - 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/
Re: [patch 1/13] Qsort
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)\
do {\
register size_t __size = (size);\
register char * __a = (a), * __b = (b); \
do {\
*__a ^= *__b; \
*__b ^= *__a; \
*__a ^= *__b; \
__a++; \
__b++; \
} while ((--__size) > 0);\
} while (0)
What do you think? :)
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.
Am I missing something?
-
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/
Re: [patch 1/13] Qsort
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 a sort function, so it makes more sense in
> > the common code.
>
> Please update this to kernel formatting standards and try to modernize
> it a bit.
I started working on this with an eye to doing some performance
testing of the insertion sort threshold in userspace, but I'm about to
head out for the day. Here's what I've got so far, compiles but
untested. Note the insertion sort at the end really ought to be using
memmove as well.
/* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
Written by Douglas C. Schmidt ([EMAIL PROTECTED]).
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA. */
/* If you consider tuning this algorithm, you should consult first:
Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
#include
#include
#define min(x,y) ({ \
typeof(x) _x = (x); \
typeof(y) _y = (y); \
(void) (&_x == &_y);\
_x < _y ? _x : _y; })
/* Byte-wise swap two items of size SIZE. */
#define SWAP(a, b, size) \
do \
{ \
size_t __size = (size); \
char *__a = (a), *__b = (b);\
do \
{ \
char __tmp = *__a; \
*__a++ = *__b; \
*__b++ = __tmp; \
} while (--__size > 0); \
} while (0)
/* Discontinue quicksort algorithm when partition gets below this size.
This particular magic number was chosen to work best on a Sun 4/260. */
#define MAX_THRESH 4
/* Stack node declarations used to store unfulfilled partition obligations. */
typedef struct {
void *lo;
void *hi;
} stack_node;
/* Order size using quicksort. This implementation incorporates
four optimizations discussed in Sedgewick:
1. Non-recursive, using an explicit stack of pointer that store the
next array partition to sort. To save time, this maximum amount
of space required to store an array of SIZE_MAX is allocated on the
stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
Pretty cheap, actually.
2. Chose the pivot element using a median-of-three decision tree.
This reduces the probability of selecting a bad pivot value and
eliminates certain extraneous comparisons.
3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
insertion sort to order the MAX_THRESH items within each partition.
This is a big win, since insertion sort is faster for small, mostly
sorted array segments.
4. The larger of the two sub-partitions is always pushed onto the
stack first, with the algorithm then concentrating on the
smaller partition. This *guarantees* no more than log (total_elems)
stack size is needed (actually O(1) in this case)! */
void qsort(void *base, size_t num, size_t size,
int (*cmp) (const void *, const void *))
{
const size_t max_thresh = MAX_THRESH * size;
void *hi, *lo, *mid, *left, *right;
void *end = base + (size * (num - 1));
void *tmp = base;
void *thresh = min(end, base + max_thresh);
void *run, *trav;
stack_node *stack, *top;
if (num == 0)
return;
lo = base;
hi = lo + size * (num - 1);
if (num > MAX_THRESH) {
Re: [patch 1/13] Qsort
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.
Please update this to kernel formatting standards and try to modernize
it a bit.
> +/* Byte-wise swap two items of size SIZE. */
> +#define SWAP(a, b, size) \
> + do \
> +{
> \
> + register size_t __size = (size);
> \
> + register char *__a = (a), *__b = (b);\
> + do \
> + { \
> + char __tmp = *__a; \
> + *__a++ = *__b; \
> + *__b++ = __tmp; \
> + } while (--__size > 0); \
> +} while (0)
Inline, please? Register keyword?!
> +typedef struct
> + {
> +char *lo;
> +char *hi;
> + } stack_node;
void *, please
> +
> +/* The next 5 #defines implement a very fast in-line stack abstraction. */
> +/* The stack needs log (total_elements) entries (we could even subtract
> + log(MAX_THRESH)). Since total_elements has type size_t, we get as
> + upper bound for log (total_elements):
> + bits per byte (CHAR_BIT) * sizeof(size_t). */
> +#define CHAR_BIT 8
> +#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
So the stack is going to be either 256 or 1024 bytes. Seems like we
ought to kmalloc it.
> +#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)),
> ++top))
> +#define POP(low, high) ((void) (--top, (low = top->lo), (high =
> top->hi)))
> +#define STACK_NOT_EMPTY (stack < top)
There's only one usage of POP, one of STACK_NOT_EMPTY and two of PUSH
that can trivially be made one. Please kill these macros.
> + 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
> + insertion sort to order the MAX_THRESH items within each partition.
> + This is a big win, since insertion sort is faster for small, mostly
> + sorted array segments.
This observation may be dated, instruction cache issues may dominate now.
> + char *mid = lo + size * ((hi - lo) / size >> 1);
Get rid of all this char* stuff, please. It makes for lots of ugly and
unnecessary casting.
> + if ((*cmp) ((void *) mid, (void *) lo) < 0)
> + SWAP (mid, lo, size);
cmp(mid, lo)
> + if ((*cmp) ((void *) hi, (void *) mid) < 0)
> + SWAP (mid, hi, size);
> + else
> + goto jump_over;
> + if ((*cmp) ((void *) mid, (void *) lo) < 0)
> + SWAP (mid, lo, size);
> + jump_over:;
?!
> + /* Once the BASE_PTR array is partially sorted by quicksort the rest
> + is completely sorted using insertion sort, since this is efficient
> + for partitions below MAX_THRESH size. BASE_PTR points to the beginning
> + of the array to sort, and END_PTR points at the very last element in
> + the array (*not* one beyond it!). */
> +
> + {
> +char *end_ptr = _ptr[size * (total_elems - 1)];
> +char *tmp_ptr = base_ptr;
> +char *thresh = min(end_ptr, base_ptr + max_thresh);
> +register char *run_ptr;
Move these vars to the top or better yet, split this into two functions.
--
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/
Re: [patch 1/13] Qsort
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 instead. Cheers, -- Andreas Gruenbacher <[EMAIL PROTECTED]> SUSE Labs, SUSE LINUX GMBH - 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/
Re: [patch 1/13] Qsort
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 {\
register size_t __size = (size);\
register char * __a = (a), * __b = (b); \
do {\
*__a ^= *__b; \
*__b ^= *__a; \
*__a ^= *__b; \
__a++; \
__b++; \
} while ((--__size) > 0); \
} while (0)
What do you think? :)
-Vadim Lobanov
On Sat, 22 Jan 2005, 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.
>
> Signed-off-by: Andreas Gruenbacher <[EMAIL PROTECTED]>
> Acked-by: Olaf Kirch <[EMAIL PROTECTED]>
>
> Index: linux-2.6.11-rc2/include/linux/kernel.h
> ===
> --- linux-2.6.11-rc2.orig/include/linux/kernel.h
> +++ linux-2.6.11-rc2/include/linux/kernel.h
> @@ -93,6 +93,8 @@ extern int sscanf(const char *, const ch
> __attribute__ ((format (scanf,2,3)));
> extern int vsscanf(const char *, const char *, va_list);
>
> +extern void qsort(void *, size_t, size_t, int (*)(const void *,const void
> *));
> +
> extern int get_option(char **str, int *pint);
> extern char *get_options(const char *str, int nints, int *ints);
> extern unsigned long long memparse(char *ptr, char **retptr);
> Index: linux-2.6.11-rc2/lib/Kconfig
> ===
> --- linux-2.6.11-rc2.orig/lib/Kconfig
> +++ linux-2.6.11-rc2/lib/Kconfig
> @@ -30,6 +30,9 @@ config LIBCRC32C
> require M here. See Castagnoli93.
> Module will be libcrc32c.
>
> +config QSORT
> + bool "Quick Sort"
> +
> #
> # compression support is select'ed if needed
> #
> Index: linux-2.6.11-rc2/lib/Makefile
> ===
> --- linux-2.6.11-rc2.orig/lib/Makefile
> +++ linux-2.6.11-rc2/lib/Makefile
> @@ -25,6 +25,7 @@ obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o
> obj-$(CONFIG_CRC32) += crc32.o
> obj-$(CONFIG_LIBCRC32C) += libcrc32c.o
> obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
> +obj-$(CONFIG_QSORT) += qsort.o
>
> obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
> obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
> Index: linux-2.6.11-rc2/lib/qsort.c
> ===
> --- /dev/null
> +++ linux-2.6.11-rc2/lib/qsort.c
> @@ -0,0 +1,249 @@
> +/* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
> + This file is part of the GNU C Library.
> + Written by Douglas C. Schmidt ([EMAIL PROTECTED]).
> +
> + The GNU C Library is free software; you can redistribute it and/or
> + modify it under the terms of the GNU Lesser General Public
> + License as published by the Free Software Foundation; either
> + version 2.1 of the License, or (at your option) any later version.
> +
> + The GNU C Library is distributed in the hope that it will be useful,
> + but WITHOUT ANY WARRANTY; without even the implied warranty of
> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + Lesser General Public License for more details.
> +
> + You should have received a copy of the GNU Lesser General Public
> + License along with the GNU C Library; if not, write to the Free
> + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
> + 02111-1307 USA. */
> +
> +/* If you consider tuning this algorithm, you should consult first:
> + Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
> + Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
> +
> +# include
> +# include
> +# include
> +
> +MODULE_LICENSE("GPL");
> +
> +/* Byte-wise swap two items of size SIZE. */
> +#define SWAP(a, b, size) \
> + do \
> +{
> \
> + register size_t __size = (size);
> \
> + register char *__a = (a), *__b = (b);\
> + do \
> + { \
> + char __tmp = *__a; \
> + *__a++ = *__b;
Re: [patch 1/13] Qsort
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 {\
register size_t __size = (size);\
register char * __a = (a), * __b = (b); \
do {\
*__a ^= *__b; \
*__b ^= *__a; \
*__a ^= *__b; \
__a++; \
__b++; \
} while ((--__size) 0); \
} while (0)
What do you think? :)
-Vadim Lobanov
On Sat, 22 Jan 2005, 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.
Signed-off-by: Andreas Gruenbacher [EMAIL PROTECTED]
Acked-by: Olaf Kirch [EMAIL PROTECTED]
Index: linux-2.6.11-rc2/include/linux/kernel.h
===
--- linux-2.6.11-rc2.orig/include/linux/kernel.h
+++ linux-2.6.11-rc2/include/linux/kernel.h
@@ -93,6 +93,8 @@ extern int sscanf(const char *, const ch
__attribute__ ((format (scanf,2,3)));
extern int vsscanf(const char *, const char *, va_list);
+extern void qsort(void *, size_t, size_t, int (*)(const void *,const void
*));
+
extern int get_option(char **str, int *pint);
extern char *get_options(const char *str, int nints, int *ints);
extern unsigned long long memparse(char *ptr, char **retptr);
Index: linux-2.6.11-rc2/lib/Kconfig
===
--- linux-2.6.11-rc2.orig/lib/Kconfig
+++ linux-2.6.11-rc2/lib/Kconfig
@@ -30,6 +30,9 @@ config LIBCRC32C
require M here. See Castagnoli93.
Module will be libcrc32c.
+config QSORT
+ bool Quick Sort
+
#
# compression support is select'ed if needed
#
Index: linux-2.6.11-rc2/lib/Makefile
===
--- linux-2.6.11-rc2.orig/lib/Makefile
+++ linux-2.6.11-rc2/lib/Makefile
@@ -25,6 +25,7 @@ obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o
obj-$(CONFIG_CRC32) += crc32.o
obj-$(CONFIG_LIBCRC32C) += libcrc32c.o
obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
+obj-$(CONFIG_QSORT) += qsort.o
obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
Index: linux-2.6.11-rc2/lib/qsort.c
===
--- /dev/null
+++ linux-2.6.11-rc2/lib/qsort.c
@@ -0,0 +1,249 @@
+/* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+ Written by Douglas C. Schmidt ([EMAIL PROTECTED]).
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C Library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, write to the Free
+ Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307 USA. */
+
+/* If you consider tuning this algorithm, you should consult first:
+ Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
+ Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
+
+# include linux/module.h
+# include linux/slab.h
+# include linux/string.h
+
+MODULE_LICENSE(GPL);
+
+/* Byte-wise swap two items of size SIZE. */
+#define SWAP(a, b, size) \
+ do \
+{
\
+ register size_t __size = (size);
\
+ register char *__a = (a), *__b = (b);\
+ do \
+ { \
+ char __tmp = *__a; \
+ *__a++ = *__b; \
+ *__b++ = __tmp;
Re: [patch 1/13] Qsort
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 instead. Cheers, -- Andreas Gruenbacher [EMAIL PROTECTED] SUSE Labs, SUSE LINUX GMBH - 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/
Re: [patch 1/13] Qsort
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.
Please update this to kernel formatting standards and try to modernize
it a bit.
+/* Byte-wise swap two items of size SIZE. */
+#define SWAP(a, b, size) \
+ do \
+{
\
+ register size_t __size = (size);
\
+ register char *__a = (a), *__b = (b);\
+ do \
+ { \
+ char __tmp = *__a; \
+ *__a++ = *__b; \
+ *__b++ = __tmp; \
+ } while (--__size 0); \
+} while (0)
Inline, please? Register keyword?!
+typedef struct
+ {
+char *lo;
+char *hi;
+ } stack_node;
void *, please
+
+/* The next 5 #defines implement a very fast in-line stack abstraction. */
+/* The stack needs log (total_elements) entries (we could even subtract
+ log(MAX_THRESH)). Since total_elements has type size_t, we get as
+ upper bound for log (total_elements):
+ bits per byte (CHAR_BIT) * sizeof(size_t). */
+#define CHAR_BIT 8
+#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
So the stack is going to be either 256 or 1024 bytes. Seems like we
ought to kmalloc it.
+#define PUSH(low, high) ((void) ((top-lo = (low)), (top-hi = (high)),
++top))
+#define POP(low, high) ((void) (--top, (low = top-lo), (high =
top-hi)))
+#define STACK_NOT_EMPTY (stack top)
There's only one usage of POP, one of STACK_NOT_EMPTY and two of PUSH
that can trivially be made one. Please kill these macros.
+ 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
+ insertion sort to order the MAX_THRESH items within each partition.
+ This is a big win, since insertion sort is faster for small, mostly
+ sorted array segments.
This observation may be dated, instruction cache issues may dominate now.
+ char *mid = lo + size * ((hi - lo) / size 1);
Get rid of all this char* stuff, please. It makes for lots of ugly and
unnecessary casting.
+ if ((*cmp) ((void *) mid, (void *) lo) 0)
+ SWAP (mid, lo, size);
cmp(mid, lo)
+ if ((*cmp) ((void *) hi, (void *) mid) 0)
+ SWAP (mid, hi, size);
+ else
+ goto jump_over;
+ if ((*cmp) ((void *) mid, (void *) lo) 0)
+ SWAP (mid, lo, size);
+ jump_over:;
?!
+ /* Once the BASE_PTR array is partially sorted by quicksort the rest
+ is completely sorted using insertion sort, since this is efficient
+ for partitions below MAX_THRESH size. BASE_PTR points to the beginning
+ of the array to sort, and END_PTR points at the very last element in
+ the array (*not* one beyond it!). */
+
+ {
+char *end_ptr = base_ptr[size * (total_elems - 1)];
+char *tmp_ptr = base_ptr;
+char *thresh = min(end_ptr, base_ptr + max_thresh);
+register char *run_ptr;
Move these vars to the top or better yet, split this into two functions.
--
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/
Re: [patch 1/13] Qsort
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 a sort function, so it makes more sense in
the common code.
Please update this to kernel formatting standards and try to modernize
it a bit.
I started working on this with an eye to doing some performance
testing of the insertion sort threshold in userspace, but I'm about to
head out for the day. Here's what I've got so far, compiles but
untested. Note the insertion sort at the end really ought to be using
memmove as well.
/* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
Written by Douglas C. Schmidt ([EMAIL PROTECTED]).
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA. */
/* If you consider tuning this algorithm, you should consult first:
Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
#include unistd.h
#include stdlib.h
#define min(x,y) ({ \
typeof(x) _x = (x); \
typeof(y) _y = (y); \
(void) (_x == _y);\
_x _y ? _x : _y; })
/* Byte-wise swap two items of size SIZE. */
#define SWAP(a, b, size) \
do \
{ \
size_t __size = (size); \
char *__a = (a), *__b = (b);\
do \
{ \
char __tmp = *__a; \
*__a++ = *__b; \
*__b++ = __tmp; \
} while (--__size 0); \
} while (0)
/* Discontinue quicksort algorithm when partition gets below this size.
This particular magic number was chosen to work best on a Sun 4/260. */
#define MAX_THRESH 4
/* Stack node declarations used to store unfulfilled partition obligations. */
typedef struct {
void *lo;
void *hi;
} stack_node;
/* Order size using quicksort. This implementation incorporates
four optimizations discussed in Sedgewick:
1. Non-recursive, using an explicit stack of pointer that store the
next array partition to sort. To save time, this maximum amount
of space required to store an array of SIZE_MAX is allocated on the
stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
Pretty cheap, actually.
2. Chose the pivot element using a median-of-three decision tree.
This reduces the probability of selecting a bad pivot value and
eliminates certain extraneous comparisons.
3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
insertion sort to order the MAX_THRESH items within each partition.
This is a big win, since insertion sort is faster for small, mostly
sorted array segments.
4. The larger of the two sub-partitions is always pushed onto the
stack first, with the algorithm then concentrating on the
smaller partition. This *guarantees* no more than log (total_elems)
stack size is needed (actually O(1) in this case)! */
void qsort(void *base, size_t num, size_t size,
int (*cmp) (const void *, const void *))
{
const size_t max_thresh = MAX_THRESH * size;
void *hi, *lo, *mid, *left, *right;
void *end = base + (size * (num - 1));
void *tmp = base;
void *thresh = min(end, base + max_thresh);
void *run, *trav;
stack_node *stack, *top;
if (num == 0)
return;
lo = base;
hi = lo + size * (num - 1);
if (num MAX_THRESH) {
Re: [patch 1/13] Qsort
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)\
do {\
register size_t __size = (size);\
register char * __a = (a), * __b = (b); \
do {\
*__a ^= *__b; \
*__b ^= *__a; \
*__a ^= *__b; \
__a++; \
__b++; \
} while ((--__size) 0);\
} while (0)
What do you think? :)
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.
Am I missing something?
-
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/
Re: [patch 1/13] Qsort
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 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) - 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/
Re: [patch 1/13] Qsort
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 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 [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch 1/13] Qsort
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, being subjective), as follows:
#define SWAP(a, b, size) \
do { \
register size_t __size = (size);\
register char * __a = (a), * __b = (b); \
do {\
*__a ^= *__b; \
*__b ^= *__a; \
*__a ^= *__b; \
__a++; \
__b++; \
} while ((--__size) 0); \
} while (0)
What do you think? :)
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.
Am I missing something?
No temporary variable needed in the xor version. mov and xor are
roughly the same speed, but xor modifies flags.
--
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/
Re: [patch 1/13] Qsort
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 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 [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch 1/13] Qsort
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 :) I like shell sort for small data sets too. And I agree it would be appropiate for the kernel. -Andi - 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/
Re: [patch 1/13] Qsort
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 gains. Both are one cycle latency for register-register on all x86 cores I've looked at. What makes you think differently? I thought XOR was more expensie. Anyways, I still don't see any advantage in replacing 3 MOVs with 3 XORs. - 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/
Re: [patch 1/13] Qsort
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 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 :) I like shell sort for small data sets too. And I agree it would be appropiate for the kernel. 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 iterative so it doesn't eat up stack space (as oposed to qsort which is recursive and eats stack like )... Yeah, I think shell sort would be good for the kernel. -- Jesper Juhl - 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/
Re: [patch 1/13] Qsort
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]; -- Andreas Gruenbacher [EMAIL PROTECTED] SUSE Labs, SUSE LINUX PRODUCTS GMBH - 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/
Re: [patch 1/13] Qsort
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 stack[STACK_SIZE]; + stack_node stack[fls(size) - fls(MAX_THRESH) + 1]; Yes, indeed. Though I think even here, we'd prefer to use kmalloc because gcc generates suboptimal code for variable-sized stack vars. -- 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/
Re: [patch 1/13] Qsort
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), * __b = (b); \
do {\
*__a ^= *__b; \
*__b ^= *__a; \
*__a ^= *__b; \
__a++; \
__b++; \
} while ((--__size) 0); \
} while (0)
What do you think? :)
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.
It will even be worse because we are accessing memory, and most architectures
will not be able to use a memory reference for both operands of the XOR.
Basically, what will be generated will look like this :
tmp = *b
*a ^= tmp
tmp ^= *a
*b = tmp
*a ^= tmp
which is 5 cycles, or 4 if the two last instructions get merged. And there's
3 memory reads + 3 memory writes (assuming that the CPU will be smart enough
to reuse *a without accessing memory at instruction 3).
The move is quite faster :
tmp1 = *a
tmp2 = *b
*a = tmp2
*b = tmp1
This is 4 cycles on simple CPUs, or even 2 cycles on most of todays CPUs
which can do the first two fetches at once, and the last two writes at once.
And there are only two reads and two writes.
Clearly this one is better.
Regards,
Willy
-
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/
