RE: [PATCH v2] lib: optimize cpumask_next_and()
From: Matthew Wilcox
Date: Wed Oct 25 2017 - 03:28:46 EST
Reviewed-by: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>
> -----Original Message-----
> From: Clement Courbet [mailto:courbet@xxxxxxxxxx]
> Sent: Tuesday, October 24, 2017 6:52 AM
> To: Arnd Bergmann <arnd@xxxxxxxx>; Rasmus Villemoes
> <linux@xxxxxxxxxxxxxxxxxx>; Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>;
> Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>; Yury Norov
> <ynorov@xxxxxxxxxxxxxxxxxx>
> Cc: Clement Courbet <courbet@xxxxxxxxxx>; Ingo Molnar
> <mingo@xxxxxxxxxx>; linux-arch@xxxxxxxxxxxxxxx; linux-kernel@xxxxxxxxxxxxxxx
> 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 <courbet@xxxxxxxxxx>
> ---
> 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