From patchwork Tue Oct 5 05:40:59 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yury Norov X-Patchwork-Id: 12535565 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 7EAAEC433F5 for ; Tue, 5 Oct 2021 05:41:49 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 3514B60187 for ; Tue, 5 Oct 2021 05:41:49 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.1 mail.kernel.org 3514B60187 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=kvack.org Received: by kanga.kvack.org (Postfix) id D05726B0088; Tue, 5 Oct 2021 01:41:48 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CB50E6B0089; Tue, 5 Oct 2021 01:41:48 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B56046B008A; Tue, 5 Oct 2021 01:41:48 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0177.hostedemail.com [216.40.44.177]) by kanga.kvack.org (Postfix) with ESMTP id A52566B0088 for ; Tue, 5 Oct 2021 01:41:48 -0400 (EDT) Received: from smtpin22.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay01.hostedemail.com (Postfix) with ESMTP id 70D67181D471B for ; Tue, 5 Oct 2021 05:41:48 +0000 (UTC) X-FDA: 78661287096.22.534D398 Received: from mail-pg1-f181.google.com (mail-pg1-f181.google.com [209.85.215.181]) by imf01.hostedemail.com (Postfix) with ESMTP id 2CF86507212E for ; Tue, 5 Oct 2021 05:41:48 +0000 (UTC) Received: by mail-pg1-f181.google.com with SMTP id s11so18730158pgr.11 for ; Mon, 04 Oct 2021 22:41:47 -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=+ZNFqZL6Mgo5rwsf7yN4tz0gd8I7XPFY6Ga4YBxagho=; b=kU5Y7HnPbgF+Rq+MtA/+UamygPQuNDHOtRvNjoP5AwB4aNWInI+I9OI3kWMvB9OG00 w/nOUbCy/H/lq2Bs9UsDu6ZVYXMII3SFKrk8sAPK4jF9AVUKTCt/9kazO/wvjbq5kJCx 75+NTA/EHHqNtci9D5KdfHHX3CNsg5bcz8rKKPiMNn8PiwQPVBDqeb7PzbTJm9VA/h8T f6xuMp9rgyeko2lCqmohheESfCVP+XBsReLy+67Xbzf27iDLWfxqqf4qxGxID2zUEges qoYCsIpZkF1UPft6kwjC/4fqzTm5buicksIiqtWMYlOVYBHvDSIiabJzt789r3Nsou0b sw6Q== 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=+ZNFqZL6Mgo5rwsf7yN4tz0gd8I7XPFY6Ga4YBxagho=; b=2jB+UXjIkwwbdf0nMQ6+GPHKA0JbWSunW2xPQ5yb1gmM1IaA41ydPoVaVUue5PpCDy D8rpOCT0l/iceZnjLSy2QaNBC5kLL7DEizBJ4P3Hr4boY3YoD7jGihhoWh2nnjJoDrPK E8kSw2PcW4gP3Hg3aPwd7Sje8bHbfKFHR13JEPfvxhmFqZu/mLK4XAw/vHMj1zAk4Eqw tBunsHRj87Yijj9Q2vlIF4qZzfiAgbjpEMXMAcbb3iFxuKAU21AKXhVzok4NHpWAftMc Pwj3//vHUaJLVYK9caCPxfoGiGrhdSVgRkBINJKXOmmGR8/zXjyMehuK+jid8l9sXA7L pN4w== X-Gm-Message-State: AOAM531ivv04kWMo6u4qZ2YuwdCCPrbmQZZLIC60H2yEAWMJzovvt7oe UO/j4LtJxcuh/cyFqhrun+g= X-Google-Smtp-Source: ABdhPJyceY+Tjx2E1vLJ8VOw77txS+bxzlDVR3Dhcj/EVOQXuYONaKvyFMjEqfjvCyKzvGpZH3bvSA== X-Received: by 2002:a65:400c:: with SMTP id f12mr14150413pgp.296.1633412507236; Mon, 04 Oct 2021 22:41:47 -0700 (PDT) Received: from localhost (searspoint.nvidia.com. [216.228.112.21]) by smtp.gmail.com with ESMTPSA id q27sm9268916pfg.125.2021.10.04.22.41.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Oct 2021 22:41:46 -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: Mon, 4 Oct 2021 22:40:59 -0700 Message-Id: <20211005054059.475634-17-yury.norov@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211005054059.475634-1-yury.norov@gmail.com> References: <20211005054059.475634-1-yury.norov@gmail.com> MIME-Version: 1.0 X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: 2CF86507212E X-Stat-Signature: 6cq3gaxhuma6w6dh8ij3o9uf8y5bzbhq Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=kU5Y7HnP; spf=pass (imf01.hostedemail.com: domain of yury.norov@gmail.com designates 209.85.215.181 as permitted sender) smtp.mailfrom=yury.norov@gmail.com; dmarc=pass (policy=none) header.from=gmail.com X-HE-Tag: 1633412508-246012 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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 d7ad44f2c8f5..4415bea601fd 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; }