Messages in this thread Patch in this message |  | | | Subject | Re: [PATCH] micro optimization of cache_estimate in slab.c | | From | Steven Rostedt <> | | Date | Sun, 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/
|  |