lkml.org 
[lkml]   [2000]   [Aug]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: kmalloc optimization
On Sat, Aug 26, 2000 at 11:33:45PM +0000, David Wragg wrote:
> 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).

The power of two buckets have to go sooner or later anyways, because they're
fairly suboptimal. They're really only a leftover from the old kmalloc.
So therefore I don't think it makes too much sense
to apply your patch now, because it would have to be removed again later.

BTW, there would be a much better more cycle saving optimization: for the
common case of a constant argument to kmalloc you can check for it
using __builtin_constant_p and select the right slab at compile time.
(this should be usually faster than your ffz hack and can be easily adapted
to other default slab sizes too)

-Andi
-
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/

\
 
 \ /
  Last update: 2005-03-22 12:38    [W:0.063 / U:22.884 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site