Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S261212AbVAWEae (ORCPT ); Sat, 22 Jan 2005 23:30:34 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S261218AbVAWEaV (ORCPT ); Sat, 22 Jan 2005 23:30:21 -0500 Received: from waste.org ([216.27.176.166]:63380 "EHLO waste.org") by vger.kernel.org with ESMTP id S261212AbVAWE3y (ORCPT ); Sat, 22 Jan 2005 23:29:54 -0500 Date: Sat, 22 Jan 2005 20:29:30 -0800 From: Matt Mackall To: Andi Kleen Cc: Felipe Alfaro Solana , Trond Myklebust , linux-kernel@vger.kernel.org, Buck Huppmann , Neil Brown , Andreas Gruenbacher , "Andries E. Brouwer" , Andrew Morton , Olaf Kirch Subject: Re: [patch 1/13] Qsort Message-ID: <20050123042930.GI3867@waste.org> References: <20050122203326.402087000@blunzn.suse.de> <20050122203618.962749000@blunzn.suse.de> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.6+20040907i Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1420 Lines: 34 On Sun, Jan 23, 2005 at 03:39:34AM +0100, Andi Kleen wrote: > Felipe Alfaro Solana writes: > > > > AFAIK, XOR is quite expensive on IA32 when compared to simple MOV > > operatings. Also, since the original patch uses 3 MOVs to perform the > > swapping, and your version uses 3 XOR operations, I don't see any > > gains. > > Both are one cycle latency for register<->register on all x86 cores > I've looked at. What makes you think differently? > > -Andi (who thinks the glibc qsort is vast overkill for kernel purposes > where there are only small data sets and it would be better to use a > simpler one optimized for code size) Mostly agreed. Except: a) the glibc version is not actually all that optimized b) it's nice that it's not recursive c) the three-way median selection does help avoid worst-case O(n^2) behavior, which might potentially be triggerable by users in places like XFS where this is used I'll probably whip up a simpler version tomorrow or Monday and do some size/space benchmarking. I've been meaning to contribute a qsort for doubly-linked lists I've got lying around as well. -- Mathematics is the supreme nostalgia of our time. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/