lkml.org 
[lkml]   [2005]   [Dec]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Subject[PATCH] micro optimization of cache_estimate in slab.c
From
Date
OK, I know this is really just a micro optimization, but I figured I'd
submit it anyway. Looking into the slab code, I came across the
cache_estimate function, which has the following code:

i = 0;
while (i*size + ALIGN(base+i*extra, align) <= wastage)
i++;
if (i > 0)
i--;

Now this is counting linearly up and will be O(n) for n = number of
objects in the page order. Since objects range up to 202 (according to
my /proc/slabinfo). So I figured there must be a better way. So I added
this:

i = 0;
do {
x = 1;
while ((x+i)*size + ALIGN(base+(x+i)*extra, align) <= wastage)
x <<= 1;
i += (x >> 1);
} while (x > 1);

Which now makes it O(log n). This basically does a binary search for
the upper range. I tested this code in userspace, and it works just the
same as the original code, but with less iterations.

I know this is really a micro optimization, but if you think every usec
counts, then we can use this patch ;)

-- 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 03:16:18.000000000 -0500
@@ -700,6 +700,7 @@
int flags, size_t *left_over, unsigned int *num)
{
int i;
+ int x;
size_t wastage = PAGE_SIZE<<gfporder;
size_t extra = 0;
size_t base = 0;
@@ -709,10 +710,12 @@
extra = sizeof(kmem_bufctl_t);
}
i = 0;
- while (i*size + ALIGN(base+i*extra, align) <= wastage)
- i++;
- if (i > 0)
- i--;
+ do {
+ x = 1;
+ while ((x+i)*size + ALIGN(base+(x+i)*extra, align) <= wastage)
+ x <<= 1;
+ i += (x >> 1);
+ } while (x > 1);

if (i > SLAB_LIMIT)
i = SLAB_LIMIT;

-
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 09:25    [W:0.036 / U:0.192 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site