From patchwork Fri Oct 1 18:12:45 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 12531595 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6764EC433FE for ; Fri, 1 Oct 2021 18:15:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 54B1F6127B for ; Fri, 1 Oct 2021 18:15:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1355957AbhJASQt (ORCPT ); Fri, 1 Oct 2021 14:16:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50386 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1355897AbhJASQ1 (ORCPT ); Fri, 1 Oct 2021 14:16:27 -0400 Received: from mail-pj1-x1033.google.com (mail-pj1-x1033.google.com [IPv6:2607:f8b0:4864:20::1033]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 87D09C0613AA; Fri, 1 Oct 2021 11:13:37 -0700 (PDT) Received: by mail-pj1-x1033.google.com with SMTP id oj15-20020a17090b4d8f00b0019f8860d6e2so824269pjb.5; Fri, 01 Oct 2021 11:13:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=FlSQA/x8Q659lExbJ8x+3pbQGN8nCVePZlCG2RLxniQ=; b=dNr9oSu6Qtp0DeQk6DSDUbA9YikKVIz9z6eDiaeb6OMzoEdg9gAFlLLwsOWXLrGG8M Tf6ft5iMykzEGrZMsfgyC9QLYxeJZzr9iokrdPNjaxqOaAq2tRkql/LvBg7Oo5bXXM7K 6j6QD6fvxGLhYzQVks5mwK0mKYnxwzsRZyJ8VPG4lYVlogXWb2FMSaNXHbJRufBdnKqU mFgBekVMogPp8ABPAVRABc0Fq2iUE0SzqOLA3wJsXjpr6o45seO512t+JfJ6HU5UQeV0 qQSgp9y9Gl4LBdLJ7YMJ84T/d4ko6eiEc+Ih+Sz3NT81xaniChwYG66PpEO7KGxtm3kA Ozuw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=FlSQA/x8Q659lExbJ8x+3pbQGN8nCVePZlCG2RLxniQ=; b=RAGdtbKX8YkTZTyHJpSnqKKpD5s2fXQqsAvEHGJ+T+WxfcZJ5Zps2ZYGg0LgV/NjZo goWoeWmPHSrTo3uh7eKPzXegStQ656h4qzzxvo4vO1n3Z3q2twolLf0Y/FjewZWZbW2F 3iOR/r25853OqFF8zn/dCW3w1IzYHzEFtN/zPqpIaMxBitpdZm/Gw7W34peVSKv0OV8R NzWVIWMNPLf+eJeLNUinf4JJWGLYqYU3x1znZZ/Te1jC0B3XiytCamttx3dp3d6flIeX uLwJ7BREjFIa33p5SgEoMg+7QGfN5dsALuPk2wTKv6xcN4KR1+EOwyT4MbkMUh4hjnvf 3XXw== X-Gm-Message-State: AOAM530tnZYscEsy/BAvm+BSDfGzGXnkqHDHmiNuInVY1qQSUMsNQOhv 23RBH0KvYla25iDhn276ojc= X-Google-Smtp-Source: ABdhPJwYukMmWxTyp0ryKmZnt4pz+cTynvNrINevzce5Gbx7dcqhhXEHbxJDQcDzmMx/MR36JOPG5g== X-Received: by 2002:a17:90a:4815:: with SMTP id a21mr14770802pjh.108.1633112017021; Fri, 01 Oct 2021 11:13:37 -0700 (PDT) Received: from localhost (searspoint.nvidia.com. [216.228.112.21]) by smtp.gmail.com with ESMTPSA id p4sm5778054pjo.0.2021.10.01.11.13.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 01 Oct 2021 11:13:36 -0700 (PDT) From: Yury Norov To: Stephen Rothwell Cc: Yury Norov , Andrew Morton , linux-kernel@vger.kernel.org, linux-mm@kvack.org, linux-arch@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-mmc@vger.kernel.org, linux-perf-users@vger.kernel.org, kvm@vger.kernel.org, "James E.J. Bottomley" , Alexander Lobakin , Alexander Shishkin , Alexey Klimov , Andrea Merello , Andy Shevchenko , Arnaldo Carvalho de Melo , Arnd Bergmann , Ben Gardon , Benjamin Herrenschmidt , Brian Cain , Catalin Marinas , Christoph Lameter , Daniel Bristot de Oliveira , David Hildenbrand , Dennis Zhou , Geert Uytterhoeven , Heiko Carstens , Ian Rogers , Ingo Molnar , Jaegeuk Kim , Jakub Kicinski , Jiri Olsa , Joe Perches , Jonas Bonn , Leo Yan , Mark Rutland , Namhyung Kim , Palmer Dabbelt , Paolo Bonzini , Peter Xu , Peter Zijlstra , Petr Mladek , Rasmus Villemoes , Rich Felker , Samuel Mendoza-Jonas , Sean Christopherson , Sergey Senozhatsky , Shuah Khan , Stefan Kristiansson , Steven Rostedt , Tejun Heo , Thomas Bogendoerfer , Ulf Hansson , Will Deacon , Wolfram Sang , Yoshinori Sato Subject: [PATCH 16/16] vsprintf: rework bitmap_list_string Date: Fri, 1 Oct 2021 11:12:45 -0700 Message-Id: <20211001181245.228419-17-yury.norov@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211001181245.228419-1-yury.norov@gmail.com> References: <20211001181245.228419-1-yury.norov@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-mmc@vger.kernel.org bitmap_list_string() is very ineffective when printing bitmaps with long ranges of set bits because it calls find_next_bit for each bit in the bitmap. We can do better by detecting ranges of set bits. In my environment, before/after is 943008/31008 ns. Signed-off-by: Yury Norov Tested-by: Wolfram Sang --- lib/vsprintf.c | 24 +++++++----------------- 1 file changed, 7 insertions(+), 17 deletions(-) diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 67a96165e587..d1bbf1d78df3 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -1241,20 +1241,13 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap, struct printf_spec spec, const char *fmt) { int nr_bits = max_t(int, spec.field_width, 0); - /* current bit is 'cur', most recently seen range is [rbot, rtop] */ - int cur, rbot, rtop; bool first = true; + int rbot, rtop; if (check_pointer(&buf, end, bitmap, spec)) return buf; - rbot = cur = find_first_bit(bitmap, nr_bits); - while (cur < nr_bits) { - rtop = cur; - cur = find_next_bit(bitmap, nr_bits, cur + 1); - if (cur < nr_bits && cur <= rtop + 1) - continue; - + for_each_set_bitrange(rbot, rtop, bitmap, nr_bits) { if (!first) { if (buf < end) *buf = ','; @@ -1263,15 +1256,12 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap, first = false; buf = number(buf, end, rbot, default_dec_spec); - if (rbot < rtop) { - if (buf < end) - *buf = '-'; - buf++; - - buf = number(buf, end, rtop, default_dec_spec); - } + if (rtop == rbot + 1) + continue; - rbot = cur; + if (buf < end) + *buf = '-'; + buf = number(++buf, end, rtop - 1, default_dec_spec); } return buf; }