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: 12531503 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 7816EC433EF for ; Fri, 1 Oct 2021 18:13:39 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 2E03161263 for ; Fri, 1 Oct 2021 18:13:39 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.1 mail.kernel.org 2E03161263 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 CB992940138; Fri, 1 Oct 2021 14:13:38 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C69F6940121; Fri, 1 Oct 2021 14:13:38 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B0B00940138; Fri, 1 Oct 2021 14:13:38 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0102.hostedemail.com [216.40.44.102]) by kanga.kvack.org (Postfix) with ESMTP id A2CD4940121 for ; Fri, 1 Oct 2021 14:13:38 -0400 (EDT) Received: from smtpin23.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id 5D8C71809B0BB for ; Fri, 1 Oct 2021 18:13:38 +0000 (UTC) X-FDA: 78648666516.23.985EB7D Received: from mail-pj1-f46.google.com (mail-pj1-f46.google.com [209.85.216.46]) by imf12.hostedemail.com (Postfix) with ESMTP id 155701000699 for ; Fri, 1 Oct 2021 18:13:37 +0000 (UTC) Received: by mail-pj1-f46.google.com with SMTP id om12-20020a17090b3a8c00b0019eff43daf5so7745902pjb.4 for ; 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=vy5L3vXW2rAq+ZZ8ZTmbzMgqa6tJvl+Y89RhPw35E1BOvK9HOyij7l3AEln2q/ENHP MzWENX/N+puW2nbOqMkkJVBhmoGMHJJ+X8fHhBkH4eJXRQ3eb8UXI4TvNe9lelRpj2nc BUV72oLFKaHxAaq3EwX7RNE/mwpQU6YKJ4E1dIEU2TUi3gbn2u0AGJ1WP+vGZLdi/r9M qqQMGNHDpzlracXJ9RieRg/RduVKql7g89wiSJIxsS+WBEydUCW5CJsNNN18PRJJBgNF sCpGwqf1erMP+JHFlqtRssfehdr3gT5bfGvPDjFASOtfjneoOJOE5adZlwhAxAP8pEQc Kkag== X-Gm-Message-State: AOAM530xVoSl/TrqTcLx8KPb9TDxtbo7A28qe6GY25MJs1T6qU6d6DcX 4na9Ty4tWXQfM73AwJPBOlE= 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 X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 155701000699 X-Stat-Signature: mpien99b33qhzmw81nom5ms1s4fupcoi Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=dNr9oSu6; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf12.hostedemail.com: domain of yury.norov@gmail.com designates 209.85.216.46 as permitted sender) smtp.mailfrom=yury.norov@gmail.com X-HE-Tag: 1633112017-597703 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 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; }