Messages in this thread |  | | Date | Sun, 27 Aug 2000 01:46:05 +0200 | From | "Andi Kleen" <> | Subject | Re: 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/
|  |