Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756033AbbBDXHc (ORCPT ); Wed, 4 Feb 2015 18:07:32 -0500 Received: from mail-la0-f48.google.com ([209.85.215.48]:50355 "EHLO mail-la0-f48.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755909AbbBDXHa (ORCPT ); Wed, 4 Feb 2015 18:07:30 -0500 Message-ID: <54D2A62B.5090104@gmail.com> Date: Thu, 05 Feb 2015 02:07:23 +0300 From: Yury User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 MIME-Version: 1.0 To: George Spelvin , akpm@linux-foundation.org, chris@chris-wilson.co.uk, davem@davemloft.net, dborkman@redhat.com, hannes@stressinduktion.org, klimov.linux@gmail.com, laijs@cn.fujitsu.com, msalter@redhat.com, takahiro.akashi@linaro.org, tgraf@suug.ch, valentinrothberg@gmail.com CC: linux-kernel@vger.kernel.org, y.norov@samsung.com, Yury Norov Subject: Re: [PATCH v2 1/3] lib: find_*_bit reimplementation References: <20150202031714.29052.qmail@ns.horizon.com> In-Reply-To: <20150202031714.29052.qmail@ns.horizon.com> Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2007 Lines: 46 On 02.02.2015 06:17, George Spelvin wrote: > Yury Norov wrote: >> New implementations takes less space in source file (see diffstat) >> and in object. For me it's 710 vs 453 bytes of text. >> >> Patch was boot-tested on x86_64 and MIPS (big-endian) machines. >> Performance tests were ran on userspace with code like this: >> >> /* addr[] is filled from /dev/urandom */ >> start = clock(); >> while (ret < nbits) >> ret = find_next_bit(addr, nbits, ret + 1); >> >> end = clock(); >> printf("%ld\t", (unsigned long) end - start); >> On Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz rezults are next: >> (for find_next_bit, nbits is 8M, for find_first_bit - 80K) >> >> find_next_bit: find_first_bit: >> new current new current >> 26932 43151 14777 14925 >> 26947 43182 14521 15423 > I'll look at this more carefully, but one immediate thought is that this > is an unrealistic benchmark. It will amost never need to look at more > than one word of the array, but real arrays have long runs of zero > bits to skip over. > > So the code size is appreciated, but the time benefits may be the result > of you optimizing for the wrong thing. > > I'd try filling the array with mostly-identical bits, flipping with odds > of 1/256 or so. > > For full generality, I'd test different 1->0 and 0->1 transition > probabilities. (But powers of two are probably enough for benchmarking.) > I think, test with random values represents at least one situation: well-fragmented memory after long time work. (This is what I really have in my project.) In other hand, if long zero runs is a typical behavior for one's system, it's a good opportunity for improvements, I think. Anyway, the idea of testing find_bit on a long runs is good. Thank you. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/