From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 55B64C369A2 for ; Tue, 8 Apr 2025 17:02:59 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 26F1C6B00BA; Tue, 8 Apr 2025 13:02:57 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1F60A6B00BB; Tue, 8 Apr 2025 13:02:57 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0BE786B00BC; Tue, 8 Apr 2025 13:02:57 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id E10956B00BA for ; Tue, 8 Apr 2025 13:02:56 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 5390F5ABA4 for ; Tue, 8 Apr 2025 17:02:58 +0000 (UTC) X-FDA: 83311496436.07.90F4956 Received: from casper.infradead.org (casper.infradead.org [90.155.50.34]) by imf25.hostedemail.com (Postfix) with ESMTP id 25856A000B for ; Tue, 8 Apr 2025 17:02:55 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=infradead.org header.s=casper.20170209 header.b="pNvxRd/r"; dmarc=none; spf=none (imf25.hostedemail.com: domain of willy@infradead.org has no SPF policy when checking 90.155.50.34) smtp.mailfrom=willy@infradead.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1744131776; a=rsa-sha256; cv=none; b=6a1yWD3l/fFh3ZzEEVda2BOUBCfuwQdXx3jByVKOFrHZJizukHajkYw8T3dRDNgRuYz2US hvOmBbOGuFNIghJO88xsK1uV99qYBVkAGB7yvJoP+ou7xvyP3ZjEtFCQ8raPt/t/Lo4aOT aoyFCm9gOY5s2AcGgRdGSXKU9ixxmbY= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=infradead.org header.s=casper.20170209 header.b="pNvxRd/r"; dmarc=none; spf=none (imf25.hostedemail.com: domain of willy@infradead.org has no SPF policy when checking 90.155.50.34) smtp.mailfrom=willy@infradead.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1744131776; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=Wthvw+g3VPjsBqYkn9PtU805EB50LUzQbJZB+kkRP04=; b=VNj9sX7bRKV8shsPIU2dGz8RM/CTRBLI/lmc86nniijTSLSvapE3BBeoNSyQh1Pxsqnacz OWpLGFEsS6HuyE8uqChtCHrR2FSmNop37avChwqsSbwQ1So1dQAuXpR3L4/k3DOeROZgr+ h+uDmsGSVxxn0H24l3rsJsjMDWUI6N0= DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=casper.20170209; h=In-Reply-To:Content-Type:MIME-Version: References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=Wthvw+g3VPjsBqYkn9PtU805EB50LUzQbJZB+kkRP04=; b=pNvxRd/rFKeuHejFP1UqBVVtJu wMFhn1znqYKaW/mLFjcM8+qpr5O392zgVI00cx12Ur6Rp6K+DE3Mglx/ManTL0g+3uJ6tazndBE2Q ew7Yo8AXeN7BLV0RSw5TffIiB7mEF5f85jPFWjjmwogHsITM7S0mLtBrcZ8KjM3lXoqusTb3DwK6O ilicc3T2BPad5dHtMSYfolaqiX+dTMYFNykY1BKO/mtvqVhauIS29BvQOsZYvkOE7B1Jt4NTyTv3c RZ/31JCEQI2IWe9u16RVO32pOAUC6PsWLXiEJfi5qWNVZGFSjqM+xQwfvOVsd1veTRO6VvjGX8sUs IQ+9PECA==; Received: from willy by casper.infradead.org with local (Exim 4.98.1 #2 (Red Hat Linux)) id 1u2CKR-000000000Fo-0n3G; Tue, 08 Apr 2025 17:01:39 +0000 Date: Tue, 8 Apr 2025 18:01:39 +0100 From: Matthew Wilcox To: "Christoph Lameter (Ampere)" Cc: Mathieu Desnoyers , Sweet Tea Dorminy , Mateusz Guzik , linux-kernel@vger.kernel.org, Andrew Morton , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , Johannes Weiner , Lorenzo Stoakes , "Liam R . Howlett" , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , linux-mm@kvack.org, linux-trace-kernel@vger.kernel.org, Yu Zhao , Roman Gushchin Subject: Re: [RFC PATCH v2] Introduce Hierarchical Per-CPU Counters Message-ID: References: <20250408160508.991738-1-mathieu.desnoyers@efficios.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 25856A000B X-Stat-Signature: d6j5j71wnb4pd3h1kqhobgjo7qf7k14j X-Rspam-User: X-HE-Tag: 1744131775-807713 X-HE-Meta: U2FsdGVkX18dAVaDmOpkvnbzNz/tGw8aAnTafdnuOO7OQBnh6H1r5JZWxv59SeSMItaHpWh4rjd04ZY4nYoesohFkCqFAkBkMC3pY6uNL8OHF3bpyXAd8T/iP+4ZhXh73GGAUn/blflF13Yw51pWCR+a2jyklrSXNg7+ron3hKgkOiI8I3v/znkkfO/38pCFBk+CNEkzXFh13ctXJIdkb8DPslGQEeFzy1i1lSlbDRYhLnb+s3BLTIVmaXalCNAIuSZz4qBB2DIcgoXVJXQR5GKtjg4E6DrR12Q1342y6Yv+WDJoDn0q9JrpU2ntpy4Uph/374x3MSN0se/maKy+eRIqRt6YGQppfoJgFX3/2ddSsZgAqsb74bhyazjbEftT0YsKf8Sr4gc+nIYwoK1GubWaV2tIwN6uaw8xl5oFc+D+qCBjfgAwoE1o/KYzac3hCJxpU9ixvxR6Zmbfq0xW4EVk5+Kq5H45ImdskFeUGgkB/kxkKU9hqvyHFdy2U/xS/j2wloS2mmtmP8cbhlpjNSqDyTdMoTnAEVXVHRUZx2YyA+MNhrfsZLZVaPnm1qeVlA7Xhtzi0ROcbyvJVKshwj91/UOWs+YudF5gzvY1OpxeS6rJIWM2i7jevGmr9MqRZBhXA9/nGSlwPFtbaY5WIOSDth9nFUM5I/HcIFuBpJ0I+Igs0R3lsqpj5xHf0LTL9Is8OHu03bhfow6R+9iPRxDNNjfXdyt4Y0botTZPHDKE5cppBYO5o4oyzlmJyilDrx+1AloqoMal4rFW8hV6Vbf2STCY5oW4WhM5MtiUiunFDfyekxxlkvbrDMC4isLZKQXikfWb6Irsq2d669pehN8UwZB2nx4em4BL+7ydMRFSEumi+yrc6CLZeJ4eRj/FeGR0QyefO85uVzQWjnqX4i4V0lM7Y0vjQEMjSrzw2pq5SmtL+QyCvL5jiKJRALnKZMFZxTnIl52UTd++jO4 5OyS3Oah e1kB76O2w5rCfX29NSyAJdtXSUKDylsjBaEoyERwhzKAJRSvbtoZhZzDXCOPXsHoEHLpRMSy2JYT01aYlYjkUoXYu+Rz5Trrnh/oszMUc9bilOHPB6KpHOEE6bOVYPDJLIyEC2htxDp7EMKzs6oN3J0MMeveu+003MRHJF6pHhc/+8WHRAewOLFiX9qHdYqdnsDaQ/GJf0LgHQzYxTxzuCnpkFbCdJ0NVmIZ56a/g78GXYEQPgN662kav16e97SPOONNg+IE5TVq1RipQCASq2hNnhTPu8b621s6T4LhsFsgpwNI= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000001, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Tue, Apr 08, 2025 at 09:37:18AM -0700, Christoph Lameter (Ampere) wrote: > > The hierarchical per-CPU counters propagate a sum approximation through > > a binary tree. When reaching the batch size, the carry is propagated > > through a binary tree which consists of log2(nr_cpu_ids) levels. The > > batch size for each level is twice the batch size of the prior level. > > A binary tree? Could we do this N-way? Otherwise the tree will be 8 levels > on a 512 cpu machine. Given the inflation of the number of cpus this > scheme better work up to 8K cpus. I find that a fan-out somewhere between 8 and 16 works well in practice. log16(512) gives a 3 level tree as does a log8 tree. log16(8192) is a 4 level tree whereas log8(8192) is a 5 level tree. Not a big difference either way. Somebody was trying to persuade me that a new tree type that maintained additional information at each level of the tree to make some operations log(log(N)) would be a better idea than a B-tree that is log(N). I countered that a wider tree made the argument unsound at any size tree up to 100k. And we don't tend to have _that_ many objects in a data structure inside the kernel. ceil(log14(100,000)) = 5 ceil(log2(log2(100,000))) = 5 at a million, there's actually a gap, 6 vs 5. But constant factors become a much larger factor than scalability arguments at that point.