Linus Torvalds wrote:

On Thu, 1 Aug 2002, David S. Miller wrote:

quoted

   Of course, if you can actually measure it, that would be
   interesting.  Naive math gives you a guess for the order of
   magnitude effect, but nothing beats real numbers ;)

The SYSV folks actually did have a buddy allocator a long time ago and
they did implement lazy coalescing because is supposedly improved
performance.

I bet that is mainly because of CPU scalability, and being able to avoid
touching the buddy lists from multiple CPU's - the same reason _we_ have
the per-CPU front-ends on various allocators.

I doubt it is because buddy matters past the 4MB mark. I just can't see
how you can avoid the naive math which says that it should be 1/512th as
common to coalesce to 4MB as it is to coalesce to 8kB.

Buddy costs tend to be down in the noise compared with the cost
of the zone->lock.

I did a per-cpu pages patch a while back which, when it takes that
lock, grabs 16 pages or frees 16 pages.  Anton tested it on the
12-way:  http://samba.org/~anton/linux/2.5.9/  blue -> purple

The cost of rmqueue() and __free_pages_ok went from 13% of system
time down to 2%.  So that 2% speedup is all that's available by fiddling
with the buddy algorithm (I think).  And I bet most of that is still taking
the lock.

Didn't submit the patch because I think a per-cpu page buffer is a bit of
a dopey cop-out.  I have patches here which make most of the page-intensive
fastpaths in the kernel stop using single pages and start using 16-page batches.

That will make a 16-page allocation request just a natural thing
to do.  But we will need a per-cpu buffer to wring the last drops
out of anonymous pagefaults and generic_file_write(), which do not
lend themselves to gang allocation.