Received-SPF: pass (google.com: domain of linux-kernel+bounces-98434-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1;
Date: Mon, 11 Mar 2024 03:41:35 +0000
From: Matthew Wilcox <willy@infradead.org>
To: Dave Chinner <david@fromorbit.com>
Cc: linux-mm@kvack.org, linux-fsdevel@vger.kernel.org,
	linux-kernel@vger.kernel.org
Subject: Re: On the optimum size of a batch
Message-ID: <Ze59byUR80z42m8R@casper.infradead.org>
References: <Zeoble0xJQYEAriE@casper.infradead.org>
 <Ze5onaXsI+LT1+Be@dread.disaster.area>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <Ze5onaXsI+LT1+Be@dread.disaster.area>

On Mon, Mar 11, 2024 at 01:12:45PM +1100, Dave Chinner wrote:
> > 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?

What SLUB is currently doing is inefficient.  One of the conversations
I had (off-list) about appropriate batch size is in relation to SLUB-ng
where one of the participants claimed that the batch size of 32 was
obviously too small (it wasn't; the performance problem was due to a
bug).

What you're thinking about is the cost of allocating from the page
allocator (which is now much cheaper than it used to be, but should
be cheaper than it currently is).  But there is another inefficiency
to consider, which is that the slab allocator has a per-slab lock,
and while you can efficiently remove and add a number of objects to
a single slab, you might only have one or two free objects per slab.
To work around this some of the more performance sensitive parts of the
kernel have implemented their own allocator in front of slab.  This is
clearly a bad thing for all of us, and hence Vlastimil has been working
on a better approach.

https://lore.kernel.org/linux-mm/20231129-slub-percpu-caches-v3-0-6bcf536772bc@suse.cz/

> 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....

But that doesn't necessarily mean that you want a larger batch size.
Because you're not just allocating, you're also freeing and over a
large enough timescale the number of objects allocated and freed is
approximately equal.  In the SLUB case, your batch size needs to be
large enough to absorb most of the allcation-vs-free bias jitter; that
is if you know they always alternate AFAFAFAFAF a batch size of 2 would
be fine.  If you know you get four allocations followed by four frees,
having a batch size of 5 woud be fine.  We'd never go to the parent
allocator if we got a AFAAFFAAAFFFAAAAFFFFAAFFAFAAFAAFFF pattern.

> > 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.

No, it's not, it's an illustration that too large a batch size can
actively harm you.

> 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.... ???

People forget these "things we've always known".  I went looking and
couldn't find a good writeup of this, so did my own.  In addition to the
percpu slub batch size, various people have opined that the folio_batch
size (15 objects) is too small for doing things like writeback and
readahead.  They're going to have to bring data to convince me.

> > 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.

Well, now you're just opining without having studied the problem, and
I have, so I can say confidently that you're wrong.  You could read
the code if you like.