Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S261436AbVAXEsK (ORCPT ); Sun, 23 Jan 2005 23:48:10 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S261437AbVAXEsK (ORCPT ); Sun, 23 Jan 2005 23:48:10 -0500 Received: from fiura.inf.utfsm.cl ([200.1.19.5]:11400 "EHLO fiura.inf.utfsm.cl") by vger.kernel.org with ESMTP id S261436AbVAXEsG (ORCPT ); Sun, 23 Jan 2005 23:48:06 -0500 Message-Id: <200501240348.j0O3mjt5010461@laptop11.inf.utfsm.cl> To: Andreas Gruenbacher cc: linux-kernel@vger.kernel.org, Neil Brown , Trond Myklebust , Olaf Kirch , "Andries E. Brouwer" , Buck Huppmann , Andrew Morton Subject: Re: [patch 1/13] Qsort In-Reply-To: Message from Andreas Gruenbacher of "Sat, 22 Jan 2005 21:34:01 BST." <20050122203618.962749000@blunzn.suse.de> X-Mailer: MH-E 7.4.2; nmh 1.0.4; XEmacs 21.4 (patch 15) Date: Mon, 24 Jan 2005 00:48:45 -0300 From: Horst von Brand Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1353 Lines: 30 Andreas Gruenbacher said: > Signed-off-by: Andreas Gruenbacher > Acked-by: Olaf Kirch [...] > +/* 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, Chile Fax: +56 32 797513 - 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/