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