micro optimization of cache_estimate in slab.c
PATCH 1/1 micro optimization of cache_estimate in slab.c
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
mm/slab.c +7 -4
@@ -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 ;
Hi Steven,
mm/slab.c line 718
Quoted 6 lines · Steven Rostedt
mm/slab.c +6
-0+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?
Pekka
Quoted 10 lines · Pekka Enberg
Hi Steven,
Review
Quoted 6 lines · Steven Rostedt
(quoted diff) +6
-0+ do { + x = 1; + while ((x+i)*size + ALIGN(base+(x+i)*extra, align) <= wastage) + x <<= 1; + i += (x >> 1); + } while (x > 1);
Quoted 3 lines
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
mm/slab.c +8 -1
@@ -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 )
Quoted 10 lines
Index:
linux-2.6.15-rc5/mm/slab.c
===================================================================mm/slab.c 2005-12-18 13:30:13.000000000 -0500 renamed from mm/slab.c 2005-12-16 16:24:09.000000000 -0500 +1
-1@@ -708,7 +708,14 @@ base = sizeof(struct slab); extra = sizeof(kmem_bufctl_t); } - i = 0; + /*
mm/slab.c 2005-12-18 13:30:13.000000000 -0500 line 721
Quoted 10 lines
mm/slab.c 2005-12-18 13:30:13.000000000 -0500 renamed from mm/slab.c 2005-12-16 16:24:09.000000000 -0500 +7
-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)
Yes, I recognised the patch because I passed Balbirs version over to Micheal Cohen in early 2002. The patch originaly was intended for 2.4
Complexity of Stevens patch has gone, readability has improved, Steven has taken advantage of context-code and the rationale has been explained in the comment.
Sounds fine to me.
Luuk van der Duim
Partners aan het Werk
Quoted 10 lines · Steven Rostedt
Index:
linux-2.6.15-rc5/mm/slab.c
===================================================================mm/slab.c +1
-1@@ -708,7 +708,14 @@ base =sizeof (struct slab ); extra =sizeof (kmem_bufctl_t); } - i =0 ; +/*
mm/slab.c line 721
Quoted 10 lines
mm/slab.c +7
-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 )
Thanks. Looks much better but I am still wondering if we could get rid of the loop altogether. Hmm.
Pekka