Re: [PATCH 2/2] libext2fs: optimize rb_test_bit

[Theodore Ts'o <tytso@mit.edu>]

On Mon, Oct 08, 2012 at 10:25:19AM +0200, Lukáš Czerner wrote:
> > the patch and the idea behind it look fine, especially when we're
> > walking the bitmap sequentially not modifying it simultaneously, but
> > I have one question/suggestion below.
> 
> Also for this kind of usage it might actually make sense to have
> something like:
> 
> get_next_zero_bit
> get_next_set_bit
> 
> which would be much more effective than testing single bits, but it
> would require actually using this in e2fsprogs tools.

Yes, I thought about that, and in fact we already have find_first_zero
(which takes a starting offset, so works for both find_first and
find_next).  When we introduced this, though, we accidentally
introduced a bug at first.

At some point I agree it would be good to implement find_first_set(),
and writing new unit tests, and then modify e2freefrag, e2fsck, and
dumpe2fs to use it.  But in the applications is actually pretty
tricky, and I didn't have the time I figured would be necessary to
really do the changes right, and validate/test them properly.

So yes, I agree this would be much more effective, and ultimately
would result in further speedups in e2fsck and e2freefrag in
particular.  It would also allow us to take out the test_bit
optimizations which do have a slight cost for random access reads ---
and this is measurable when looking at the results of the CPU time for
e2fsck pass 4 in particular.  It's just that the performance hit for
the random access test_bit case is very tiny compared with the huge
wins in the sequential scan case.

> > what about using the next_ext once we're holding it to check the bit
> > ? On sequential walk this shout make sense to do so since we
> > actually should hit this if we're not in rcursor nor between rcursor
> > and next_ext.

Yes, I implemented that in the 2/3 commit in the follow-on patch
series.

Cheers!

						 - Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html