mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
* [PATCH 00/18] lib: bitmap: Various improvements
@ 2014-07-03 22:42 Rasmus Villemoes
  2014-07-03 22:42 ` [PATCH 01/18] lib: bitmap: Make nbits parameter of bitmap_empty unsigned Rasmus Villemoes
                   ` (18 more replies)
  0 siblings, 19 replies; 21+ messages in thread
From: Rasmus Villemoes @ 2014-07-03 22:42 UTC (permalink / raw)
  To: linux-kernel; +Cc: Rasmus Villemoes

Many functions in lib/bitmap.c start with an expression such as lim =
bits/BITS_PER_LONG. Since bits has type (signed) int, and since gcc
cannot know that it is in fact non-negative, it generates worse code
than it could. These patches, mostly consisting of changing various
parameters to unsigned, gives a slight overall code reduction:

add/remove: 1/1 grow/shrink: 8/16 up/down: 251/-414 (-163)
function                                     old     new   delta
tick_device_uses_broadcast                   335     425     +90
__irq_alloc_descs                            498     554     +56
__bitmap_andnot                               73     115     +42
__bitmap_and                                  70     101     +31
bitmap_weight                                  -      11     +11
copy_hugetlb_page_range                      752     762     +10
follow_hugetlb_page                          846     854      +8
hugetlb_init                                1415    1417      +2
hugetlb_nrpages_setup                        130     131      +1
hugetlb_add_hstate                           377     376      -1
bitmap_allocate_region                        82      80      -2
select_task_rq_fair                         2202    2191     -11
hweight_long                                  66      55     -11
__reg_op                                     230     219     -11
dm_stats_message                            2849    2833     -16
bitmap_parselist                              92      74     -18
__bitmap_weight                              115      97     -18
__bitmap_subset                              153     129     -24
__bitmap_full                                128     104     -24
__bitmap_empty                               120      96     -24
bitmap_set                                   179     149     -30
bitmap_clear                                 185     155     -30
__bitmap_equal                               136     105     -31
__bitmap_intersects                          148     108     -40
__bitmap_complement                          109      67     -42
tick_device_setup_broadcast_func.isra         81       -     -81

[The increases in __bitmap_and{,not} are due to bug fixes 17/18,18/18.
No idea why bitmap_weight suddenly appears.] While 163 bytes treewide
is insignificant, I believe the bitmap functions are often called with
locks held, so saving even a few cycles might be worth it.

While making these changes, I found a few other things that might be
worth including. 16,17,18 are actual bug fixes. The rest shouldn't
change the behaviour of any of the functions, provided no-one passed
negative nbits values. If something should come up, it should be
fairly bisectable.

A few issues I thought about, but didn't know what to do with:

* Many of the functions misbehave if nbits is compile-time 0; the
  out-of-line functions generally handle 0 correctly. bitmap_fill() is
  particularly bad, whether the 0 is known at compile time or not. It
  would probably be nice to add detection of at least compile-time 0
  and handle that appropriately.

* I didn't change __bitmap_shift_{left,right} to use unsigned because
  I want to fully understand why the algorithm works before making
  that change. However, AFAICT, they behave correctly for all
  (positive) shift amounts. This is not the case for the
  small_const_nbits versions. If for example nbits = n =
  BITS_PER_LONG, the shift operators turn into no-ops (at least on
  x86), so one get *dst = *src, whereas one would expect to get
  *dst=0. That difference in behaviour is somewhat annoying.

Rasmus Villemoes (18):
  lib: bitmap: Make nbits parameter of bitmap_empty unsigned
  lib: bitmap: Make nbits parameter of bitmap_full unsigned
  lib: bitmap: Make nbits parameter of bitmap_equal unsigned
  lib: bitmap: Make nbits parameter of bitmap_complement unsigned
  lib: bitmap: Remove unnecessary mask from bitmap_complement
  lib: bitmap: Make nbits parameter of bitmap_{and,or,xor,andnot}
    unsigned
  lib: bitmap: Make nbits parameter of bitmap_intersects unsigned
  lib: bitmap: Make nbits parameter of bitmap_subset unsigned
  lib: bitmap: Make nbits parameter of bitmap_weight unsigned
  lib: bitmap: Make the start index of bitmap_set unsigned
  lib: bitmap: Make the start index of bitmap_clear unsigned
  lib: bitmap: Simplify bitmap_parselist
  lib: bitmap: Fix typo in kerneldoc for bitmap_pos_to_ord
  lib: bitmap: Change parameter of bitmap_*_region to unsigned
  lib: bitmap: Micro-optimize bitmap_allocate_region
  lib: bitmap: Add missing mask in bitmap_shift_right
  lib: bitmap: Add missing mask in bitmap_and
  lib: bitmap: Add missing mask in bitmap_andnot

 include/linux/bitmap.h |  62 +++++++++++++--------------
 lib/bitmap.c           | 111 +++++++++++++++++++++++++------------------------
 2 files changed, 87 insertions(+), 86 deletions(-)

-- 
1.9.2

^ permalink raw reply	[flat|nested] 21+ messages in thread
end of thread, other threads:[~2014-07-07 23:45 UTC | newest]

Thread overview: 21+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-07-03 22:42 [PATCH 00/18] lib: bitmap: Various improvements Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 01/18] lib: bitmap: Make nbits parameter of bitmap_empty unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 02/18] lib: bitmap: Make nbits parameter of bitmap_full unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 03/18] lib: bitmap: Make nbits parameter of bitmap_equal unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 04/18] lib: bitmap: Make nbits parameter of bitmap_complement unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 05/18] lib: bitmap: Remove unnecessary mask from bitmap_complement Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 06/18] lib: bitmap: Make nbits parameter of bitmap_{and,or,xor,andnot} unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 07/18] lib: bitmap: Make nbits parameter of bitmap_intersects unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 08/18] lib: bitmap: Make nbits parameter of bitmap_subset unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 09/18] lib: bitmap: Make nbits parameter of bitmap_weight unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 10/18] lib: bitmap: Make the start index of bitmap_set unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 11/18] lib: bitmap: Make the start index of bitmap_clear unsigned Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 12/18] lib: bitmap: Simplify bitmap_parselist Rasmus Villemoes
2014-07-03 22:42 ` [PATCH 13/18] lib: bitmap: Fix typo in kerneldoc for bitmap_pos_to_ord Rasmus Villemoes
2014-07-03 22:43 ` [PATCH 14/18] lib: bitmap: Change parameter of bitmap_*_region to unsigned Rasmus Villemoes
2014-07-03 22:43 ` [PATCH 15/18] lib: bitmap: Micro-optimize bitmap_allocate_region Rasmus Villemoes
2014-07-03 22:43 ` [PATCH 16/18] lib: bitmap: Add missing mask in bitmap_shift_right Rasmus Villemoes
2014-07-03 22:43 ` [PATCH 17/18] lib: bitmap: Add missing mask in bitmap_and Rasmus Villemoes
2014-07-03 22:43 ` [PATCH 18/18] lib: bitmap: Add missing mask in bitmap_andnot Rasmus Villemoes
2014-07-07 23:20 ` [PATCH 00/18] lib: bitmap: Various improvements Andrew Morton
2014-07-07 23:45   ` Joe Perches

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®