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/
This archive was generated by hypermail 2b29 : Thu Aug 31 2000 - 21:00:18 EST