linux-kernel - Re: [PATCH v2 1/8] lib/find_bit.c: Add find_last_zero

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

Message-ID: <CAM7-yPRirVPsFDa37HC8shSwXhk=Bmb490z8=Bs2g0w=A9BhCw@mail.gmail.com>
Date:   Sun, 6 Dec 2020 18:15:32 +0900
From:   Yun Levi <ppbuk5246@...il.com>
To:     Nikolay Borisov <nborisov@...e.com>
Cc:     Greg KH <gregkh@...uxfoundation.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Yury Norov <yury.norov@...il.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        richard.weiyang@...ux.alibaba.com, christian.brauner@...ntu.com,
        Arnd Bergmann <arnd@...db.de>,
        Josh Poimboeuf <jpoimboe@...hat.com>, rdunlap@...radead.org,
        masahiroy@...nel.org, peterz@...radead.org,
        peter.enderborg@...y.com, krzk@...nel.org,
        Brendan Higgins <brendanhiggins@...gle.com>,
        Kees Cook <keescook@...omium.org>, broonie@...nel.org,
        matti.vaittinen@...rohmeurope.com, mhiramat@...nel.org,
        jpa@....mail.kapsi.fi, nivedita@...m.mit.edu,
        Alexander Potapenko <glider@...gle.com>, orson.zhai@...soc.com,
        Takahiro Akashi <takahiro.akashi@...aro.org>, clm@...com,
        Josef Bacik <josef@...icpanda.com>, dsterba@...e.com,
        dushistov@...l.ru,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        linux-arch@...r.kernel.org, linux-btrfs@...r.kernel.org
Subject: Re: [PATCH v2 1/8] lib/find_bit.c: Add find_last_zero_bit

> btrfs' free space cache v1 is going to be removed some time in the
> future so introducing kernel-wide change just for its own sake is a bit
> premature.

Sorry, I don't know about this fact Thanks..

> Also do you have measurements showing it indeed improves
> performances?

I'm not test btrfs' free space cache directly, But I used find_bit_benchmark.c.

here is the result of find_bit_benchmark.

              Start testing find_bit() with random-filled bitmap
[  +0.001874] find_next_bit:                      816326 ns, 163323 iterations
[  +0.000822] find_next_zero_bit:             808977 ns, 164357 iterations
[  +0.000571] find_last_bit:                       561444 ns, 163323 iterations
[  +0.000619] find_last_zero_bit:              609533 ns, 164357 iterations
[  +0.002043] find_first_bit:                       2011390 ns,  16204
iterations
[  +0.000003] find_next_and_bit:                  59 ns,      0 iterations
[  +0.000001]
              Start testing find_bit() with sparse bitmap
[  +0.000068] find_next_bit:                      34573 ns,    653 iterations
[  +0.001691] find_next_zero_bit:            1663556 ns, 327027 iterations
[  +0.000010] find_last_bit:                       7864 ns,    653 iterations
[  +0.001235] find_last_zero_bit:             1216449 ns, 327027 iterations
[  +0.000664] find_first_bit:                 653148 ns,    653 iterations
[  +0.000002] find_next_and_bit:                  44 ns,      0 iterations

as this result, the find_last_zero_bit is a little fast, and logically,
because find_each_clear_bit is iterate till the specified index (i) times,
But find_last_zero_bit in that case call one time
(find_each_clear_bit call i times but find_last_zero_bit call only one time)

So, i think it has a slight improvement.

Thanks.
Levi.

On Sun, Dec 6, 2020 at 6:01 PM Nikolay Borisov <nborisov@...e.com> wrote:
>
>
>
> On 6.12.20 г. 10:56 ч., Yun Levi wrote:
> >> This, and the change above this, are not related to this patch so you
> >> might not want to include them.
> >
> >> Also, why is this patch series even needed?  I don't see a justification
> >> for it anywhere, only "what" this patch is, not "why".
> >
> > I think the find_last_zero_bit will help to improve in
> > 7th patch's change and It can be used in the future.
> > But if my thinking is bad.. Please let me know..
> >
> > Thanks.
> > Levi.
> >
>
> btrfs' free space cache v1 is going to be removed some time in the
> future so introducing kernel-wide change just for its own sake is a bit
> premature. Also do you have measurements showing it indeed improves
> performances?