Messages in this thread Patch in this message |  | | Subject | kmalloc optimization | From | David Wragg <> | Date | 26 Aug 2000 23:33:45 +0000 |
| |
Hi,
Intel's P6 processors have BSR, a cheap (couple of cycles) instruction to find the most significant set bit in a word. This can be used in kmalloc to identify the slab cache to allocate from; it's quicker than the linear search through to cache_sizes array that is currently used. There's a proof of concept patch below.
However, on the P5 and earlier Intel processors BSR is very slow, and other architectures might not have such an instruction at all. There is also a general optimization possible, though, to use a binary search rather than a linear search.
A proper patch including both optimizations would clutter up the kmalloc() definition a bit, and although kmalloc is important() I doubt the improvement would ever be measurable under real workloads, so I'm looking for feedback on whether people think this is a good/bad idea. I'd also like to know whether BSR is similarly cheap on the Athlon (and the P4; the Willamette information I have doesn't mention BSR, though since the branch misprediction penalty is horrible this optmization is almost certainly still valid there).
David Wragg
diff -rua linux-2.4.0test7/include/asm-i386/bitops.h linux-2.4.0test7.mod/include/asm-i386/bitops.h --- linux-2.4.0test7/include/asm-i386/bitops.h Sat Aug 26 00:18:14 2000 +++ linux-2.4.0test7.mod/include/asm-i386/bitops.h Sun Aug 27 00:07:15 2000 @@ -190,6 +190,17 @@ return word; } +/* + * ffzr = Find First Zero in word reverse, i.e. from the MSB down. + */ +extern __inline__ unsigned long ffzr(unsigned long word) +{ + __asm__("bsrl %1,%0" + :"=r" (word) + :"r" (~word)); + return word; +} + #ifdef __KERNEL__ /* diff -rua linux-2.4.0test7/mm/slab.c linux-2.4.0test7.mod/mm/slab.c --- linux-2.4.0test7/mm/slab.c Fri Aug 25 23:48:58 2000 +++ linux-2.4.0test7.mod/mm/slab.c Sun Aug 27 00:07:21 2000 @@ -324,24 +324,16 @@ kmem_cache_t *cs_dmacachep; } cache_sizes_t; -static cache_sizes_t cache_sizes[] = { #if PAGE_SIZE == 4096 - { 32, NULL, NULL}, +#define CACHE_SIZE_SHIFT_MIN 5 +#else +#define CACHE_SIZE_SHIFT_MIN 6 #endif - { 64, NULL, NULL}, - { 128, NULL, NULL}, - { 256, NULL, NULL}, - { 512, NULL, NULL}, - { 1024, NULL, NULL}, - { 2048, NULL, NULL}, - { 4096, NULL, NULL}, - { 8192, NULL, NULL}, - { 16384, NULL, NULL}, - { 32768, NULL, NULL}, - { 65536, NULL, NULL}, - {131072, NULL, NULL}, - { 0, NULL, NULL} -}; + +#define CACHE_SIZE_SHIFT_MAX 17 + +static cache_sizes_t cache_sizes[BITS_PER_LONG - CACHE_SIZE_SHIFT_MIN]; + /* internal cache of cache description objs */ static kmem_cache_t cache_cache = { @@ -424,7 +416,7 @@ */ void __init kmem_cache_sizes_init(void) { - cache_sizes_t *sizes = cache_sizes; + int i; char name[20]; /* * Fragmentation resistance on low memory - only use bigger @@ -432,13 +424,17 @@ */ if (num_physpages > (32 << 20) >> PAGE_SHIFT) slab_break_gfp_order = BREAK_GFP_ORDER_HI; - do { + + for (i = 0; i <= CACHE_SIZE_SHIFT_MAX - CACHE_SIZE_SHIFT_MIN; i++) { + cache_sizes_t *sizes = cache_sizes + i; + /* For performance, all the general caches are L1 aligned. * This should be particularly beneficial on SMP boxes, as it * eliminates "false sharing". * Note for systems short on memory removing the alignment will * allow tighter packing of the smaller caches. */ - sprintf(name,"size-%Zd",sizes->cs_size); + sizes->cs_size = 1 << (i + CACHE_SIZE_SHIFT_MIN); + sprintf(name,"size-%Zd", sizes->cs_size); if (!(sizes->cs_cachep = kmem_cache_create(name, sizes->cs_size, 0, SLAB_HWCACHE_ALIGN, NULL, NULL))) { @@ -455,8 +451,7 @@ SLAB_CACHE_DMA|SLAB_HWCACHE_ALIGN, NULL, NULL); if (!sizes->cs_dmacachep) BUG(); - sizes++; - } while (sizes->cs_size); + } } int __init kmem_cpucache_init(void) @@ -1520,14 +1515,15 @@ */ void * kmalloc (size_t size, int flags) { - cache_sizes_t *csizep = cache_sizes; + cache_sizes_t *csizep; + + size = (size | 1 << CACHE_SIZE_SHIFT_MIN) - 1; + csizep = cache_sizes + ffzr(~size) + 1 - CACHE_SIZE_SHIFT_MIN; - for (; csizep->cs_size; csizep++) { - if (size > csizep->cs_size) - continue; + if (csizep->cs_size) return __kmem_cache_alloc(flags & GFP_DMA ? csizep->cs_dmacachep : csizep->cs_cachep, flags); - } + BUG(); // too big size return NULL; } @@ -1577,17 +1573,15 @@ kmem_cache_t * kmem_find_general_cachep (size_t size, int gfpflags) { - cache_sizes_t *csizep = cache_sizes; - /* This function could be moved to the header file, and * made inline so consumers can quickly determine what * cache pointer they require. */ - for ( ; csizep->cs_size; csizep++) { - if (size > csizep->cs_size) - continue; - break; - } + cache_sizes_t *csizep; + + size = (size | 1 << CACHE_SIZE_SHIFT_MIN) - 1; + csizep = cache_sizes + ffzr(~size) + 1 - CACHE_SIZE_SHIFT_MIN; + return (gfpflags & GFP_DMA) ? csizep->cs_dmacachep : csizep->cs_cachep; } - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org Please read the FAQ at http://www.tux.org/lkml/
|  |