From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from SJ2PR03CU001.outbound.protection.outlook.com (mail-westusazon11012024.outbound.protection.outlook.com [52.101.43.24]) (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 E342D361657 for ; Wed, 13 May 2026 05:29:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=fail smtp.client-ip=52.101.43.24 ARC-Seal:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778650191; cv=fail; b=X/6rTOsn6W1WqmDa6j9SRcaQHDtrfDRmQNZywM7UkltbcN9ITkVsQvBtbh9/+pAtFSndabHlKMVSp5/d9HsXgmBx+o1fdd5mNOTH7boQbpNMpm2nELzPWbcaCOzwTseZefz2tc1ymYsvfC6Hf7r3zfw/Qe/1w8a2J9URzAgkvxg= ARC-Message-Signature:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778650191; c=relaxed/simple; bh=M1tn/xDIWnlB8G+akfgdIGPtgjhwUh3Qv7l2tPusktw=; h=Message-ID:Date:MIME-Version:Subject:To:References:From: In-Reply-To:Content-Type; b=EyNYiQj2PxKbvfBu9qTCLOVeqaaDqCvxoITcIq4Y4RAwonRFTpMt1WI/r3dDaXdXs/A3agPksHAa5yCdnLox9f6JuQ3cuSvymRL8v2RKZxqyMnusdxsMvNz7OtcWO8G8596FP3YdkPRLiKc+1rDstkMcYvRmlLtdLy7ioEreGeQ= 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=K/cGjhxO; arc=fail smtp.client-ip=52.101.43.24 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="K/cGjhxO" ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=BYG0pJQhoGR+wvjFDfN+3UKXbco8c6L311twtNczmh7h/DuDXHAD+hQiJJHcFc8eM2Qdx8z/iNi4r/EIrhIC4OKiTKV7aDIDdGhW5rEgSZvX4Sdg+nOn5kfeZk9R+C6uMAvS8etVRMgG2vRKJvog1svJkzIoZTTsz4dM3GR6DD3vAOO9SfQSQ1l7JwKGy+40+SumvVUGAxpe6zLDnrtwX2PxioU0G/JinP612IP4X8Znlm2cOAtBXuW7h68kPZ6TP2WZnEa/BRyh3LltiPQIbgyWc56ewcLaQdyjR1U6HX7F2nBn5ybfknrzZzIMCD3rjf0lKZae0kedle0w+qsxxQ== 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=99O25lfoLe/q/Hkwli0DL90Q9sSUYrcofJoLU9jP018=; b=YZhJeHrFy04S3CtXsc1NdnfliTkOOIrVQlt49slOo/vIhjmbFoTRck7J/f2mkg3fqzYlHV9V1OUQPghiFydD0BtYi0d3pBA50UpMKPx6pe2TuccoaMI9ZiqbG8UTZYdqIjZGVWADICRWHGl/lcrItteI1vLHTMQfOiMu61jQQHM5+lW+PWFJewdkMhfGiFxOVYStllNS9Et5qe21KXpZq4i+MuYgHhEXBdaUts3lbdbjS6qgaHTjGD/yB9TuR6GIQ9M/A0iT57ksP/QbaVdlrFVrYhdQAPJ5fsLjOV/JG70St+Ih4uCxYM/AwgKOCmLuwbeahzA+n9zH9ANZkhM2sw== 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=99O25lfoLe/q/Hkwli0DL90Q9sSUYrcofJoLU9jP018=; b=K/cGjhxOxZutZfbzI8BKB6aUCJot+AmOv0Vi1FYeQm9uL7Eh/7Guxv4iDaydJyXHR8YMLCdpbtEsvVN20hnzHQmbd4l0R/3FH+fDiw1TRD5xidHryNt4fE1BnLGWT65X6FIyGeaF+0mfAulD18rd1c5p5XlqKC7h9pzuoemHeDg= Received: from BY3PR10CA0021.namprd10.prod.outlook.com (2603:10b6:a03:255::26) by PH0PR12MB5679.namprd12.prod.outlook.com (2603:10b6:510:14f::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.9891.23; Wed, 13 May 2026 05:29:46 +0000 Received: from SJ1PEPF000026C5.namprd04.prod.outlook.com (2603:10b6:a03:255:cafe::fb) by BY3PR10CA0021.outlook.office365.com (2603:10b6:a03:255::26) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.9891.23 via Frontend Transport; Wed, 13 May 2026 05:29:45 +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 SJ1PEPF000026C5.mail.protection.outlook.com (10.167.244.102) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.21.25.13 via Frontend Transport; Wed, 13 May 2026 05:29:45 +0000 Received: from satlexmb10.amd.com (10.181.42.219) 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.41; Wed, 13 May 2026 00:29:45 -0500 Received: from satlexmb08.amd.com (10.181.42.217) by satlexmb10.amd.com (10.181.42.219) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.2562.41; Wed, 13 May 2026 00:29:45 -0500 Received: from [172.31.184.125] (10.180.168.240) by satlexmb08.amd.com (10.181.42.217) with Microsoft SMTP Server id 15.2.2562.41 via Frontend Transport; Wed, 13 May 2026 00:29:40 -0500 Message-ID: Date: Wed, 13 May 2026 10:59:39 +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] sched/fair: Replace random newidle_balance with Bresenham accumulator To: Qing Wang , Ingo Molnar , "Peter Zijlstra" , Juri Lelli , "Vincent Guittot" , Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , Valentin Schneider , Li Chen , References: <20260429085147.1029505-1-wangqing7171@gmail.com> <20260506024455.2799069-1-wangqing7171@gmail.com> Content-Language: en-US From: K Prateek Nayak In-Reply-To: <20260506024455.2799069-1-wangqing7171@gmail.com> Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SJ1PEPF000026C5:EE_|PH0PR12MB5679:EE_ X-MS-Office365-Filtering-Correlation-Id: 21d7bb79-0948-48b4-8272-08deb0b0a4d7 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0;ARA:13230040|376014|7416014|82310400026|1800799024|36860700016|22082099003|56012099003|18002099003|921020|11063799003; X-Microsoft-Antispam-Message-Info: aq+g7O4XwX41qs5eWyprAolUehsjSqGsPUGDaJ4xLwdBLKDJQ/Th88YQUJoatg93UUMWDuV3XIwQDToXHayJ/sRTiUVOrVaTE5PbjoV5IOoy5/aqV88/0P0ONiA7GIkGYEOgUFs3Y4Zu5FMqkqJAbUFEj8L6wsvXTvAw2DH5Un5S6p3cHWzdASsa1+s3fQymLrOR0hl8RBDoP2FG7L4bTwtMHNCq6yaCS5hfdHm/9vF2pARzAnPLONqBukUt85qfaPX8zdyzqTXtgVphCUYbDV7zwy5dt3A5Ixac0MY+bw1kxVm8wi4XuoZnSfIUJCQW5b1u2kdf8y0PYTlj7FYSdLpBQ3uvoRMAtuu1EmpSttmyMqrdtp4QoSIlWW5VVoNaGbYuZfNBOb7eVpCktDV1MyIHXNHPALaj5c99zWly8/l/7CVYRz4ZXTee+z+gX5pnYGbBwAiRMc2oc16dTPi1MDxfRgYQkV67ZpQhDs2Nz9iJdXUePIIuUrTJhIkPRmPHu03lk58bdkjSP6mcRu9HhtuuFxX/8wbK+tuKpuLm7a8Fo/YzFRTP1vnY5KjM9Um7pIeM90Yvv9BgMbzPR+RZpTw+3+PucJpmYm4kDSUILxsUmSWSm9hIUm3cFkk3f4R7yDjqHymTuDCtQADnrMoFWSQ1dBTLyMd2e5682Zu8C9U6jJSbOoX0MJojWmqXfgi1RydIMqzKFIIkhBEGAl1TSxPco4W3DCuGaSqqa4iE6K02PI2mkoZD3f2jxr3n+CdvHF8JHzae/+CSFzjup74nAw== 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)(376014)(7416014)(82310400026)(1800799024)(36860700016)(22082099003)(56012099003)(18002099003)(921020)(11063799003);DIR:OUT;SFP:1101; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: LzmMaZEWGAe4nzTOiZys/2qxgxQs2oI3aMKrodApoobB3FjFMcKGQlBZ9cylWDl7GhXra2QyPvHHD6vchwW58t+ceJbVLZt/uxVg96mc0YXCNYC4DlSYT6KkcudMg4sV43C1SR4VVSIscA8WrLWh99nOhL5vrPrJ8SohD68wmVQLha+Xp0UCzNuVrGNDE15vcrHOl95okuNwPRmR8tCG3RtnQc4+7my+ORRE5jL2sdx9ixd3whE2OAFULyBO/l6zBpT7Es/JGH+pLuu43vNnB/KUJnil99x+Qd2/KELZGhpBBLr67zYC4/Gh/Ej4hqyJU9+mqhRMbIB3LO7sPMXDDn7e81RElbNpzEFNCkUvDm4EPpGwzFwkkuSwOFv9TKoj34RDKfvmSu3YzqRuL48yGLp1GMyOwO9l+fp9WiR5Bc3WKmonm6hps5s2pVOgjE28 X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 13 May 2026 05:29:45.8737 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 21d7bb79-0948-48b4-8272-08deb0b0a4d7 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: SJ1PEPF000026C5.namprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH0PR12MB5679 Hello Qing, On 5/6/2026 8:14 AM, Qing Wang wrote: > The current NI_RANDOM implementation uses a random dice roll to allow > newidle_balance attempts according to the success rate. There is a better > way to implememte it. > > Replace the random dice with a Bresenham accumulator that distributes the > allowed attempts with uniformly spaced evenly across a 1024-step window: > > Each step do those: > - Accumulate (1 + newidle_ratio) into newidle_window_pos. > - If the accumulator reaches 1024, allow the balance attempt and > subtract 1024. > > This guarantees exactly (1 + newidle_ratio) newidle_balance per 1024 steps > and per newidle_balance with uniformly spaced for any ratio in [0, 1023]. I took the most sensitive workload I have for newidle balance (tbench) and took it for a spin with these changes. Following are the results: Clients: tip bresenham_accm 1 321.65 (0.00 pct) 313.97 (-2.38 pct) 2 641.92 (0.00 pct) 638.74 (-0.49 pct) 4 1245.65 (0.00 pct) 1237.26 (-0.67 pct) 8 2435.80 (0.00 pct) 2442.23 ( 0.26 pct) 16 4717.66 (0.00 pct) 4688.19 (-0.62 pct) 32 9303.53 (0.00 pct) 9390.71 ( 0.93 pct) 64 18002.57 (0.00 pct) 17911.56 (-0.50 pct) 128 27729.26 (0.00 pct) 27621.95 (-0.38 pct) 256 47134.77 (0.00 pct) 46137.36 (-2.11 pct) 512 43179.41 (0.00 pct) 43277.53 ( 0.22 pct) 1024 40339.30 (0.00 pct) 40176.49 (-0.40 pct) The %diff is in noise range which is a good indication that there shouldn't be any surprises. I'll queue a run overnight to see if there are other benchmarks that like / dislike these changes. I'll let Peter comment on the change itself since he knows these bits best ;-) -- Thanks and Regards, Prateek