Re: kmalloc optimization

From: Andi Kleen (
Date: Sat Aug 26 2000 - 18:46:05 EST

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)

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

This archive was generated by hypermail 2b29 : Thu Aug 31 2000 - 21:00:18 EST