Re: [PATCH] micro optimization of cache_estimate in slab.c

[Steven Rostedt <rostedt@goodmis.org>]

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 a
while 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 come
up with the below patch.  This patch removes the need for the second
while, and adds a comment to why. The size is already calculated to be
no smaller than the alignment. So that the division will not return
something greater than 1 of what is needed.  So the if (i > 0) after the
while is all that is needed.  So this patch is O(1) K=1.

-- Steve

Index: 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)