Received: by 2002:a05:6a10:8c0a:0:0:0:0 with SMTP id go10csp979574pxb; Wed, 3 Mar 2021 23:19:27 -0800 (PST) X-Google-Smtp-Source: ABdhPJx04hYcpG3JN3himo4lwrTVYs+WxJffI5SnD8XShoGh7rIZ750PjjO9e+VltIocyr35o3xY X-Received: by 2002:a17:906:3603:: with SMTP id q3mr2580756ejb.201.1614842367186; Wed, 03 Mar 2021 23:19:27 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1614842367; cv=none; d=google.com; s=arc-20160816; b=sUVAU7ilfTZwFHC5/XLtHOxudXCHnyTrTmSFoeJyO6FYfEiK7NPWu8r0ayv9ztRXIB SFLkw7yQTi9pPowPiqxLUfQ9yriYa32B6Iq+o0F7LbkNXj9zey+i6P337iu7bswtlF2F cCh9rND8ApESaEcHyxR3FKGkF1ziYkqnYQxPPFCL52aSbwOyolSJWEEGBbb1JTQxMmvu UThQ+YvfScYxY8TL+bLQ3ipgvmrB9znsuQ/LsMhHJPIiRWQahV/Ih/f5VkU4olJVK93s cfMTqPorpEHazsNsFFP4wnxwjecqzJ560mdr4jGl3sYBY0L3nly66KsjuxuLuW3lqWuN 2YWA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:cc:to:subject :message-id:date:from:in-reply-to:references:mime-version :dkim-signature; bh=ZJLDfWzNU3w9w48fw//Uxyb1sOcIpyn6YYFLL1vcIk8=; b=dP3xQ6sHRoKD6RNI1ea4/2dWasVXhexlHbTRfosan0RennvNVF2aOenvY+QTE53/hg 4mQ/OQHVenyhw4oh1nXCP+NDzT+yIziVHIYndH1e8y72bTFIBNypn9I7EVtyHVf+Olpt QREkuu+YYi25rVrTiHdAHqO620eMRhq3EFY7hcok0frvpMAnYoVDBEDYD15b2JuXNpgt 40CuTNP2p8p+UAQZGr38gTpz74QveNjx+9lzaE2f3u1MgeC4lyBmcZ8gMmo4xXFvcTOQ LVvbNda/6i5l2ddP0w1bWXm4sGbg/8lTjPqtWXb0z1j0s3fZZTT+id7bJXUpBGniKFHs r4cw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=Kzt75NHg; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [23.128.96.18]) by mx.google.com with ESMTP id p14si4108817eji.719.2021.03.03.23.19.05; Wed, 03 Mar 2021 23:19:27 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=Kzt75NHg; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2360368AbhCBWTl (ORCPT + 99 others); Tue, 2 Mar 2021 17:19:41 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37186 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240248AbhCBU6c (ORCPT ); Tue, 2 Mar 2021 15:58:32 -0500 Received: from mail-qk1-x733.google.com (mail-qk1-x733.google.com [IPv6:2607:f8b0:4864:20::733]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9318CC061756 for ; Tue, 2 Mar 2021 12:57:49 -0800 (PST) Received: by mail-qk1-x733.google.com with SMTP id s7so11686357qkg.4 for ; Tue, 02 Mar 2021 12:57:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=ZJLDfWzNU3w9w48fw//Uxyb1sOcIpyn6YYFLL1vcIk8=; b=Kzt75NHgnvYvy5prBScBu7knefWFLKoR8R0acXtUSwTMkQWiqa6IKhg9XDU/4NmMSe QKzybEvDTbkp6MMPdwgaUE6k/Ip3hRFF1ya1Maax8049PegWP/FF7m0G6N68xgeZZnVu LCq3BYY0GUmtQfh9LBaqBgi3qiUczqtzcfBI1UAPSWZNz2EQFxnHQj0zR3FALHG85ogF E/6TmRHYjO/68sowblYtMA/VhzBv/THqUFPGlZhwy0YR3C+COCjXrVGBiyGdfEWhInXZ +Ta/tK4yL3AX0ECzeCOI3yct8avAXBf8vK/yfmJAKoYd3SyTX+lKM4kPRYJEvLdIJV5D tcOg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=ZJLDfWzNU3w9w48fw//Uxyb1sOcIpyn6YYFLL1vcIk8=; b=rYtGTyehopyWuDb2+yG/z+1dGsY0S0w5tC2dI443k5xwxTsPCv5cTK/n2JjEDLv9AQ A3DB8kWK9XiQtWwTdW75j4BfhNXeyawZB04YMjh4e61GVjjF27ODN5MajZImc1yI3YZz SZEfOo659CufGsaf4yokPmFogEv7U6BZMnwGgangvi8HO0E41ziJ9ivpg1J3zgqDb3E9 UolkXQPCHW1hkjq2D3EWs/737CJKwY2qdHRbcUGSL17j8AMmH3d4Osyu618kdG83hD8D ghLYJYBAjCcHvYX92KLKX+lKrm+rdGzD/KsYL++eDrRAiVqk4wOJOZyvZ4XO5co9JvP+ cwrg== X-Gm-Message-State: AOAM531Za7HygP3liNJzFx7YIPoEjbUdilY5a26oXX46WAtYpu+OXzvS 1EpiIzKLnJgj3U1iB5wlxOB2W+d8l8wWhubIXaz91Q== X-Received: by 2002:a05:620a:1410:: with SMTP id d16mr20764625qkj.465.1614718668150; Tue, 02 Mar 2021 12:57:48 -0800 (PST) MIME-Version: 1.0 References: <20210226195239.3905966-1-joshdon@google.com> In-Reply-To: From: Josh Don Date: Tue, 2 Mar 2021 12:57:37 -0800 Message-ID: Subject: Re: [PATCH] sched: Optimize __calc_delta. To: Peter Zijlstra Cc: Ingo Molnar , Juri Lelli , Vincent Guittot , Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , Daniel Bristot de Oliveira , linux-kernel , Clement Courbet , Oleg Rombakh Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Clement Courbet A significant portion of __calc_delta time is spent in the loop shifting a u64 by 32 bits. Use `fls` instead of iterating. This is ~7x faster on benchmarks. The generic `fls` implementation (`generic_fls`) is still ~4x faster than the loop. Architectures that have a better implementation will make use of it. For example, on X86 we get an additional factor 2 in speed without dedicated implementation. On gcc, the asm versions of `fls` are about the same speed as the builtin. On clang, the versions that use fls (fls,fls64) are more than twice as slow as the builtin. This is because the way the `fls` function is written, clang puts the value in memory: https://godbolt.org/z/EfMbYe. This can be fixed in a separate patch. ``` name cpu/op BM_Calc<__calc_delta_loop> 9.57ms =C2=B112% BM_Calc<__calc_delta_generic_fls> 2.36ms =C2=B113% BM_Calc<__calc_delta_asm_fls> 2.45ms =C2=B113% BM_Calc<__calc_delta_asm_fls_nomem> 1.66ms =C2=B112% BM_Calc<__calc_delta_asm_fls64> 2.46ms =C2=B113% BM_Calc<__calc_delta_asm_fls64_nomem> 1.34ms =C2=B115% BM_Calc<__calc_delta_builtin> 1.32ms =C2=B111% ``` Signed-off-by: Clement Courbet Signed-off-by: Josh Don --- kernel/sched/fair.c | 30 ++++++++++++++++++++++-------- kernel/sched/sched.h | 1 + 2 files changed, 23 insertions(+), 8 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 8a8bd7b13634..67e5a1d536ad 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -214,6 +214,16 @@ static void __update_inv_weight(struct load_weight *lw= ) lw->inv_weight =3D WMULT_CONST / w; } +/* + * An fls that handles an u32 value on architectures + * where `sizeof(unsigned int) < 32`. + */ +#if (__SIZEOF_INT__ >=3D 32) +# define FLS_AT_LEAST_32(v) fls(v) +#else +# define FLS_AT_LEAST_32(v) fls64(v) +#endif + /* * delta_exec * weight / lw.weight * OR @@ -229,27 +239,31 @@ static void __update_inv_weight(struct load_weight *l= w) static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw) { u64 fact =3D scale_load_down(weight); + u32 fact_hi =3D (u32)(fact >> 32); int shift =3D WMULT_SHIFT; + int fs; __update_inv_weight(lw); - if (unlikely(fact >> 32)) { - while (fact >> 32) { - fact >>=3D 1; - shift--; - } + if (unlikely(fact_hi)) { + fs =3D FLS_AT_LEAST_32(fact_hi); + shift -=3D fs; + fact >>=3D fs; } fact =3D mul_u32_u32(fact, lw->inv_weight); - while (fact >> 32) { - fact >>=3D 1; - shift--; + fact_hi =3D (u32)(fact >> 32); + if (fact_hi) { + fs =3D FLS_AT_LEAST_32(fact_hi); + shift -=3D fs; + fact >>=3D fs; } return mul_u64_u32_shr(delta_exec, fact, shift); } +#undef FLS_AT_LEAST_32 const struct sched_class fair_sched_class; diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 10a1522b1e30..714af71cf983 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -36,6 +36,7 @@ #include #include +#include #include #include #include --=20 2.30.1.766.gb4fecdf3b7-goog