Static, ReadOnly/Const array in a method

[Martin]

Hi all !

Considering the code below, is it possible to declare this array
static and readonly/const in order to force .NET to allocate this
array only once instead of at each method call. Thank you for your
help !

public static int NbBitsOnOpt(int n)
{
byte[] PreComputedNbBitsOn = new byte[] {0, 1, 1, 2, 1, 2,
2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5,
5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3,
4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4,
3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5,
6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5,
5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6,
7, 7, 8 };
const int NbBits = sizeof(int);
int nbBitsOn = 0;

for (int i = 0; i < NbBits; i++)
{
nbBitsOn += PreComputedNbBitsOn[n & 0xFF];
n >>= 8;
}

return nbBitsOn;
}

 

[Peter Duniho]

Considering the code below, is it possible to declare this array
static and readonly/const in order to force .NET to allocate this
array only once instead of at each method call. Thank you for your
help !

Well, for sure you could make it a static field outside your method.

That said, are we allowed to comment on your algorithm? You'd have to
be spending a LOT of time counting bits for your "always four iteration"
loop to produce a measurable performance improvement over the
less-data-centric "on average, sixteen iteration" algorithm, or even the
brute-force "always thirty-two iteration" version.

Pete

 

[Martin]

Hi Peter,

I agree with you, in that case, there is not a huge performance
improvement. There is an improvement only if the method is called many
time and the array of precomputed data is static and outside the
method. Do you have a better suggestion for counting bits?

Martin

 

[Jon Skeet [C# MVP]]

I agree with you, in that case, there is not a huge performance
improvement. There is an improvement only if the method is called many
time and the array of precomputed data is static and outside the
method. Do you have a better suggestion for counting bits?

I'd suggest using the simplest possible way (maybe bit shifting until
it's zero, being careful of negative numbers) until you run into a
situation where the performance is a bottleneck.

See http://infolab.stanford.edu/~manku/bitcount/bitcount.html for a
page on this though.

 

[Peter Duniho]

I agree with you, in that case, there is not a huge performance
improvement. There is an improvement only if the method is called many
time and the array of precomputed data is static and outside the
method. Do you have a better suggestion for counting bits?

Sure. Though, the page that Jon posted the link to includes the two
options I would have offered, plus more, so I won't bother writing them
here.

I would recommend, absent any specific performance problems, that you just
do the brute-force, shift one bit at a time, incrementing a counter each
time you find a bit set ("Iterated Count" in the linked page). It's
simple, readable, gets the job done, and assuming your program is mostly
doing other things, you will never notice the performance difference.

If you do, by some strange turn of events, discover that you are spending
a significant amount of time in your program counting bits, my next step
would be to look at whether that's really what you meant to do. That is,
unless the work your program does is inherently about counting bits, I'd
expect that spending a lot of time counting bits means that you're
probably just counting bits more often than you really need to. Reworking
the algorithm so that you really only count bits when you have to is
likely to fix that performance issue.

Finally, if after all that analysis, you decide that yes, you really need
to be counting bits as part of a major component of your processing, then
you go with the table-driven lookup method. Given how much RAM you can
have these days, you might even consider using a 16-bit table instead of
an 8-bit one. It'll double your performance (after you initialize the
table...you should probably just write a loop that initializes the table
by brute force at the beginning of your program, rather than hard-coding
all the values), and will still only take up 64K (small potatoes these
days). I doubt it would come to that though.

Pete