From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751995AbdJYH2l (ORCPT ); Wed, 25 Oct 2017 03:28:41 -0400 Received: from mail-by2nam03on0121.outbound.protection.outlook.com ([104.47.42.121]:53940 "EHLO NAM03-BY2-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1751557AbdJYH2j (ORCPT ); Wed, 25 Oct 2017 03:28:39 -0400 From: Matthew Wilcox To: Clement Courbet , Arnd Bergmann , Rasmus Villemoes , Andrew Morton , Yury Norov CC: Ingo Molnar , "linux-arch@vger.kernel.org" , "linux-kernel@vger.kernel.org" Subject: RE: [PATCH v2] lib: optimize cpumask_next_and() Thread-Topic: [PATCH v2] lib: optimize cpumask_next_and() Thread-Index: AQHTTLZt3TOfTCp5T0qw6YXZdXwmeqL0KCEg Date: Wed, 25 Oct 2017 07:28:36 +0000 Message-ID: References: <20171024105159.18293-1-courbet@google.com> In-Reply-To: <20171024105159.18293-1-courbet@google.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: msip_labels: MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Enabled=True; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_SiteId=72f988bf-86f1-41af-91ab-2d7cd011db47; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Ref=https://api.informationprotection.azure.com/api/72f988bf-86f1-41af-91ab-2d7cd011db47; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Owner=mawilcox@microsoft.com; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_SetDate=2017-10-25T03:14:10.4663426-04:00; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Name=General; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Application=Microsoft Azure Information Protection; MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Extended_MSFT_Method=Automatic; Sensitivity=General x-originating-ip: [46.13.11.148] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;MWHPR21MB0127;6:+r+0FxF1Nu1BZU/Wck1+/3fJeW7XH9U4kwa6tQi84OU781FIPen8QznNwf+8Z0B48rlABnWUCTKaWAZy6VMvNMJJImLs2X5tQ7rpIRu56QIXyLqwxjhC15jC0yQCdoz2VexslzLhIl4DSyZR8P3nRQ5U6Z0M5s58bxgsO6RDqa2cH5BqKdA1RhyVyCObcIpAw7PK3OyNQ6hmijqfE0+8rro+MjQi5R1p+QIUTQpQKM2o2SkWKsN7xTl7O+9FkYQTMy1sP+CWcEUGHVVFdQd3MZ+lyhgfs7i0KyJc0elFoYiun3yBuIrJNfz0XI3oscSnhovZDRfe94s8WLds4mByynLtU9zcarwQ97oAWQnpAX8=;5:3wMWcnjb7u1ymgv9Lww/AMBxiS8Q0t9glfewuCot4CtsattWDlb+OKwpfGJMCj1TCn7crTboeWBRToE9/ezMSYmF3TKa9E5wkrG6L5RgEd53X8rUitFcQms3cgVq+1gJvIH9dpMXGNbI2i+x+ooKKrnOODtSCxNhL/LXS9GlSeQ=;24:lG9UeZLR2J2THdBhrwbfzIVb6oAdZ+PQzGb5bJ5G6U7CxqK+90NS6MsPXYp19UN4CqiR+52aXnIQ3Lmj/Z9VtGHyF/cCZGjAoBrfabuiZFo=;7:r95jF10t2cMhDAG5YQB6ct4UxghQE17K4DUVQ3M8se5VJnt4ch9uIptWFMhQphj8w/eBrASdelJwCVg5GbXE707K3vbqA/Npx7ckRwpLTPZXzvvH5TrNbGP7tvRF39aqEMoeMt56px6gqENK5u2wz95HbG5qAH2pOFd7mWVcU6A5Cyg2vKhXHV+jW+xhy/aETYGhqTt9SA+5BeC70wmWDGCSBm3hpD3KtoGMiYsAbyjzRisZCoTUlAY90GRuVi4z x-ms-exchange-antispam-srfa-diagnostics: SSOS; x-ms-office365-filtering-correlation-id: 06a5471c-5389-4eb6-56b6-08d51b7a0168 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:(22001)(48565401081)(4534020)(4602075)(4627075)(201703031133081)(201702281549075)(2017052603238);SRVR:MWHPR21MB0127; x-ms-traffictypediagnostic: MWHPR21MB0127: x-exchange-antispam-report-test: UriScan:(89211679590171)(9452136761055)(211936372134217)(153496737603132); x-microsoft-antispam-prvs: x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(61425038)(6040450)(2401047)(8121501046)(5005006)(3231020)(3002001)(93006095)(93001095)(100000703101)(100105400095)(10201501046)(920507026)(6055026)(61426038)(61427038)(6041248)(20161123558100)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123560025)(20161123555025)(20161123564025)(20161123562025)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095);SRVR:MWHPR21MB0127;BCL:0;PCL:0;RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095);SRVR:MWHPR21MB0127; x-forefront-prvs: 0471B73328 x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(6009001)(376002)(346002)(39860400002)(47760400005)(13464003)(199003)(189002)(5660300001)(105586002)(189998001)(7696004)(106356001)(77096006)(6506006)(97736004)(86612001)(6436002)(229853002)(86362001)(3846002)(6116002)(102836003)(53546010)(33656002)(68736007)(76176999)(54356999)(50986999)(2950100002)(101416001)(10090500001)(66066001)(8936002)(8676002)(74316002)(81156014)(81166006)(316002)(2906002)(22452003)(34040400001)(6246003)(4326008)(110136005)(14454004)(54906003)(53936002)(9686003)(3280700002)(55016002)(305945005)(99286003)(7736002)(478600001)(2900100001)(10290500003)(3660700001)(25786009)(8990500004)(357404004);DIR:OUT;SFP:1102;SCL:1;SRVR:MWHPR21MB0127;H:MWHPR21MB0845.namprd21.prod.outlook.com;FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; authentication-results: spf=none (sender IP is ) smtp.mailfrom=mawilcox@microsoft.com; spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-Network-Message-Id: 06a5471c-5389-4eb6-56b6-08d51b7a0168 X-MS-Exchange-CrossTenant-originalarrivaltime: 25 Oct 2017 07:28:36.4566 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR21MB0127 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by nfs id v9P7SmFh030767 Reviewed-by: Matthew Wilcox > -----Original Message----- > From: Clement Courbet [mailto:courbet@google.com] > Sent: Tuesday, October 24, 2017 6:52 AM > To: Arnd Bergmann ; Rasmus Villemoes > ; Andrew Morton ; > Matthew Wilcox ; Yury Norov > > Cc: Clement Courbet ; Ingo Molnar > ; linux-arch@vger.kernel.org; linux-kernel@vger.kernel.org > Subject: [PATCH v2] lib: optimize cpumask_next_and() > > We've measured that we spend ~0.6% of sys cpu time in cpumask_next_and(). > It's essentially a joined iteration in search for a non-zero bit, which > is currently implemented as a lookup join (find a nonzero bit on the > lhs, lookup the rhs to see if it's set there). > > Implement a direct join (find a nonzero bit on the incrementally built > join). Direct benchmarking shows that it's 1.17x to 14x faster with a > geometric mean of 2.1 on 32 CPUs. No impact on memory usage. > > Approximate benchmark code: > > ``` > unsigned long src1p[nr_cpumask_longs] = {pattern1}; > unsigned long src2p[nr_cpumask_longs] = {pattern2}; > for (/*a bunch of repetitions*/) { > for (int n = -1; n <= nr_cpu_ids; ++n) { > asm volatile("" : "+rm"(src1p)); // prevent any optimization > asm volatile("" : "+rm"(src2p)); > unsigned long result = cpumask_next_and(n, src1p, src2p); > asm volatile("" : "+rm"(result)); > } > } > ``` > > Results: > pattern1 pattern2 time_before/time_after > 0x0000ffff 0x0000ffff 1.65 > 0x0000ffff 0x00005555 2.24 > 0x0000ffff 0x00001111 2.94 > 0x0000ffff 0x00000000 14.0 > 0x00005555 0x0000ffff 1.67 > 0x00005555 0x00005555 1.71 > 0x00005555 0x00001111 1.90 > 0x00005555 0x00000000 6.58 > 0x00001111 0x0000ffff 1.46 > 0x00001111 0x00005555 1.49 > 0x00001111 0x00001111 1.45 > 0x00001111 0x00000000 3.10 > 0x00000000 0x0000ffff 1.18 > 0x00000000 0x00005555 1.18 > 0x00000000 0x00001111 1.17 > 0x00000000 0x00000000 1.25 > ----------------------------- > geo.mean 2.06 > > Signed-off-by: Clement Courbet > --- > Changes in v2: > - Refactored _find_next_common_bit into _find_next_bit., as suggested > by Yury Norov. This has no adverse effects on the performance side, > as the compiler successfully inlines the code. > > include/asm-generic/bitops/find.h | 16 ++++++++++++++ > include/linux/bitmap.h | 2 ++ > lib/cpumask.c | 9 ++++---- > lib/find_bit.c | 37 +++++++++++++++++++++++++-------- > tools/include/asm-generic/bitops/find.h | 16 ++++++++++++++ > 5 files changed, 67 insertions(+), 13 deletions(-) > > diff --git a/include/asm-generic/bitops/find.h b/include/asm- > generic/bitops/find.h > index 998d4d544f18..130962f3a264 100644 > --- a/include/asm-generic/bitops/find.h > +++ b/include/asm-generic/bitops/find.h > @@ -15,6 +15,22 @@ extern unsigned long find_next_bit(const unsigned long > *addr, unsigned long > size, unsigned long offset); > #endif > > +#ifndef find_next_and_bit > +/** > + * find_next_and_bit - find the next set bit in both memory regions > + * @addr1: The first address to base the search on > + * @addr2: The second address to base the search on > + * @offset: The bitnumber to start searching at > + * @size: The bitmap size in bits > + * > + * Returns the bit number for the next set bit > + * If no bits are set, returns @size. > + */ > +extern unsigned long find_next_and_bit(const unsigned long *addr1, > + const unsigned long *addr2, unsigned long size, > + unsigned long offset); > +#endif > + > #ifndef find_next_zero_bit > /** > * find_next_zero_bit - find the next cleared bit in a memory region > diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h > index 700cf5f67118..b4606bfda52f 100644 > --- a/include/linux/bitmap.h > +++ b/include/linux/bitmap.h > @@ -77,6 +77,8 @@ > * find_first_bit(addr, nbits) Position first set bit in *addr > * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit > * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit > + * find_next_and_bit(addr1, addr2, nbits, bit) Same as find_first_bit, but in > + * (*addr1 & *addr2) > */ > > /* > diff --git a/lib/cpumask.c b/lib/cpumask.c > index 8b1a1bd77539..5602223837fa 100644 > --- a/lib/cpumask.c > +++ b/lib/cpumask.c > @@ -32,10 +32,11 @@ EXPORT_SYMBOL(cpumask_next); > int cpumask_next_and(int n, const struct cpumask *src1p, > const struct cpumask *src2p) > { > - while ((n = cpumask_next(n, src1p)) < nr_cpu_ids) > - if (cpumask_test_cpu(n, src2p)) > - break; > - return n; > + /* -1 is a legal arg here. */ > + if (n != -1) > + cpumask_check(n); > + return find_next_and_bit(cpumask_bits(src1p), cpumask_bits(src2p), > + nr_cpumask_bits, n + 1); > } > EXPORT_SYMBOL(cpumask_next_and); > > diff --git a/lib/find_bit.c b/lib/find_bit.c > index 6ed74f78380c..ebc08fd9fdf8 100644 > --- a/lib/find_bit.c > +++ b/lib/find_bit.c > @@ -24,19 +24,25 @@ > #if !defined(find_next_bit) || !defined(find_next_zero_bit) > > /* > - * This is a common helper function for find_next_bit and > - * find_next_zero_bit. The difference is the "invert" argument, which > - * is XORed with each fetched word before searching it for one bits. > + * This is a common helper function for find_next_bit, find_next_zero_bit, and > + * find_next_and_bit. The differences are: > + * - The "invert" argument, which is XORed with each fetched word before > + * searching it for one bits. > + * - The optional "addr2", which is anded with "addr1" if present. > */ > -static unsigned long _find_next_bit(const unsigned long *addr, > - unsigned long nbits, unsigned long start, unsigned long invert) > +static unsigned long _find_next_bit(const unsigned long *addr1, > + const unsigned long *addr2, unsigned long nbits, > + unsigned long start, unsigned long invert) > { > unsigned long tmp; > > if (unlikely(start >= nbits)) > return nbits; > > - tmp = addr[start / BITS_PER_LONG] ^ invert; > + tmp = addr1[start / BITS_PER_LONG]; > + if (addr2) > + tmp &= addr2[start / BITS_PER_LONG]; > + tmp ^= invert; > > /* Handle 1st word. */ > tmp &= BITMAP_FIRST_WORD_MASK(start); > @@ -47,7 +53,10 @@ static unsigned long _find_next_bit(const unsigned long > *addr, > if (start >= nbits) > return nbits; > > - tmp = addr[start / BITS_PER_LONG] ^ invert; > + tmp = addr1[start / BITS_PER_LONG]; > + if (addr2) > + tmp &= addr2[start / BITS_PER_LONG]; > + tmp ^= invert; > } > > return min(start + __ffs(tmp), nbits); > @@ -61,7 +70,7 @@ static unsigned long _find_next_bit(const unsigned long > *addr, > unsigned long find_next_bit(const unsigned long *addr, unsigned long size, > unsigned long offset) > { > - return _find_next_bit(addr, size, offset, 0UL); > + return _find_next_bit(addr, NULL, size, offset, 0UL); > } > EXPORT_SYMBOL(find_next_bit); > #endif > @@ -70,11 +79,21 @@ EXPORT_SYMBOL(find_next_bit); > unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long > size, > unsigned long offset) > { > - return _find_next_bit(addr, size, offset, ~0UL); > + return _find_next_bit(addr, NULL, size, offset, ~0UL); > } > EXPORT_SYMBOL(find_next_zero_bit); > #endif > > +#if !defined(find_next_and_bit) > +unsigned long find_next_and_bit(const unsigned long *addr1, > + const unsigned long *addr2, unsigned long nbits, > + unsigned long start) > +{ > + return _find_next_bit(addr1, addr2, size, offset, ~0UL); > +} > +EXPORT_SYMBOL(find_next_and_bit); > +#endif > + > #ifndef find_first_bit > /* > * Find the first set bit in a memory region. > diff --git a/tools/include/asm-generic/bitops/find.h b/tools/include/asm- > generic/bitops/find.h > index 5538ecdc964a..435c7d002f33 100644 > --- a/tools/include/asm-generic/bitops/find.h > +++ b/tools/include/asm-generic/bitops/find.h > @@ -15,6 +15,22 @@ extern unsigned long find_next_bit(const unsigned long > *addr, unsigned long > size, unsigned long offset); > #endif > > +#ifndef find_next_and_bit > +/** > + * find_next_and_bit - find the next set bit in both memory regions > + * @addr1: The first address to base the search on > + * @addr2: The second address to base the search on > + * @offset: The bitnumber to start searching at > + * @size: The bitmap size in bits > + * > + * Returns the bit number for the next set bit > + * If no bits are set, returns @size. > + */ > +extern unsigned long find_next_and_bit(const unsigned long *addr1, > + const unsigned long *addr2, unsigned long size, > + unsigned long offset); > +#endif > + > #ifndef find_next_zero_bit > > /** > -- > 2.15.0.rc0.271.g36b669edcc-goog