Re: [patch] bitmap.c: Speed up bitmap_find_bit.

[Diego Novillo <dnovillo at redhat dot com>]

On Thu, 2004-11-25 at 09:29 -0700, Jeffrey A Law wrote:
> On Thu, 2004-11-25 at 00:05 -0500, Kazu Hirata wrote:
> > Hi,
> > 
> > Attached is a patch to speed up bitmap_find_bit.
> > 
> > Currently, bitmap_find_bit always traverses from head->current.  This
> > approach tends to be slow if the we are looking for a bit that's
> > closer to the beginning of the bitmap than to the "current element" of
> > the bitmap.
> > 
> > The patch adds another way of traversal, namely from head->first.  We
> > choose to traverse from head->first when the index of the element that
> > contains the bit we are after is less than half of head->indx.
> Before you install that patch you might do well to look at places
> where we are doing random or semi-random queries into the bitmaps.
> You'll likely get bigger improvements by avoiding the random
> bitmap queries rather than by twidding the bitmap code itself.
> 
True, but we should also try and optimize the data structure itself.  We
can't always avoid random accesses to bitmaps.

Perhaps we should have another instance of bitmaps more streamlined for
non-linear references?


Diego.