From nobody Tue Dec 23 14:22:19 2025 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E434913C8F3 for ; Mon, 13 Jan 2025 04:10:16 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736741418; cv=none; b=UXwJ6H2i07Qpwk+znlntYc9IQUnvZt0o3fwgW60niRwGJ+if9MUldAUpFTmW9aVIbwOSPSS7Bw089GnDC8yN0zCzfQP/a2W0AD0u5vww5wb/SE8dwM/3Ml/LWGa8SwSf4fnH+8EtE5Ailwmg2F06A74brF7Ss7bcLtbIVW+6qig= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736741418; c=relaxed/simple; bh=PH543vEZJlnKbAgQLWBSqsyUdPU8zT8FsczMdSMkjOg=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=arCKPZKtrZj94ilJW7x2I7OApiiZ6xC/CsxUGMV0H8kiWKdKMUJoc4Cyh0yiWbtnyW+cknMRlkQEvA7F3IcKOEuB4gBRnu24eVmj1be2soq1+jYUNr5yvWVJdOHZdC037lFfSwSgarMgCVmHMkE6RjxT1DGF8Q0teDHFrcG5784= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=dkKgmnxA; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="dkKgmnxA" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-2161eb94cceso45071275ad.2 for ; Sun, 12 Jan 2025 20:10:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1736741416; x=1737346216; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=hzE3KvO1Rm/WqDk5yY7hOQsGeqfFPOD4sOQSI7ARCAI=; b=dkKgmnxA+7LcqtqwHExyJaI20I3PycoQTR16jOSCisvsd57CO+eaQqmHdeiZXjtpqE 8k/9210ELISiCL7Q+NIhFuYTbpPmTu+7Wqq6SnXBmdF/OeaG3rsb7LC1sZ3SS2bblaMA g4ej6OHaA0eHsSb/60FmAioBGG5qZf+4dGYLV7lcrrs0DjS8hGTakwZBgo0EkHkHqGcr rgZEC7y1nzZ1xL7jras1nD2nL1ObxvWhRmFi2Vdca38ITEjmC3Z6mALLGy5T+px/BlC2 yc8C6GSRkX4B/J3BZoUAd3SCbu2axunUTnbxl3Co+bT9qV+e+vxwY2gjZ0j++h9GlFTC EGnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1736741416; x=1737346216; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=hzE3KvO1Rm/WqDk5yY7hOQsGeqfFPOD4sOQSI7ARCAI=; b=b5hBcvkB0IAp3cVaiuHXpAL806glFRDyxZp/pE+em5sJ+ytOkv09+YfWEsEQHzsfJ7 Ye5s5hf9mYMgrEu+jq6gkojYEF/m29+ZFQteYLKxgG0LQ1qhK9l1Wdau8/+wPYyplVDb /1jMgbI9MAC6QKP6deaI+x88TIF7CwpD0w5W+JQT1yT+bvG557XFsXnJ2fz1s6+0ryoK 2pPZq8fu0Si/yC9ZL+voWroYqD/6yxsbcRS37hnkHcpOHqaRZsSeFQ4Z9kFhSR2tWgcC J6Zw7YNAHdCNL2cSjZlFfpXiQPRLF/dq7krWOqH5SnDTzTKKIeGiK/ZrvybNv71EwVg0 l+sA== X-Forwarded-Encrypted: i=1; AJvYcCXoe397IQatB6c0hMpfQrZiduScNGMynXtK53jl2wbRMEhuiBHUKJ5FszEMn1nhYiT7Yor0TiFbIja4x9s=@vger.kernel.org X-Gm-Message-State: AOJu0YzBksuRZzqYUe/L7+gKpVac90W3HJeu3N7PPvki8TZKfiLlKIJQ V8qDmAkGtKZnyZvBp+7EnAMOWd2aWvSA5xY3n4wMA0yVVVbp1v1h X-Gm-Gg: ASbGncvG5JQFZaib5sV5w9lf6bqndhSP3JryRwwVtBy/69BDaLzekyX9yd2sV7CJhrr y8cIVYImgjN+/WxTGQkUuWhRJYKAzF4d5KpAnmAfjVVP9Vn2D8ZAisEp9fEbzTie3jTG0cg62iV RsJbsX5UOvCMlxB9U+EknNU8DnBaVwh4G1Ja7SL2leJXAIEBABjDIlqRmnifK/9bWklWOVG8dmC QUTnvQeB3wRRhDQ0gQYT5FR7ctGP0FP7j8KKHk/UJvphvxTGmtoT68R69V/yttZcQ0Y/n5YlLy0 X-Google-Smtp-Source: AGHT+IGGpK+4cQFPIQDfCA/HcXmX+1BUGGZa7qkBE/fy7H0jjAK5+J63tMGZqzddl3c2qflmcRhaCQ== X-Received: by 2002:a05:6a00:6f0b:b0:728:cd4f:d5d7 with SMTP id d2e1a72fcca58-72d21e09259mr27325059b3a.0.1736741416024; Sun, 12 Jan 2025 20:10:16 -0800 (PST) Received: from vaxr-BM6660-BM6360.. ([2001:288:7001:2703:ed7e:d523:ad1d:dd48]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72d40658b1csm4923984b3a.115.2025.01.12.20.10.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 12 Jan 2025 20:10:15 -0800 (PST) From: I Hsin Cheng To: mingo@redhat.com Cc: peterz@infradead.org, juri.lelli@redhat.com, vincent.guittot@linaro.org, dietmar.eggemann@arm.com, rostedt@goodmis.org, bsegall@google.com, mgorman@suse.de, vschneid@redhat.com, nysal@linux.ibm.com, jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, I Hsin Cheng Subject: [PATCH] sched/fair: Refactor can_migrate_task() to elimate looping Date: Mon, 13 Jan 2025 12:10:08 +0800 Message-ID: <20250113041008.6341-1-richard120310@gmail.com> X-Mailer: git-send-email 2.43.0 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The function "can_migrate_task()" utilize "for_each_cpu_and" with a "if" statement inside to find the destination cpu. It's the same logic to find the first set bit of the result of the bitwise-AND of "env->dst_grpmask", "env->cpus" and "p->cpus_ptr". Refactor it by using "cpumask_first_and_and()" to perform bitwise-AND for "env->dst_grpmask", "env->cpus" and "p->cpus_ptr" and pick the first cpu within the intersection as the destination cpu, so we can elimate the need of looping and multiple times of branch. After the refactoring this part of the code can speed up from ~115ns to ~54ns, according to the test below. Ran the test for 5 times and the result is showned in the following table, and the test script is paste in next section. ------------------------------------------------------- |Old method| 130| 118| 115| 109| 106| avg ~115ns| ------------------------------------------------------- |New method| 58| 55| 54| 48| 55| avg ~54ns| ------------------------------------------------------- v1 -> v2: - Use cpumask_first_and_and() - Remove additional cpumask Signed-off-by: I Hsin Cheng --- Test is done on Linux 6.9.0-0-generic x86_64 with Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz Test is executed in the form of kernel module. Test script: int init_module(void) { struct cpumask cur_mask, custom_mask; struct task_struct *p =3D current; int cpu, cpu1 =3D nr_cpu_ids, cpu2 =3D nr_cpu_ids; unsigned tmp =3D 0; cpumask_copy(&cur_mask, cpu_online_mask); /* Self-implemented function, didn't paste here because the length */ generate_random_cpumask(&custom_mask); ktime_t start_1 =3D ktime_get(); for_each_cpu_and(cpu, &cur_mask, &custom_mask) { if (cpumask_test_cpu(cpu, p->cpus_ptr)) { /* imitate load balance operation */ tmp |=3D 0x01010101; cpu1 =3D cpu; break; } } ktime_t end_1 =3D ktime_get(); ktime_t start_2 =3D ktime_get(); cpu =3D cpumask_first_and_and(&cur_mask, &custom_mask, p->cpus_ptr); if (cpu < nr_cpu_ids) { /* imitate load balance operation */ tmp |=3D 0x01010101; cpu2 =3D cpu; } ktime_t end_2 =3D ktime_get(); if (cpu1 !=3D cpu2) { pr_err("Failed Assertion, cpu1 =3D %d, cpu2 =3D %d\n", cpu1, cpu2); return 0; } pr_info("Old method spend time : %lld\n", ktime_to_ns(end_1 - start_1)); pr_info("New method spend time : %lld\n", ktime_to_ns(end_2 - start_2)); return 0; } --- kernel/sched/fair.c | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 2d16c8545..d49960d50 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -9404,12 +9404,11 @@ int can_migrate_task(struct task_struct *p, struct = lb_env *env) return 0; =20 /* Prevent to re-select dst_cpu via env's CPUs: */ - for_each_cpu_and(cpu, env->dst_grpmask, env->cpus) { - if (cpumask_test_cpu(cpu, p->cpus_ptr)) { - env->flags |=3D LBF_DST_PINNED; - env->new_dst_cpu =3D cpu; - break; - } + cpu =3D cpumask_first_and_and(env->dst_grpmask, env->cpus, p->cpus_ptr); + + if (cpu < nr_cpu_ids) { + env->flags |=3D LBF_DST_PINNED; + env->new_dst_cpu =3D cpu; } =20 return 0; --=20 2.43.0