lkml.org 
[lkml]   [2005]   [Dec]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
SubjectRe: [PATCH] micro optimization of cache_estimate in slab.c
FromSteven Rostedt <>
DateSun, 18 Dec 2005 13:37:42 -0500
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)

-
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/

\
 
 \ /
  Last update: 2005-12-18 19:41    [from the cache]
©2003-2010