Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Alice Ryhl <aliceryhl@google.com>]

On Fri, Apr 25, 2025 at 06:17:59PM +0200, Burak Emir wrote:
> On Fri, Apr 25, 2025 at 3:45 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > On Fri, Apr 25, 2025 at 02:20:13PM +0200, Burak Emir wrote:
> > > On Fri, Apr 25, 2025 at 12:31 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > >
> > > > On Thu, Apr 24, 2025 at 09:48:17AM -0700, Boqun Feng wrote:
> > > > > On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> > > > > > On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > > > > So? Can you show your numbers?
> > > > > >
> > > > > > For now, I only have numbers that may not be very interesting:
> > > > > >
> > > > > > - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
> > > > > >   22 ns/iteration in C, 32 ns/iteration in Rust.
> > > > > >
> > > > > > - for sparse find_next_bit (sparse):
> > > > > >   60 ns/iteration in C, 70 ns/iteration in Rust.
> > > > > >
> > > > > > This is a VM running nested in a VM. More importantly: the C helper
> > > > > > method is not inlined.
> > > > > > So we are likely measuring the overhead (plus the extra bounds checking).
> 
> Alice and I discussed that it may be better to do away with the extra
> bounds check.
> Micro benchmark, for the upcoming v8 that has the bounds check removed
> (and the test changed to >=, as requested):
> 
> [] Start testing find_bit() with random-filled bitmap
> [] find_next_bit:                 3598165 ns, 164282 iterations
> [] find_next_zero_bit:            3626186 ns, 163399 iterations
> [] Start testing find_bit() with sparse bitmap
> [] find_next_bit:                   40865 ns,    656 iterations
> [] find_next_zero_bit:            7100039 ns, 327025 iterations
> [] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
> random-filled bitmap
> [] find_bit_benchmark_rust_module: next_bit:
> 4572086 ns, 164112 iterations
> [] find_bit_benchmark_rust_module: next_zero_bit:
> 4582930 ns, 163569 iterations
> [] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
> sparse bitmap
> [] find_bit_benchmark_rust_module: next_bit:
> 42622 ns,    655 iterations
> [] find_bit_benchmark_rust_module: next_zero_bit:
> 8835122 ns, 327026 iterations

By the way, if you add assert_eq!(bitmap.len(), BITMAP_LEN) before the
loop you may get the bounds checks optimized out.

Alice