On Sat, Dec 5, 2020 at 3:10 AM Rasmus Villemoes <li...@rasmusvillemoes.dk> wrote: > > On 03/12/2020 19.46, Yury Norov wrote: > > > I would prefer to avoid changing the find*bit() semantics. As for now, > > if any of find_*_bit() > > finds nothing, it returns the size of the bitmap it was passed. > > Yeah, we should actually try to fix that, it causes bad code generation. > It's hard, because callers of course do that "if ret == size" check. But > it's really silly that something like find_first_bit needs to do that > "min(i*BPL + __ffs(word), size)" - the caller does a comparison anyway, > that comparison might as well be "ret >= size" rather than "ret == > size", and then we could get rid of that branch (which min() necessarily > becomes) at the end of find_next_bit.
We didn't do that 5 years ago because it's too invasive and the improvement is barely measurable, the difference is 2 instructions (on arm64).e. Has something changed since that? 20000000000000000 <find_first_bit_better>: 0: aa0003e3 mov x3, x0 4: aa0103e0 mov x0, x1 8: b4000181 cbz x1, 38 <find_first_bit_better+0x38> c: f9400064 ldr x4, [x3] 10: d2800802 mov x2, #0x40 // #64 14: 91002063 add x3, x3, #0x8 18: b40000c4 cbz x4, 30 <find_first_bit_better+0x30> 1c: 14000008 b 3c <find_first_bit_better+0x3c> 20: f8408464 ldr x4, [x3], #8 24: 91010045 add x5, x2, #0x40 28: b50000c4 cbnz x4, 40 <find_first_bit_better+0x40> 2c: aa0503e2 mov x2, x5 30: eb00005f cmp x2, x0 34: 54ffff63 b.cc 20 <find_first_bit_better+0x20> // b.lo, b.ul, b.last 38: d65f03c0 ret 3c: d2800002 mov x2, #0x0 // #0 40: dac00084 rbit x4, x4 44: dac01084 clz x4, x4 48: 8b020080 add x0, x4, x2 4c: d65f03c0 ret 0000000000000050 <find_first_bit_worse>: 50: aa0003e4 mov x4, x0 54: aa0103e0 mov x0, x1 58: b4000181 cbz x1, 88 <find_first_bit_worse+0x38> 5c: f9400083 ldr x3, [x4] 60: d2800802 mov x2, #0x40 // #64 64: 91002084 add x4, x4, #0x8 68: b40000c3 cbz x3, 80 <find_first_bit_worse+0x30> 6c: 14000008 b 8c <find_first_bit_worse+0x3c> 70: f8408483 ldr x3, [x4], #8 74: 91010045 add x5, x2, #0x40 78: b50000c3 cbnz x3, 90 <find_first_bit_worse+0x40> 7c: aa0503e2 mov x2, x5 80: eb02001f cmp x0, x2 84: 54ffff68 b.hi 70 <find_first_bit_worse+0x20> // b.pmore 88: d65f03c0 ret 8c: d2800002 mov x2, #0x0 // #0 90: dac00063 rbit x3, x3 94: dac01063 clz x3, x3 98: 8b020062 add x2, x3, x2 9c: eb02001f cmp x0, x2 a0: 9a829000 csel x0, x0, x2, ls // ls = plast a4: d65f03c0 ret > I haven't dug very deep into this, but I could also imagine the > arch-specific parts of this might become a little easier to do if the > semantics were just "if no such bit, return an indeterminate value >= > the size". > > > Changing this for > > a single function would break the consistency, and may cause problems > > for those who > > rely on existing behaviour. > > True. But I think it should be possible - I suppose most users are via > the iterator macros, which could all be updated at once. Changing ret == > size to ret >= size will still work even if the implementations have not > been switched over, so it should be doable. Since there's no assembler users for it, we can do just: #define find_first_bit(bitmap, size) min(better_find_first_bit((bitmap), (size)), (size)) ... and deprecate find_first_bit. > > Passing non-positive size to find_*_bit() should produce undefined > > behaviour, because we cannot dereference a pointer to the bitmap in > > this case; this is most probably a sign of a problem on a caller side > > anyways. > > No, the out-of-line bitmap functions should all handle the case of a > zero-size bitmap sensibly. I could be more specific, the behaviour is defined: don't dereference the address and return undefined value (which now is always 0). > Is bitmap full? Yes (all the 0 bits are set). > Is bitmap empty? Yes, (none of the 0 bits are set). > Find the first bit set (returns 0, there's no such bit) I can't answer because this object is not a map of bits - there's no room for bits inside. > Etc. The static inlines for small_const_nbits do assume that the pointer > can be dereferenced, which is why small_const_nbits was updated to mean > 1<=bits<=BITS_PER_LONG rather than just bits<=BITS_PER_LONG. I don't want to do something like if (size == 0) return -1; ... because it legitimizes this kind of usage and hides problems on callers' side. Instead, I'd add WARN_ON(size == 0), but I don't think it's so critical to bother with it. Yury > Rasmus