[PATCH,RFC] faster kmalloc lookup

[Manfred Spraul <manfred@colorfullife.com>]

[-- Attachment #1: Type: text/plain, Size: 241 bytes --]

kmalloc spends a large part of the total execution time trying to find 
the cache for the passed in size.

What about the attached patch (against 2.5.44-mm5)?
It uses fls jump over the caches that are definitively too small.

--
    Manfred

[-- Attachment #2: patch-fast-kmalloc --]
[-- Type: text/plain, Size: 1219 bytes --]

--- 2.5/mm/slab.c	Sat Oct 26 21:13:33 2002
+++ build-2.5/mm/slab.c	Sat Oct 26 20:40:09 2002
@@ -424,6 +430,7 @@
 	CN("size-131072")
 }; 
 #undef CN
+static struct cache_sizes *malloc_hints[sizeof(size_t)*8];
 
 struct arraycache_init initarray_cache __initdata = { { 0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
 struct arraycache_init initarray_generic __initdata = { { 0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
@@ -587,6 +594,7 @@
 void __init kmem_cache_init(void)
 {
 	size_t left_over;
+	int i;
 
 	init_MUTEX(&cache_chain_sem);
 	INIT_LIST_HEAD(&cache_chain);
@@ -604,6 +612,18 @@
 	 * that initializes ac_data for all new cpus
 	 */
 	register_cpu_notifier(&cpucache_notifier);
+
+	for (i=0;i<sizeof(size_t)*8;i++) {
+		struct cache_sizes *csizep = malloc_sizes;
+		int size = (1<<i)/2+1;
+
+		for ( ; csizep->cs_size; csizep++) {
+			if (size > csizep->cs_size)
+				continue;
+			break;
+		}
+		malloc_hints[i] = csizep;
+	}
 }
 
 
@@ -1796,7 +1816,11 @@
  */
 void * kmalloc (size_t size, int flags)
 {
-	struct cache_sizes *csizep = malloc_sizes;
+	struct cache_sizes *csizep;
+	
+	if(unlikely(size<2))
+		size=2;
+	csizep = malloc_hints[fls((size-1))];
 
 	for (; csizep->cs_size; csizep++) {
 		if (size > csizep->cs_size)