linux-kernel - Re: [PATCH] Optimize bitmap

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAC5umyi_P6UkOrCXHV1+Oonj3MGL=HHP5V-7WauEaPvqe2Utcg@mail.gmail.com>
Date:	Tue, 15 May 2012 20:58:10 +0900
From:	Akinobu Mita <akinobu.mita@...il.com>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] Optimize bitmap_weight

2012/5/15 Andrew Morton <akpm@...ux-foundation.org>:
> On Mon, 14 May 2012 06:50:15 +0900
> Akinobu Mita <akinobu.mita@...il.com> wrote:
>
>> 2012/5/12 Andrew Morton <akpm@...ux-foundation.org>:
>> > On Fri, 11 May 2012 23:10:14 +0900
>> > Akinobu Mita <akinobu.mita@...il.com> wrote:
>> >
>> >> The current implementation of bitmap_weight simply evaluates the
>> >> population count for each long word of the array, and adds.
>> >>
>> >> The subsection "Counting 1-bits in an Array" in the revisions of
>> >> the book 'Hacker's Delight' explains more superior methods than
>> >> the naive method.
>> >>
>> >> http://www.hackersdelight.org/revisions.pdf
>> >> http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt
>> >>
>> >> My benchmark results on Intel Core i3 CPU with 32-bit kernel
>> >> showed 50% faster for 8192 bits bitmap.  However, it is not faster
>> >> for small bitmap (< BITS_PER_LONG * 8) than the naive method.
>> >> So if the bitmap size is known to be small at compile time,
>> >> use the naive method.
>> >>
>> >> ...
>> >>
>> >>  extern void bitmap_clear(unsigned long *map, int start, int nr);
>> >> @@ -277,7 +278,9 @@ static inline int bitmap_weight(const unsigned long *src, int nbits)
>> >>  {
>> >>       if (small_const_nbits(nbits))
>> >>               return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
>> >
>> > Why do we require a constant_p `nbits' for this case?
>
> ^^ this?

The commit 4b0bc0bca83f3fb7cf920e2ec80684c15d2269c0
"bitmap: test for constant as well as small size for inline versions"
explains that it's for reducing text size, especially for the variable
cpumasks.

>> >> -     return  bitmap_weight(src, nbits);
>> >> +     else if ( builtin_constant_p(nbits) && (nbits) < BITS_PER_LONG * 8)
>> >> +             return  bitmap_weight(src, nbits);
>> >> +     return  bitmap_weight_fast(src, nbits);
>> >>  }
>> >
>> > BITS_PER_LONG*8 sounds like a large bitmap: 256 or 512 entries.  Will
>> > the kernel call  bitmap_weight_fast() sufficiently often to make this
>> > extra code worth merging?
>> >
>>
>> I roughly checked the call sites of bitmap_weight() and picked up some
>> outstanding usages below.
>>
>> Some filesystems (udf, omfs, ntfs, and hpfs) use bitmap_weight() to
>> the block size bytes region in statfs() path.
>>
>> num_online_cpus() and the variants are bitmap_weight() to the NR_CPUS
>> bitmap and num_online_nodes() and the variants are to the MAX_NUMNODES
>> bitmap.  So these bitmaps could be large on extremely large system.
>>
>> bm_count_bits() in drivers/block/drbd/drbd_bitmap.c computes the
>> population count for multiple pages.  But it is currently open-coded
>> loops with hweight_long() which can be converted to bitmap_weight().
>>
>> I consider introducing bitmap_weight_large() which is specialized for
>> the large bitmap instead of optimizing bitmap_weight() and replace the
>> call sites like above.
>
> I don't see much advantage to that - it would be better if
> bitmap_weight() Just Works.

OK, I withdraw the idea of bitmap_weight_large().
Do you still have doubts about merging this and want examples
counting large bitmap popcount in kernel?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/