Whamcloud - gitweb
libext2fs: optimize rb_test_bit
authorTheodore Ts'o <tytso@mit.edu>
Fri, 5 Oct 2012 03:38:55 +0000 (23:38 -0400)
committerTheodore Ts'o <tytso@mit.edu>
Thu, 11 Oct 2012 10:30:16 +0000 (06:30 -0400)
commit547a59a821df1cffcd0ca2c763be9ef319cb980b
tree2df7e3847e2a96c52594bd6445a795787881e59d
parentea2d3788621cec5ed067280c7d228ec8897d2208
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>
lib/ext2fs/blkmap64_rb.c