`On Sun, 2005-12-18 at 19:27 +0200, Pekka Enberg wrote:> Hi Steven,> > On 12/18/05, Steven Rostedt <rostedt@goodmis.org> wrote:> > +       do {> > +               x = 1;> > +               while ((x+i)*size + ALIGN(base+(x+i)*extra, align) <= wastage)> > +                       x <<= 1;> > +               i += (x >> 1);> > +       } while (x > 1);> > The above is pretty hard to read. Perhaps we could give x and i better> names? Also, couldn't we move left part of the expression into a> separate static inline function for readability?Actually, Luuk sent me this patch made by Balbir Singh that was done awhile ago.                extra = sizeof(kmem_bufctl_t);        }-       i = 0;+       i = (wastage - base)/(size + extra);        while (i*size + L1_CACHE_ALIGN(base+i*extra) <= wastage)                i++;-       if (i > 0)+       while (i*size + L1_CACHE_ALIGN(base+i*extra) > wastage)                i--;This actually has a O(1) with a K=2.  Analyzing this further, I've comeup with the below patch.  This patch removes the need for the secondwhile, and adds a comment to why. The size is already calculated to beno smaller than the alignment. So that the division will not returnsomething greater than 1 of what is needed.  So the if (i > 0) after thewhile is all that is needed.  So this patch is O(1) K=1.-- SteveIndex: linux-2.6.15-rc5/mm/slab.c===================================================================--- linux-2.6.15-rc5.orig/mm/slab.c	2005-12-16 16:24:09.000000000 -0500+++ linux-2.6.15-rc5/mm/slab.c	2005-12-18 13:30:13.000000000 -0500@@ -708,7 +708,14 @@ 		base = sizeof(struct slab); 		extra = sizeof(kmem_bufctl_t); 	}-	i = 0;+	/*+	 * Divide the amount we have, by the amount we need for+	 * each object.  Since the size is already calculated+	 * to be no less than the alignment, this result will+	 * not be any greater than 1 that we need, and this will+	 * be subtracted after the while loop.+	 */+	i = (wastage - base)/(size + extra); 	while (i*size + ALIGN(base+i*extra, align) <= wastage) 		i++; 	if (i > 0)-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`