Messages in this thread | | | Date | Sun, 23 Jan 2005 08:49:04 -0800 | From | Matt Mackall <> | Subject | 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 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/
| |