Making a C code run faster

Question

I have written a piece of code which is used for counting the frequency of numbers between 0 and 255.

unsigned char arr[4096]; //aligned 64 bytes, filled with random characters

short counter[256]; //aligned 32 bytes

register int i;

for(i = 0; i < 4096; i++)
    ++counter[arr[i]];

It is taking a lot of time to execute; the random access to counter array is very expensive.

Does anyone have any ideas which I could use to either make the accesses sequential or any other approach I could use?

Answer 1

What makes you think that random access to the counter array is expensive? Have you profiled? Try Valgrind, which has a cache profiling tool called "cachegrind". Profiling also lets you know if the code is actually slow or if you just think it is slow because it ought to be.

This is a very simple piece of code and before optimizing it is important to know whether it is memory bound or if it is not memory bound (w.r.t. the data, not the histogram table). I can't answer that off the top of my head. Try comparing to a simple algorithm which just sums the entire input: if both run at about the same speed, then your algorithm is memory bound and you are done.

My best guess is that the main issue which could slow you down is this:

   Registers                      RAM
1.  <-- read data[i] ---------------
2.  <-- read histogram[data[i]] ----
3. increment
4.  --- write histogram[data[i]] -->
5.  <-- read data[i] ---------------
6.  <-- read histogram[data[i]] ----

The compiler and processor are not allowed to reorder most of the instructions here (except #1 and #5, which can be done ahead of time) so you are basically going to be limited by whichever is smaller: the bandwidth of your L1 cache (which is where the histogram is) and the bandwidth of your main RAM, each multiplied by some unknown constant factor. (Note: the compiler can only move #1/5 around if it unrolls the loop, but the processor might be able to move it around anyway.)

Which is why you profile before you try to get clever -- because if your L1 cache has enough bandwidth, then you will always be starving for data and there is nothing you can do about it.

Footnote:

This code:

register int i;
for(i = 0; i < 4096; i++)
    ++counter[arr[i]];

Generates the same assembly as this code:

int i;
for(i = 0; i < 4096; i++)
    counter[arr[i]]++;

But this code is easier to read.