From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from BL0PR03CU003.outbound.protection.outlook.com (mail-eastusazon11012037.outbound.protection.outlook.com [52.101.53.37]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CD8FA2F5A13 for ; Fri, 23 Jan 2026 03:10:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=fail smtp.client-ip=52.101.53.37 ARC-Seal:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769137862; cv=fail; b=gKRHGU1qyM66b6DBKR+K2SHWQB6HZa4F2kfEPbiu2Uc9UQDdfq97divxPt7X18ynUCPsik80DdhHhleMYdHxc5tsfYVXY+rcQPY573PUtU7U3PjcQ0JN8xcR46Q8ZG8oOYAQCFUz4w55dam86RGp/fkuyd7HkMUNjS2wpRZc6ms= ARC-Message-Signature:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769137862; c=relaxed/simple; bh=uQl551SiRDuRRKCMUbq7TUUz+UpFM7J1CHIV8/s24p0=; h=Message-ID:Date:MIME-Version:Subject:To:CC:References:From: In-Reply-To:Content-Type; b=iE/ra/l9alkgJwbjvxoWbhKmdWmGNaMWCZFFW7QWPns314eOCh3q4DgM6HnNzWWSLkigj3VDM/SEwr2vf+o59sq6HbpybGlrcd5ntrPoCOqo5oA+omBwo0gzWHTtuRWbs2AqhxUGluOPili1y+y1j8rQbimcaHWr2YDMLQcF1lw= ARC-Authentication-Results:i=2; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=amd.com; spf=fail smtp.mailfrom=amd.com; dkim=pass (1024-bit key) header.d=amd.com header.i=@amd.com header.b=x5PFwKEk; arc=fail smtp.client-ip=52.101.53.37 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=amd.com Authentication-Results: smtp.subspace.kernel.org; spf=fail smtp.mailfrom=amd.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=amd.com header.i=@amd.com header.b="x5PFwKEk" ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=BQNJN4SxkAQYdnToXZ8PXeDm4yKfnAWEDktZwCwY0TEE6J8Yr/XzyMAUF+wxUykkVOOuGfdJV2RQyHPUJM0BL//YvtP9LR0aewx6AXkPKHePxgPrwaMY87nxG2L0jQ8wX6GF+HkyiNTKmRQ4wcblzaZbLarO9JzhfM9CR4EmGYmgOeKwtUQivJlwhFBB5Ln61E6BrXjujGUYODvzZCWSPnrCWjo3rGwVaqdaI75VKTG/4nkuyNmgh/nHnN+nPFhj1hTJS9UDpJOCpHEfAI+q7yM7UWmT5khf1ZrNXUaLNWT24Q/grn0ZTIJOR15Vg5ovlbdJuHp3K1gNNEg1Y6Otew== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=65oLA43Tn+xn8hqenjN5gaLd9ntp4ST0IUvE3v9bToo=; b=CS1UKJw91lC45Yni7calU+XbB5Og+qnOr3aYcpbAizYcFv0FoSo6QnJIZoo9bjwxsIaa5wNNJYYRfAfyJFo0KvOd2UesW2XxZABuZQs9uy9EGDSeDYvh8PIPTncnT4pC0skqj8iw8MhAjF6EagiY6LFF1esk33/bp0b7lLRP2Cf9X0RyeYdXbsz5DN33qSpkFkrS0GioTVxQpbuo8akPwj8sVInsSSOastM7+1BK2JwgzJ2TbmSr9TGwRWf2GOVWibAFC4wGE5Gk1v2G0xLFPvZFi9x5H0OG+IyEu3xzBsmhgumQZRJRYVY+slxoUVI4ZbgCYCLl3vhD0YilCby4Dw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 165.204.84.17) smtp.rcpttodomain=gmail.com smtp.mailfrom=amd.com; dmarc=pass (p=quarantine sp=quarantine pct=100) action=none header.from=amd.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amd.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=65oLA43Tn+xn8hqenjN5gaLd9ntp4ST0IUvE3v9bToo=; b=x5PFwKEkaHqgnV3n/9g1mKpVK68BLXRarfYTyWg1SYVIUwe4Q/N6aaHywHNxJuXbm1ocwb0SFbTselxZY78ccFROHg2vfy49SGvJH6Z7MruoFKYxbCgFW4K5+fB0zTMHp/U5E+iFJ6oVnaBoknhcrgmYGa6+IDk/MSISn8ldiis= Received: from SJ0PR13CA0239.namprd13.prod.outlook.com (2603:10b6:a03:2c1::34) by LV2PR12MB999096.namprd12.prod.outlook.com (2603:10b6:408:353::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.9542.10; Fri, 23 Jan 2026 03:10:42 +0000 Received: from SJ1PEPF000026CA.namprd04.prod.outlook.com (2603:10b6:a03:2c1:cafe::eb) by SJ0PR13CA0239.outlook.office365.com (2603:10b6:a03:2c1::34) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.9564.3 via Frontend Transport; Fri, 23 Jan 2026 03:10:29 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 165.204.84.17) smtp.mailfrom=amd.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=amd.com; Received-SPF: Pass (protection.outlook.com: domain of amd.com designates 165.204.84.17 as permitted sender) receiver=protection.outlook.com; client-ip=165.204.84.17; helo=satlexmb07.amd.com; pr=C Received: from satlexmb07.amd.com (165.204.84.17) by SJ1PEPF000026CA.mail.protection.outlook.com (10.167.244.107) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.9564.3 via Frontend Transport; Fri, 23 Jan 2026 03:10:41 +0000 Received: from satlexmb07.amd.com (10.181.42.216) by satlexmb07.amd.com (10.181.42.216) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.2562.17; Thu, 22 Jan 2026 21:10:41 -0600 Received: from [10.136.37.139] (10.180.168.240) by satlexmb07.amd.com (10.181.42.216) with Microsoft SMTP Server id 15.2.2562.17 via Frontend Transport; Thu, 22 Jan 2026 19:10:38 -0800 Message-ID: Date: Fri, 23 Jan 2026 08:40:37 +0530 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v2] sched/fair: Cache NUMA node statistics to avoid O(N) scanning To: Qiliang Yuan , , , CC: , , , , , , , Qiliang Yuan References: <20260122161647.142704-1-realwujing@gmail.com> <20260123013933.195263-1-realwujing@gmail.com> Content-Language: en-US From: K Prateek Nayak In-Reply-To: <20260123013933.195263-1-realwujing@gmail.com> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SJ1PEPF000026CA:EE_|LV2PR12MB999096:EE_ X-MS-Office365-Filtering-Correlation-Id: af12bd96-e373-44b0-53ae-08de5a2cfdef X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0;ARA:13230040|7416014|36860700013|1800799024|376014|82310400026|7053199007; X-Microsoft-Antispam-Message-Info: =?utf-8?B?eWJiWmdvb2JLNWs4WUZESXV6OWhSMlV0ZFMrVzFMNlZJZGYxbEVCV04vRmxN?= =?utf-8?B?dVNNTnloRHBaZWR6MDVLNjJNcDZEY0MvYkIrL1RQV3lTY0xSNlAyU2dTVGhk?= =?utf-8?B?YUkxUVErcUR2WUoxby9adFk2RnZhMTZTdVVKaHRndXNzbEIxZU9ZalNBSEsx?= =?utf-8?B?dXAxQlJtUE9tRGZEUU5oV2w0bnRHOWlCdE5RdFRrK2pFT2ExSVNsTzlFY0da?= =?utf-8?B?U3lETVFVRXhLemorM2Fnc0VlZE5iMGJXWkxmNGU2Rld0NXcvaTRWUW91aVBP?= =?utf-8?B?OUZvZDc4Q3dFaW5QQ0phdFRjbUtWOEd1T1lDTDh0UzZ2UVhRZk5pcHpMZG1Q?= =?utf-8?B?QTd1SVhTSGJZS1pnUFBjbjBVUzViMnFJWG1abng2dnIvanB3QWZkYUFFOWRE?= =?utf-8?B?SEZXazFkQmdPZGJlQ3RIcFZBamxLQnpIV0dLYUJ5ODIzeDY0T2RSTTZVcUJr?= =?utf-8?B?YVp1SFVucXlwM0tYV0RzeFNDbEtrdnhDQ25iYnQyQTAzSk1PTGtVNXF3aWlw?= =?utf-8?B?MDBpY25iY29YTkdWZm4wMmJZNXVIWmVxUk43SWFMTEMrSStKZkFtWUNIN1dN?= =?utf-8?B?ekdrVDBFdUE3aTZqaWhUM2piYkpPTmFrVU5uYkV1T1QyTk5WQ0MrS1RLUE12?= =?utf-8?B?Q0hoc3R4NjRtbVVjajhoa2M0emtrajVPQmFZM2xBZGprK0ZIL0VSV2VxZGNy?= =?utf-8?B?ZllzYnFOVkpDSG1FUnlIcFg0aGgxUXRXVXl6Nk1wck5jcVJYazBUZDZNNkly?= =?utf-8?B?VEpXdXRFTTNvZWlGemtOelBwYm15dEFLMTlFS2JBT0s5eVU3eWFLSlA0VTJ4?= =?utf-8?B?REY3K2RsUTh1RjhaWTk4dlZKUFc2bXlheG1XbkI1cjlYazJkeGU0ZkJRamYz?= =?utf-8?B?V1U0OVhDWlh3a01rMklpRW1kYTNhQUUvSXI5UzR0bjJROHU3TWVvMXpxd3Nx?= =?utf-8?B?MSs0TGxibGdIelI3SDRCaUlzaU8xSC9BM0hDM1pSNkI5cE5yNmRSbXJPUXBw?= =?utf-8?B?eDN3OEFITFlBS0VmRkhGREZ4Yi9TMjZvUzF1N2pOZXd5M212OTBnL21pWjhL?= =?utf-8?B?MjBUSUZRZkF1aUlrOE1JbEF0cFpOSXYvcjFueWJtME5EbzkwVSsvR0h1bEtu?= =?utf-8?B?cXNDN3pUT0grb09YODk3d2lXUk40b0JxQThjMVZvallqWG9QNnJCVTk2R2E0?= =?utf-8?B?MzRYWkJuV2lSOGZCVWE2YUF5c0Q3czNqeGRkNktoVko0aXlJWnkwQmM2SnNy?= =?utf-8?B?bFdodnpEcnBFNk85T0ZmazNhSjg5d0kwQzc4UDZHcGRtSWxYS2JKbmVPSGJi?= =?utf-8?B?Y0VBanVKV3RuN00rUXVjbVRHRGNWVTFrM3hRazk0NXNvTGZwU3lzaDUwa1Q0?= =?utf-8?B?YmtZWmUvUnV0YW1kc2swWVBpWVVRR1NYaFNIYnhiWDR4UGZlbUNhZ3Q5WFpP?= =?utf-8?B?WkkyTC9RdTZKQ1RBam41YzFrZnpOdGEvWEkzT1pUU29zOVgzUkJ5bS9ZQnVP?= =?utf-8?B?WHl5QTE0QWFBaDNSaUZBWHpiakVPbjZPQ0ZBNTBadTVZWkhpeC82dk13a2xZ?= =?utf-8?B?TGtVazhER09UT3FTYU1iM1dmaW9EamNmOVVzdXQyOHUxK0pHR3psK1RrUHpw?= =?utf-8?B?cWZQUG1IZ1lMLzkwY2tINkFiRC9VQlFEMi9oVmJqQXBxUWJqWlY5ODNxSTZK?= =?utf-8?B?UjRZTGlGQ2QzZ2s4MG5pbThoTUNVRThRdHZodzI0Wi9na21yYmdJeTY3UlIy?= =?utf-8?B?RjNtRlVlRDFjOThuLytQZnJ5ZHZkWFRGWm9Xb1ZJcmtSdElYS29sdGpFbU0r?= =?utf-8?B?eERtNXpsZ1ZEWnFaT1pteEtvSE9oVHhJc2JSeW1LZERCa0NualRLM0JVdkFC?= =?utf-8?B?WVA1WEt3LzV1Y0NvZHhMT0lMM2tQODlUc1lJblRtSENnN0w5UW5RZC9zZnJh?= =?utf-8?B?ZTdHMWs2SzVRbWQ5dWxDVnZPMWlxOGNtTUdiNk94aU5KY1dFYUFDQTRhbU9T?= =?utf-8?B?TUp6ejJZVG5mY0lxM010cmY5Nks2V1JrTEJZbXFkOFprbFNEYUdTVDgzN3R2?= =?utf-8?B?aDhqSVFrVGtGQlIzMGI0bk9qM0MrN2RqK1pMVi9Vc0kxY1hFYkFEbGlFOWZG?= =?utf-8?B?UkVMcUI2amg0cTcxTXhha0dCY2tQMXBPdFlzUGRGZXVEU0cxRUZxS2V3UFVn?= =?utf-8?B?bzhobGtzTnpNdng5UHdaMUF5ekw1YnZvVzlwWWl6MG11QWJCbHNKZWlrSm5M?= =?utf-8?B?VEdNN3ZLTVI3Q0l5ZnJNTnlETVhnPT0=?= X-Forefront-Antispam-Report: CIP:165.204.84.17;CTRY:US;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:satlexmb07.amd.com;PTR:InfoDomainNonexistent;CAT:NONE;SFS:(13230040)(7416014)(36860700013)(1800799024)(376014)(82310400026)(7053199007);DIR:OUT;SFP:1101; X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 23 Jan 2026 03:10:41.7223 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: af12bd96-e373-44b0-53ae-08de5a2cfdef X-MS-Exchange-CrossTenant-Id: 3dd8961f-e488-4e60-8e11-a82d994e183d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=3dd8961f-e488-4e60-8e11-a82d994e183d;Ip=[165.204.84.17];Helo=[satlexmb07.amd.com] X-MS-Exchange-CrossTenant-AuthSource: SJ1PEPF000026CA.namprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: LV2PR12MB999096 Hello Qiliang, On 1/23/2026 7:09 AM, Qiliang Yuan wrote: > Optimize update_numa_stats() by leveraging pre-calculated group > statistics from the load balancer hierarchy. This reduces the complexity > of NUMA balancing overhead from O(CPUs_per_node) to O(1) in the hot path Is it a hot-path? How much of a difference does this make? Some benchmark numbers to support this would be good. > when stats are fresh. > > Signed-off-by: Qiliang Yuan > Signed-off-by: Qiliang Yuan > --- > kernel/sched/fair.c | 35 +++++++++++++++++++++++++++++++++++ > kernel/sched/sched.h | 7 +++++++ > 2 files changed, 42 insertions(+) > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c > index e71302282671..dc46262bd227 100644 > --- a/kernel/sched/fair.c > +++ b/kernel/sched/fair.c > @@ -2099,11 +2099,36 @@ static void update_numa_stats(struct task_numa_env *env, > bool find_idle) > { > int cpu, idle_core = -1; > + struct sched_domain *sd; > + struct sched_group *sg; > > memset(ns, 0, sizeof(*ns)); > ns->idle_cpu = -1; > > rcu_read_lock(); > + /* Algorithmic Optimization: Avoid O(N) scan by using cached stats from load balancer */ > + sd = rcu_dereference(per_cpu(sd_numa, env->src_cpu)); > + if (sd && !find_idle) { > + sg = sd->groups; The first group is always the local group and should contain the CPU you are are looking at. No need for the do-while. > + do { > + /* Check if this group corresponds to the node we are interested in */ > + if (cpumask_test_cpu(cpumask_first(cpumask_of_node(nid)), sched_group_span(sg))) { How often is this true? How much benefit are you seeing from this? > + /* Use cached stats if they are recent enough (e.g. within 10ms) */ > + if (time_before(jiffies, sg->sgc->stats_update + msecs_to_jiffies(10))) { > + ns->load = sg->sgc->load; > + ns->runnable = sg->sgc->runnable; > + ns->util = sg->sgc->util; > + ns->nr_running = sg->sgc->nr_running; > + ns->compute_capacity = sg->sgc->capacity; Nothing protects a parallel updates to these variables from say a newidle balance and you can see some inconsistent state here. > + rcu_read_unlock(); > + goto skip_scan; > + } > + break; > + } > + sg = sg->next; > + } while (sg != sd->groups); > + } > + > for_each_cpu(cpu, cpumask_of_node(nid)) { > struct rq *rq = cpu_rq(cpu); > > @@ -2126,6 +2151,7 @@ static void update_numa_stats(struct task_numa_env *env, > } > rcu_read_unlock(); > > +skip_scan: You can move that label before the unlock and save on that unlock before jump. > ns->weight = cpumask_weight(cpumask_of_node(nid)); > > ns->node_type = numa_classify(env->imbalance_pct, ns); > @@ -10488,6 +10514,15 @@ static inline void update_sg_lb_stats(struct lb_env *env, > if (sgs->group_type == group_overloaded) > sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) / > sgs->group_capacity; > + > + /* Algorithmic Optimization: Cache group stats for O(1) NUMA lookups */ > + if (env->sd->flags & SD_NUMA) { > + group->sgc->nr_running = sgs->sum_h_nr_running; > + group->sgc->load = sgs->group_load; > + group->sgc->util = sgs->group_util; > + group->sgc->runnable = sgs->group_runnable; > + WRITE_ONCE(group->sgc->stats_update, jiffies); Again, nothing protects concurrent updates from newidle context. Is it okay to see some intermediate state at update_numa_stats()? > + } > } > > /** > diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h > index d30cca6870f5..81160790993e 100644 > --- a/kernel/sched/sched.h > +++ b/kernel/sched/sched.h > @@ -2105,6 +2105,13 @@ struct sched_group_capacity { > > int id; > > + /* O(1) NUMA stats cache */ > + unsigned long nr_running; > + unsigned long load; > + unsigned long util; > + unsigned long runnable; > + unsigned long stats_update; > + 40 more bytes that'll only be used by the groups of one SD_NUMA domain. I believe there should be a better way to do this than burdening everyone. > unsigned long cpumask[]; /* Balance mask */ > }; > -- Thanks and Regards, Prateek