From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758023AbbBEPBb (ORCPT ); Thu, 5 Feb 2015 10:01:31 -0500 Received: from mail-lb0-f169.google.com ([209.85.217.169]:47948 "EHLO mail-lb0-f169.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757669AbbBEPB3 (ORCPT ); Thu, 5 Feb 2015 10:01:29 -0500 From: Rasmus Villemoes To: Yury Cc: klimov.linux@gmail.com, davem@davemloft.net, akpm@linux-foundation.org, hannes@stressinduktion.org, dborkman@redhat.com, laijs@cn.fujitsu.com, takahiro.akashi@linaro.org, valentinrothberg@gmail.com, linux@horizon.com, msalter@redhat.com, chris@chris-wilson.co.uk, tgraf@suug.ch, linux-kernel@vger.kernel.org, Yury Norov Subject: Re: [PATCH v2 1/3] lib: find_*_bit reimplementation Organization: D03 References: <1422737907-26114-1-git-send-email-yury.norov@gmail.com> <878uggr3tm.fsf@rasmusvillemoes.dk> <54D2A2B9.1020206@gmail.com> X-Hashcash: 1:20:150205:chris@chris-wilson.co.uk::vhVyx74PhIaVTayi:00000000000000000000000000000000000000u/E X-Hashcash: 1:20:150205:takahiro.akashi@linaro.org::FhtJ0fp/xT9Z1/23:000000000000000000000000000000000000Rwl X-Hashcash: 1:20:150205:yury.norov@gmail.com::91q6ZOUfBaNiFLjX:000000000000000000000000000000000000000001MtK X-Hashcash: 1:20:150205:davem@davemloft.net::xw3dByYYKih2qbey:0000000000000000000000000000000000000000001jeH X-Hashcash: 1:20:150205:laijs@cn.fujitsu.com::bIrwCxVo4lI/1u3v:000000000000000000000000000000000000000001hop X-Hashcash: 1:20:150205:akpm@linux-foundation.org::o1X6McPL6B4lCwm3:0000000000000000000000000000000000001+9G X-Hashcash: 1:20:150205:linux-kernel@vger.kernel.org::gbf6L9OeJ+GS473b:0000000000000000000000000000000002brP X-Hashcash: 1:20:150205:dborkman@redhat.com::66DbOpCkp1q+YHt4:0000000000000000000000000000000000000000002K6e X-Hashcash: 1:20:150205:hannes@stressinduktion.org::NawYrb17tC5IbwPn:0000000000000000000000000000000000037fG X-Hashcash: 1:20:150205:msalter@redhat.com::JDIM7Moz/TEoXJQ9:0000000000000000000000000000000000000000000308U X-Hashcash: 1:20:150205:linux@horizon.com::M4rtmFRWDqqx4Thc:000000000000000000000000000000000000000000003nOf X-Hashcash: 1:20:150205:valentinrothberg@gmail.com::PNuNr+vXOf9XSAjq:000000000000000000000000000000000005Io6 X-Hashcash: 1:20:150205:y.norov@samsung.com::B56SfGJHSK2ZH1JS:0000000000000000000000000000000000000000004jtM X-Hashcash: 1:20:150205:tgraf@suug.ch::OeLMwN7+KygqTIX9:00006z6o X-Hashcash: 1:20:150205:klimov.linux@gmail.com::gNuaxr/GbVpCCX9m:000000000000000000000000000000000000000DJYT Date: Thu, 05 Feb 2015 16:01:26 +0100 In-Reply-To: <54D2A2B9.1020206@gmail.com> (Yury's message of "Thu, 05 Feb 2015 01:52:41 +0300") Message-ID: <87pp9os8qh.fsf@rasmusvillemoes.dk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Wed, Feb 04 2015, Yury wrote: > On 02.02.2015 13:43, Rasmus Villemoes wrote: >>> @@ -23,86 +50,22 @@ >>> unsigned long find_next_bit(const unsigned long *addr, unsigned long size, >>> unsigned long offset) >>> { >>> - const unsigned long *p = addr + BITOP_WORD(offset); >>> - unsigned long result = offset & ~(BITS_PER_LONG-1); >>> - unsigned long tmp; >>> - >>> if (offset >= size) >>> return size; >> Why can't this ... >> >> >>> - size -= result; >>> - offset %= BITS_PER_LONG; >>> - if (offset) { >>> - tmp = *(p++); >>> - tmp &= (~0UL << offset); >>> - if (size < BITS_PER_LONG) >>> - goto found_first; >>> - if (tmp) >>> - goto found_middle; >>> - size -= BITS_PER_LONG; >>> - result += BITS_PER_LONG; >>> - } >>> - while (size & ~(BITS_PER_LONG-1)) { >>> - if ((tmp = *(p++))) >>> - goto found_middle; >>> - result += BITS_PER_LONG; >>> - size -= BITS_PER_LONG; >>> - } >>> - if (!size) >>> - return result; >>> - tmp = *p; >>> >>> -found_first: >>> - tmp &= (~0UL >> (BITS_PER_LONG - size)); >>> - if (tmp == 0UL) /* Are any bits set? */ >>> - return result + size; /* Nope. */ >>> -found_middle: >>> - return result + __ffs(tmp); >>> + return min(_find_next_bit(addr, size, offset, 1), size); >> ... and this be part of _find_next_bit? Can find_next_bit not be simply >> 'return _find_next_bit(addr, size, offset, 1);', and similarly for >> find_next_zero_bit? Btw., passing true and false for the boolean >> parameter may be a little clearer. > I moved size checkers out of '_find_next_bit' to let user call it from his code > if he knows for sure that size/offset pair is valid. This may help save a couple > of clocks. I think, I'll walk over the code to find how many such places we have. > If not too much / not in critical paths, checks may be moved into the function. But _find_next_bit is static, so outsiders can't call it... The branches are easily predicted and hence almost free, so I think it's better to do the code deduplication and move the bounds checking inside _find_next_bit, so that find_next_bit is literally just 'return _find_next_bit(addr, size, offset, 0ul);' and find_next_zero_bit is 'return _find_next_bit(addr, size, offset, ~0ul);'. Rasmus