Re: bitmap.c tweeks

[Daniel Berlin <dan at cgsoftware dot com>]

Richard Henderson <rth@redhat.com> writes:

> The recent change to use xmalloc is somewhat less than optimal.
> The rest of the routines in the file allocate the temporary
> directly.
> 
> Also, the use of EXECUTE_IF_SET_IN_BITMAP to search for the last
> bit in the map -- iterating over every bit to get there, note --
> is the worst way this could be done.

Yes.

You could pull off this same optimization
sbitmap_first_set_bit/last_set_bit too, no?

That is where I got that particular piece of code from, after all.

We could also just use a lookup table for the 8 bits or less cases,
using a table of the number of leading zeroes.

I.E. 
static const unsigned char leadingzeroes[256] = {
8, 
7,
6, 6,
5, 5, 5, 5,
4, 4, 4, 4, 4, 4 ,4, 4,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
<four rows of ones>
<all the rest are zeros>
};

Hard to say whether it would be faster than the last part of the
binary search in reality, however.
--Dan


-- 
"When I have a kid, I want to buy one of those strollers for
twins.  Then put the kid in and run around, looking frantic.
When he gets older, I'd tell him he used to have a brother, but
he didn't obey.
"-Steven Wright