From patchwork Wed Nov 15 09:04:54 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: tip-bot2 for Thomas Gleixner X-Patchwork-Id: 165214 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b909:0:b0:403:3b70:6f57 with SMTP id t9csp2412712vqg; Wed, 15 Nov 2023 01:06:24 -0800 (PST) X-Google-Smtp-Source: AGHT+IG/Vx0Bl/ZcPikpbKT3VQrAh+qsr2AeoM2kN3+eSW4Lz+ecM2hFg8NQkmzj+YVCSz+GnSwF X-Received: by 2002:a17:903:2306:b0:1cc:4625:74e2 with SMTP id d6-20020a170903230600b001cc462574e2mr6498227plh.24.1700039183942; Wed, 15 Nov 2023 01:06:23 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1700039183; cv=none; d=google.com; s=arc-20160816; b=K6BuFZ/Z/wHhPYHYi2Iwa7zqQimz1c9yJI05BGxUBRo3LzCKtifBKHdPAKlT9+IL3O BELnH0gRz8yIPlyt6sggX5+udq6zDLtFZ9pqfHyd4gFa2R/9kFspFYH7RWNkVfu035eo pd5XD/y8KEUmp22ICIh5Y/alxs+yULKewBkQHx+VdmJT76MiwKz4k5rTzR4NN+tPuiXg lu3I1I8nMJVOLB7yB75JenJjvCJ43SKRF9PWHsKKK/dU2tuwKnQHE5LSRavTj8hSMpC5 ByaIXR+5UneeLXWXKdgwwc7rbZwrMh24epnGsnoJqb/un/Ys9h0r2KeVipPRmIbE2fDx yRxQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:robot-unsubscribe :robot-id:message-id:mime-version:references:in-reply-to:cc:subject :to:reply-to:sender:from:dkim-signature:dkim-signature:date; bh=/QYSSvUOrr4LCCn0jOmwTPfiYTrF8t+LpJ/wwhjengA=; fh=YIX/3xudK9Lq2PV2FGrJBffVY0XIymHnWmj078pIWkQ=; b=X9alaYaS3F1uF5/NjF7y6jC+70WPZCzRQJW8TC45l7HVdJaQUp5vYDorvU0wO9Cpkz x8sHen/47nhvXA7ezd3CovwLOT7kv7yYFAgJLF3z0rddQrI5BRTGKqHuPVwZ98XaEXoY n+wa5yT9WLEy0PBwC9ai5pFanRu/w6nPKhv3YddqoZghbTmqo4yVOKJdb1d5y4TPMreR R8M8BL/jVJ3NTR3a3RSJbsXZCEx8jYRBpwt+iJgIWZq8QrPp8lcBPOY9ArTaWs0bp4pk wKDCkBXAxPlH8qKGQeHJB/zlefrP8poXq8zpsj7XNhXWd14obQThpQ+S/bu737BcgBD0 edzQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linutronix.de header.s=2020 header.b=HnMEP2yA; dkim=neutral (no key) header.i=@linutronix.de; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.32 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=linutronix.de Received: from agentk.vger.email (agentk.vger.email. [23.128.96.32]) by mx.google.com with ESMTPS id i5-20020a170902cf0500b001c72b13a1cbsi10734810plg.352.2023.11.15.01.06.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 15 Nov 2023 01:06:23 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.32 as permitted sender) client-ip=23.128.96.32; Authentication-Results: mx.google.com; dkim=pass header.i=@linutronix.de header.s=2020 header.b=HnMEP2yA; dkim=neutral (no key) header.i=@linutronix.de; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.32 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=linutronix.de Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by agentk.vger.email (Postfix) with ESMTP id D309780A443C; Wed, 15 Nov 2023 01:06:10 -0800 (PST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.11 at agentk.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234771AbjKOJFP (ORCPT + 28 others); Wed, 15 Nov 2023 04:05:15 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41832 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234709AbjKOJE7 (ORCPT ); Wed, 15 Nov 2023 04:04:59 -0500 Received: from galois.linutronix.de (Galois.linutronix.de [193.142.43.55]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 097D7118; Wed, 15 Nov 2023 01:04:56 -0800 (PST) Date: Wed, 15 Nov 2023 09:04:54 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020; t=1700039094; h=from:from:sender:sender:reply-to: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:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=/QYSSvUOrr4LCCn0jOmwTPfiYTrF8t+LpJ/wwhjengA=; b=HnMEP2yAvdCP2XVOUaS4gJcXDPkXb9STLQW4Rp1YCmMiMg+KaoTU+Ftpbnzort3nsJBPV1 W9S+VnZ/Gy0xzPBaCAsf8yBYFbBLErUhFxRx5de+ad0WAUxRGOvIcRMJzmA0wASgVAS33L iq+Qq5gSxpI9FanKABAVpHp8M99VSnExSIRgyOr92LESnLBSCWLj6/YoEnzOc79wyll2iz qdcfVGv98qc0iw+VUe5+8PFZnFmO2vIEldPB0GjlQK05Dj3CwpyjX7nsb+maNiihwL0rXY YDTKoI6IaVZR3yNYjhl9ybGQO5M36O9ajzJdPxIb03Qo0uQ0ByhdeEML0cao8w== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020e; t=1700039094; h=from:from:sender:sender:reply-to: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:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=/QYSSvUOrr4LCCn0jOmwTPfiYTrF8t+LpJ/wwhjengA=; b=tRToTnKSDv21wezBGC3kFmF1ZuaW1yKHZLJKlvg/4+yUgJbh3fw90PIrVXnr0aScsB31me /Mjo3erfdSojWkAg== From: "tip-bot2 for Abel Wu" Sender: tip-bot2@linutronix.de Reply-to: linux-kernel@vger.kernel.org To: linux-tip-commits@vger.kernel.org Subject: [tip: sched/core] sched/eevdf: O(1) fastpath for task selection Cc: Abel Wu , "Peter Zijlstra (Intel)" , x86@kernel.org, linux-kernel@vger.kernel.org In-Reply-To: <20231115033647.80785-4-wuyun.abel@bytedance.com> References: <20231115033647.80785-4-wuyun.abel@bytedance.com> MIME-Version: 1.0 Message-ID: <170003909401.391.2052507290620204426.tip-bot2@tip-bot2> Robot-ID: Robot-Unsubscribe: Contact to get blacklisted from these emails X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on agentk.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (agentk.vger.email [0.0.0.0]); Wed, 15 Nov 2023 01:06:10 -0800 (PST) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1782599648133019597 X-GMAIL-MSGID: 1782620287438216937 The following commit has been merged into the sched/core branch of tip: Commit-ID: ee4373dc902c0a403dd084b254ce70a78f95466f Gitweb: https://git.kernel.org/tip/ee4373dc902c0a403dd084b254ce70a78f95466f Author: Abel Wu AuthorDate: Wed, 15 Nov 2023 11:36:46 +08:00 Committer: Peter Zijlstra CommitterDate: Wed, 15 Nov 2023 09:57:47 +01:00 sched/eevdf: O(1) fastpath for task selection Since the RB-tree is now sorted by deadline, let's first try the leftmost entity which has the earliest virtual deadline. I've done some benchmarks to see its effectiveness. All the benchmarks are done inside a normal cpu cgroup in a clean environment with cpu turbo disabled, on a dual-CPU Intel Xeon(R) Platinum 8260 with 2 NUMA nodes each of which has 24C/48T. hackbench: process/thread + pipe/socket + 1/2/4/8 groups netperf: TCP/UDP + STREAM/RR + 24/48/72/96/192 threads tbench: loopback 24/48/72/96/192 threads schbench: 1/2/4/8 mthreads direct: cfs_rq has only one entity parity: RUN_TO_PARITY fast: O(1) fastpath slow: heap search (%) direct parity fast slow hackbench 92.95 2.02 4.91 0.12 netperf 68.08 6.60 24.18 1.14 tbench 67.55 11.22 20.61 0.62 schbench 69.91 2.65 25.73 1.71 The above results indicate that this fastpath really makes task selection more efficient. Signed-off-by: Abel Wu Signed-off-by: Peter Zijlstra (Intel) Link: https://lkml.kernel.org/r/20231115033647.80785-4-wuyun.abel@bytedance.com --- kernel/sched/fair.c | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 31bca05..d3e045d 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -878,6 +878,7 @@ struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) { struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node; + struct sched_entity *se = __pick_first_entity(cfs_rq); struct sched_entity *curr = cfs_rq->curr; struct sched_entity *best = NULL; @@ -886,7 +887,7 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) * in this cfs_rq, saving some cycles. */ if (cfs_rq->nr_running == 1) - return curr && curr->on_rq ? curr : __node_2_se(node); + return curr && curr->on_rq ? curr : se; if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr))) curr = NULL; @@ -898,9 +899,14 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) if (sched_feat(RUN_TO_PARITY) && curr && curr->vlag == curr->deadline) return curr; + /* Pick the leftmost entity if it's eligible */ + if (se && entity_eligible(cfs_rq, se)) { + best = se; + goto found; + } + /* Heap search for the EEVD entity */ while (node) { - struct sched_entity *se = __node_2_se(node); struct rb_node *left = node->rb_left; /* @@ -913,6 +919,8 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) continue; } + se = __node_2_se(node); + /* * The left subtree either is empty or has no eligible * entity, so check the current node since it is the one @@ -925,7 +933,7 @@ static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) node = node->rb_right; } - +found: if (!best || (curr && entity_before(curr, best))) best = curr;