Making a C code run faster

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.

More idiomatic:

// make sure you actually fill this with random chars // if this is declared in a function, it _might_ have stack garbage // if it's declared globally, it will be zeroed (which makes for a boring result) unsigned char arr[4096]; // since you're counting bytes in an array, the array can't have more // bytes than the current system memory width, so then size_t will never overflow // for this usage size_t counter[256]; for(size_t i = 0; i < sizeof(arr)/sizeof(*arr); ++i) ++counter[arr[i]]; 

Now the key is to compile with C99, and some serious optimization flags:

cc mycode.c -O3 -std=c99 

Any optimization at all on a simple loop like this will make it extremely quick. Don't waste more time on making something this simple faster.

First, I complete agree with Dietrich, please prove (yourself and us) where the real bottleneck lies, first.

The only possible improvement I can see is in your short. The size of the table will not be a problem here, I guess, but promotions and overflow. Use a type that handles this by default, namely unsigned.

Anyhow, counters should always be unsigned (even better size_t), this is the semantic of cardinalities. As an extra advantage unsigned types don't overflow, but wrap a arround in a controled way. The compiler doesn't have to use an additional instruction for that.

Then arithmetic in C is done with a width of at least that of int. This then has to be cast back to short.

the code takes a data of size 4k...it adds every 3 consecutive bytes and stores the result in a temporary buffer of size 4k. The temporary buffer is used for the generation of the histogram.

Vectorization is possible for the addition of 3 consecutive bytes which I did using SIMD instructions.

As per what Dietrich suggested, if instead of doing generating the histogram, I simply added the values in the temporary buffer, it executes very fast. But generation of histogram is the part which takes time. I did the profiling of the code using cache grind...the output is:

==11845== ==11845== I refs: 212,171 ==11845== I1 misses: 842 ==11845== LLi misses: 827 ==11845== I1 miss rate: 0.39% ==11845== LLi miss rate: 0.38% ==11845== ==11845== D refs: 69,179 (56,158 rd + 13,021 wr) ==11845== D1 misses: 2,905 ( 2,289 rd + 616 wr) ==11845== LLd misses: 2,470 ( 1,895 rd + 575 wr) ==11845== D1 miss rate: 4.1% ( 4.0% + 4.7% ) ==11845== LLd miss rate: 3.5% ( 3.3% + 4.4% ) ==11845== ==11845== LL refs: 3,747 ( 3,131 rd + 616 wr) ==11845== LL misses: 3,297 ( 2,722 rd + 575 wr) ==11845== LL miss rate: 1.1% ( 1.0% + 4.4% ) 

and the complete output is:

I1 cache: 65536 B, 64 B, 2-way associative D1 cache: 65536 B, 64 B, 2-way associative LL cache: 1048576 B, 64 B, 16-way associative Command: ./a.out Data file: cachegrind.out.11845 Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Thresholds: 0.1 100 100 100 100 100 100 100 100 Include dirs: User annotated: Auto-annotation: off -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 212,171 842 827 56,158 2,289 1,895 13,021 616 575 PROGRAM TOTALS -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function -------------------------------------------------------------------------------- 97,335 651 642 26,648 1,295 1,030 10,883 517 479 ???:??? 59,413 13 13 13,348 886 829 17 1 0 ???:_dl_addr 40,023 7 7 12,405 10 8 223 18 17 ???:core_get_signature 5,123 2 2 1,277 64 19 256 64 64 ???:core_get_signature_parallel 3,039 46 44 862 9 4 665 8 8 ???:vfprintf 2,344 11 11 407 0 0 254 1 1 ???:_IO_file_xsputn 887 7 7 234 0 0 134 1 0 ???:_IO_file_overflow 720 9 7 250 5 2 150 0 0 ???:__printf_chk 538 4 4 104 0 0 102 2 2 ???:__libc_memalign 507 6 6 145 0 0 114 0 0 ???:_IO_do_write 478 2 2 42 1 1 0 0 0 ???:strchrnul 350 3 3 80 0 0 50 0 0 ???:_IO_file_write 297 4 4 98 0 0 23 0 0 ???:_IO_default_xsputn 

Well, Richard is certainly right. This is because the compiler has to convert the array to pointer, but that takes some time, thus increasing execution time. For instance, try this:

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