lkml.org 
[lkml]   [2001]   [Nov]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
Subjectslab: avoid linear search in kmalloc? (GCC Guru wanted :)
From
Hello,

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

I am no gcc expert, so it might not help... any body knows?

I also not sure if removing the elses does produce faster code?

Perhaps we can improve the situation even more by using some fast path
optimization by looking at the usage profile of that function?

btw: the kmem_find_general_cache most likely needs to be inline now... not
sure if my kmalloc rewrite in that case is to bloated, if cut+paste is
better, here.

--- mm/slab.c.org Wed Nov 21 02:02:27 2001
+++ mm/slab.c Wed Nov 21 02:35:38 2001
@@ -1533,14 +1533,13 @@
*/
void * kmalloc (size_t size, int flags)
{
- cache_sizes_t *csizep = cache_sizes;
+ kmem_cache_t *cp;
+
+ cp = kmem_find_general_cachep(size, flags);
+
+ if (cp)
+ return __kmem_cache_alloc(cp, flags);

- 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;
}

@@ -1604,20 +1603,67 @@
local_irq_restore(flags);
}

-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.
+ */
+
+#if PAGE_SIZE == 4096
+#define CACHE_ENTRY(p, f) (f & GFP_DMA ? cache_sizes[p].cs_dmacachep : cache_sizes[p].cs_cachep)
+#else
+#define CACHE_ENTRY(p, f) (f & ? cache_sizes[p-1]. : cache_sizes[p-1].)
+#endif

- /* 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;
+kmem_cache_t * kmem_find_general_cachep (size_t size, int gfpflag)
+{
+ if (size <= 512) {
+ if (size <= 128) {
+#if PAGE_SIZE == 4096
+#endif
+ if (size <= 64) {
+#if PAGE_SIZE == 4096
+ if (size <= 32) {
+ return CACHE_ENTRY(0, gfpflag); // 32
+ }
+#endif
+ return CACHE_ENTRY(1, gfpflag); // 64
+ } else
+ return CACHE_ENTRY(2, gfpflag); // 128
+ } else {
+ if (size <= 256)
+ return CACHE_ENTRY(3, gfpflag); // 256
+ else
+ return CACHE_ENTRY(4, gfpflag); // 512
+ }
}
- return (gfpflags & GFP_DMA) ? csizep->cs_dmacachep : csizep->cs_cachep;
+ if (size <= 8192) {
+ if (size <= 2048) {
+ if (size <= 1024)
+ return CACHE_ENTRY(5, gfpflag); // 1024
+ else
+ return CACHE_ENTRY(6, gfpflag); // 2048
+ } else {
+ if (size <= 4096)
+ return CACHE_ENTRY(7, gfpflag); // 4096
+ else
+ return CACHE_ENTRY(8, gfpflag); // 8192
+ }
+ }
+ if (size <= 131072) {
+ if (size <= 32768) {
+ if (size <= 16384)
+ return CACHE_ENTRY(9, gfpflag); // 16384
+ else
+ return CACHE_ENTRY(10, gfpflag); // 32768
+ } else {
+ if (size <= 65536)
+ return CACHE_ENTRY(11, gfpflag); // 65536
+ else
+ return CACHE_ENTRY(12, gfpflag); // 131072
+ }
+ }
+
+ return NULL;
}

#ifdef CONFIG_SMP
--
(OO) -- Bernd_Eckenfels@Wendelinusstrasse39.76646Bruchsal.de --
( .. ) ecki@{inka.de,linux.de,debian.org} http://home.pages.de/~eckes/
o--o *plush* 2048/93600EFD eckes@irc +497257930613 BE5-RIPE
(O____O) When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl!
-
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.056 / U:1.124 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site