performance - Making a C code run faster -

i have written piece of code used counting frequency of numbers between 0 , 255.

unsigned char arr[4096]; //aligned 64 bytes, filled random characters  short counter[256]; //aligned 32 bytes  register int i;  for(i = 0; < 4096; i++)     ++counter[arr[i]]; 

it taking lot of time execute; random access counter array expensive.

does have ideas use either make accesses sequential or other approach use?

what makes think random access counter array expensive? have profiled? try valgrind, has cache profiling tool called "cachegrind". profiling lets know if code slow or if think slow because ought be.

this simple piece of code , before optimizing important know whether memory bound or if not memory bound (w.r.t. data, not histogram table). can't answer off top of head. try comparing simple algorithm sums entire input: if both run @ same speed, algorithm memory bound , done.

my best guess main issue slow down 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 , processor not allowed reorder of instructions here (except #1 , #5, can done ahead of time) going limited whichever smaller: bandwidth of l1 cache (which histogram is) , bandwidth of main ram, each multiplied unknown constant factor. (note: compiler can move #1/5 around if unrolls loop, processor might able move around anyway.)

which why profile before try clever -- because if l1 cache has enough bandwidth, starving data , there nothing can it.

footnote:

this code:

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

generates same assembly code:

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

but code easier read.