lkml.org 
[lkml]   [2001]   [Nov]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
SubjectRe: slab: avoid linear search in kmalloc? (GCC Guru wanted :)
From
Date
>>>>> "Bernd" == Bernd Eckenfels <ecki@lina.inka.de> writes:

Bernd> Hello,
Bernd> I noticed that kmalloc and kmem_find_general_cachep are doing a linear
Bernd> search in the cache_sizes array. Isnt it better to speed that up by doing a
Bernd> binary search or a b-tree if like the following patch?

Here is a patch using a gcc extension. gcc generates binary search for the case.

Regards,
-velco

--- slab.c.orig Wed Sep 19 00:16:26 2001
+++ slab.c Wed Nov 21 11:11:09 2001
@@ -1533,15 +1533,9 @@ void * kmem_cache_alloc (kmem_cache_t *c
*/
void * kmalloc (size_t size, int flags)
{
- cache_sizes_t *csizep = cache_sizes;
-
- for (; csizep->cs_size; csizep++) {
- if (size > csizep->cs_size)
- continue;
- return __kmem_cache_alloc(flags & GFP_DMA ?
- csizep->cs_dmacachep : csizep->cs_cachep, flags);
- }
- return NULL;
+ kmem_cache_t *cp = kmem_find_general_cachep (size, flags);
+
+ return cp == NULL ? NULL : __kmem_cache_alloc(cp, flags);
}

/**
@@ -1589,18 +1583,66 @@ void kfree (const void *objp)

kmem_cache_t * kmem_find_general_cachep (size_t size, int gfpflags)
{
- cache_sizes_t *csizep = cache_sizes;
+ int idx;

- /* 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;
+ switch (size) {
+#if PAGE_SIZE == 4096
+ case 0 ... 32:
+ idx = 0;
+ break;
+ case 33 ... 64:
+ idx = 1;
+ break;
+#else
+ case 0 ... 64:
+ idx = 1;
+ break;
+#endif
+ case 65 ... 128:
+ idx = 2;
+ break;
+ case 129 ... 256:
+ idx = 3;
+ break;
+ case 257 ...512:
+ idx = 4;
+ break;
+ case 513 ... 1024:
+ idx = 5;
+ break;
+ case 1025 ... 2048:
+ idx = 6;
+ break;
+ case 2049 ... 4096:
+ idx = 7;
+ break;
+ case 4097 ... 8192:
+ idx = 8;
+ break;
+ case 8193 ... 16384:
+ idx = 9;
+ break;
+ case 16385 ... 32768:
+ idx = 10;
+ break;
+ case 32769 ... 65536:
+ idx = 11;
+ break;
+ case 65537 ... 131072:
+ idx = 12;
+ break;
+ default:
+ idx = -1;
break;
}
- return (gfpflags & GFP_DMA) ? csizep->cs_dmacachep : csizep->cs_cachep;
+
+ if (idx == -1)
+ return NULL;
+
+#if PAGE_SIZE != 4096
+ idx = idx - 1;
+#endif
+ return (gfpflags & GFP_DMA) ? cache_sizes [idx].cs_dmacachep : cache_sizes [idx].cs_cachep;
}

#ifdef CONFIG_SMP
-
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-03-22 13:13    [W:0.097 / U:6.388 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site