Re: [RFC] memory page_alloc zonelist caching speedup

Paul Jackson
2006-10-10T19:35:55Z

Christoph wrote:
> Could it be worth to investigate more radical ideas? This gets way too
> complicated for me. Maybe drop the whole zone list generation idea and
> iterate over nodes in another way?

Worth some thought.

I'll be surprised if this eliminates the usefulness of something
like this zonelist caching patch, however.

Sooner or later, regardless of what shape data structures we have,
we end up having to examine a bunch of nodes when allocating for
workloads or numa emulated configurations that make heavy use of
off-node allocations.

And when that happens, we end up with an N-squared information
flow problem, needing to get information or at least hints as to
which nodes have free pages to the tasks trying to allocate those
pages.

But we really would rather not pay the price of even a linear
scan over N nodes, in either the tasks freeing pages, nor in the
tasks allocating them.

The best I've been able to do, in this patch, is:
1) compact the information, to minimize the cache line footprint, and
2) have the allocators get by on incomplete information, essentially
doing the first scan based on remembering which nodes were
recently noticed to be full.

I predict that regardless of the shape (zonelists, nodemasks or
whatever) of the placement information coming into the core
routine of our allocator, we will still need some sort of caching
like this, bolted onto the side, for the cases making heavy use
of off-node allocations.

So I would not use disgust at the added complexity of this zonelist
caching patch to justify changing the fundamental zonelist structures
used to drive the kernel allocator.