2

I have a function which receives a one-dimensional array and a number from a user and adds these two together.

Sample:

0 1 2 3 4 5 6 7 8

User : 9

9 10 11 12 13 14 ...

I've been using the following code:

for(int i =0; i < arr; i++){
   arr[i] = arr[i] + usrNumber;
}

Now this seems terribly inefficient as I have to essentially iterate through every single position of the array and add the values together.

I have read of the block method from a previous post but I was under the impression that it had to be at least two-dimensional for it to work. What is a way to improve this function?

Community
  • 1
  • 1
Kadana Kanz
  • 177
  • 2
  • 11
  • 1
    For a 1D array, I don't think you can do better; essentially you're already benefiting from what you've mentioned, see here: http://stackoverflow.com/questions/12065774/why-does-cache-locality-matter-for-array-performance – user4520 May 21 '15 at 06:47
  • Well you are under correct impression, the block method is used for 2-D arrays since the arrays are generally stored in a row-major fashion. So if they are accessed in a column major fashion, then it may result in a lot of cache misses – Nishant May 21 '15 at 06:47

1 Answers1

2

Your code already has excellent spatial locality. Spatial locality is defined as

If a particular memory location is referenced at a particular time, then it is likely that nearby memory locations will be referenced in the near future. (Wikipedia)

The easiest way to do better is to use your processors's vector instructions, assuming the processor has them and the compiler doesn't do it for you. For example, x86 processors have SSE instructions that can speed what you are doing.

If the array is big enough, then you could do cache prefetching if the processor supports it. Note that Intel processors made in the last few years do this automatically.

Craig S. Anderson
  • 6,966
  • 4
  • 33
  • 46
  • hmmmmmm ok will have to research on SSE instructions. – Kadana Kanz May 21 '15 at 06:59
  • It'd probably be wise to make use of your profiler to determine whether or not this piece of code is even a minor bottleneck, let alone a major one, before trying to manually optimise it. – autistic May 21 '15 at 08:50