tree 2df7e3847e2a96c52594bd6445a795787881e59d
parent ea2d3788621cec5ed067280c7d228ec8897d2208
author Theodore Ts'o <tytso@mit.edu> 1349408335 -0400
committer Theodore Ts'o <tytso@mit.edu> 1349951416 -0400

libext2fs: optimize rb_test_bit

Optimize testing for a bit in an rbtree-based bitmap for the case
where the calling application is scanning through the bitmap
sequentially.  Previously, we did this for a set of bits which were
inside an allocated extent, but we did not optimize the case where
there was a large number of bits after an allocated extents which were
not in use.

             1111111111111110000000000000000000
             ^ optimized    ^not optimized

In my tests of a roughly half-filled file system, the run time of
e2freefrag was halved, and the cpu time spent in userspace was during
e2fsck's pass 5 was reduced by a factor of 30%.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Reviewed-by: Lukas Czerner <lczerner@redhat.com>