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] [day] [month] [year] [list]

Message-ID: <CAC5umyiisLM3MA-MdG4UBJW8hb-4+ZyhuBtcakuZgZuavJDfOg@mail.gmail.com>
Date:	Sat, 26 May 2012 07:57:55 +0900
From:	Akinobu Mita <akinobu.mita@...il.com>
To:	linux-kernel@...r.kernel.org, akpm@...ux-foundation.org
Subject: Re: [PATCH] Optimize bitmap_weight

2012/5/11 Akinobu Mita <akinobu.mita@...il.com>:
> 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.

My benchmark was bogus.  I used __sw_hweight32 for hweight_long.
It is much slower on x86 with X86_FEATURE_POPCNT.

This patch slows bitmap_weight().  So please drop this patch
(bitmap_weight-optimize-for-large-bitmaps.patch) from -mm tree.
--
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/