Re: On the optimum size of a batch

[Dave Chinner]

On Thu, Mar 07, 2024 at 07:55:01PM +0000, Matthew Wilcox wrote:
> I've had a few conversations recently about how many objects should be
> in a batch in some disparate contextx, so I thought I'd write down my
> opinion so I can refer to it in future.  TLDR: Start your batch size
> around 10, adjust the batch size when measurements tell you to change it.
> 
> In this model, let's look at the cost of allocating N objects from an
> allocator.  Assume there's a fixed cost, say 4 (units are not relevant
> here) for going into the allocator and then there's a 1 unit cost per
> object (eg we're taking a spinlock, pulling N objects out of the data
> structure and releasing the spinlock again).
> 
> Allocating 100 * 1 objects would cost 500 units.  Our best case is that
> we could save 396 units by allocating a batch of 100.  But we probably
> don't know how many objects we're going to need to allocate, so we pull
> objects from the allocator in smaller batches.  Here's a table showing
> the costs for different batch sizes:
> 
> Batch size      Cost of allocating 100          thousand        million
> 1               500 (5 * 100)                   5000            5M
> 2               300 (6 * 50)                    3000            3M
> 4               200 (8 * 25)                    2000            2M
> 8               156 (12 * 13)                   1500            1.5M
> 16              140 (20 * 7)                    1260            1.25M
> 32              144 (36 * 4)                    1152            1.13M
> 64              136 (68 * 2)                    1088            1.06M
> 128             132 (132 * 1)                   1056            1.03M

Isn't this just repeating the fundamental observation that SLUB is
based on?  i.e. it can use high-order pages so that it can
pre-allocate optimally sized batches of objects regardless of their
size? i.e.  it tries to size the backing page order to allocate in
chunks of 30-40 objects at a time?

> You can see the knee of this curve is around 8.  It fluctuates a bit after
> that depending on how many "left over" objects we have after allocating
> the 100 it turned out that we needed.  Even if we think we're going to
> be dealing with a _lot_ of objects (the thousand and million column),
> we've got most of the advantage by the time we get to 8 (eg a reduction
> of 3.5M from a total possible reduction of 4M), and while I wouldn't
> sneeze at getting a few more percentage points of overhead reduction,
> we're scrabbling at the margins now, not getting big wins.

Except for SLUB we're actually allocating in the hundreds of
millions to billions of objects on machines with TBs of RAM. IOWs we
really want to be much further down the curve than 8 - batches of at
least 32-64 have significantly lower cost and that matters when
scaling to (and beyond) hundreds of millions of objects....

> This is a simple model for only one situation.  If we have a locking
> contention breakdown, the overhead cost might be much higher than 4 units,
> and that would lead us to a larger batch size.
> 
> Another consideration is how much of each object we have to touch.
> put_pages_list() is frequently called with batches of 500 pages.  In order
> to free a folio, we have to manipulate its contents, so touching at least
> one cacheline per object.

Right, that's simply the cost of the batch cache footprint issue
rather than a "fixed cost mitigation" described for allocation.

So I'm not sure what you're trying to say here? We've known about
these batch optimisation considerations for a long, long time and
that batch size optimisation is always algorithm and access pattern
dependent, so.... ???

> And we make multiple passes over the batch,
> first decrementing the refcount, removing it from the lru list; second
> uncharging the folios from the memcg (writes to folio->memcg_data);
> third calling free_pages_prepare which, eg, sets ->mapping to NULL;
> fourth putting the folio on the pcp list (writing to the list_head).

Sounds like "batch cache footprint" would be reduced by inverting
that algorithm and doing all the work on a single object in a single
pass, rahter than doing it in multiple passes.  That way the cache
footprint of the batch is determined entirely by the size of the
data structures accessed to process each object in the batch.

i.e. if you are going to take an L1 cache miss accessing every
object in the batch anyway, then reducing batch size doesn't improve
overall per-object processing efficiency. All it does is keep the
processing cost down to a single L1 cache miss per object in the
batch. The tradeoff for this is more frequent batch refills, so this
only works is the additional fixed cost for obtaining each batch is
lower than the cost of multiple L1 cache misses per object....

All this says to me is that sometimes the batch size is not actually
the problem that needs fixing - changing the algorithm
and/or processing pipeline to remove the possiblity of repeated
accesses to individual objects in the batch reduces selecting the
batch size down to the same "fixed cost mitigation" case you started
with....

-Dave.
-- 
Dave Chinner
david@xxxxxxxxxxxxx