linux-kernel - RE: On the optimum size of a batch

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <905fcd730d6e40b992c15ce0fe526941@AcuMS.aculab.com>
Date: Sun, 10 Mar 2024 19:07:41 +0000
From: David Laight <David.Laight@...LAB.COM>
To: 'Matthew Wilcox' <willy@...radead.org>, "linux-mm@...ck.org"
	<linux-mm@...ck.org>
CC: "linux-fsdevel@...r.kernel.org" <linux-fsdevel@...r.kernel.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: RE: On the optimum size of a batch

From: Matthew Wilcox
> Sent: 07 March 2024 19:55
> 
> 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).

I think you are trying to measure the length of a piece of string.
(and not the ones in the box labelled 'pieces of string too small to keep')

What I did recently for a global+local buffer allocator was to make
each entry on the global list itself be a list of objects.
So if the local list was empty it was a single cmpxchg to grab
(about 100) items.
Similarly if the local free list got too big a single locked
operation would free a block of items.
That significantly reduced lock contention.

If was necessary to split the free of very long lists - otherwise
a single item on the global list could contain silly numbers of items.

This was userspace, and we don't talk about the test that ended up
with ALL system memory on one linked list.
I managed to kill enough (remote) things to get a working shell.
It took the system about 20 minutes just to count the linked list!

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)