I have an array of integers called “count” that is 14348907 in size. I usually look at a few elements of this array and update one element with each iteration of the algorithm. But now I want to add one to the entire array with each iteration. I have found this slows me down by a couple orders of magnitude. The way I do it is by “count = count + 1”. I thought this would be highly efficient, but it isn’t. Is there are faster way?
ps. It seems like looking at an element of an array is faster than changing it. Correct?
No, that should be the same if the array is in L1 cache. Changing it is one extra memory write.
But changing all elements is obviously slower than changing one element. Maybe if you post the code that you are trying to do, and which compiler+options+platform you use, we can help more.
I would modify the algorithm. Adding 1 to every element is not necessary. You should reorganize the rest of the code so that the value that the rest of the code cares about is the result of adding some scalar, call it IEVERY, to an element of the array. Then, you only need to increment the scalar IEVERY.
Updating an array is likely to be slower than just reading it, I believe. There’s more memory traffic, which might not be amenable to latency-hiding (depends what other code is around). Additionally, if the update uses the caches, there is the cost to neighbouring code of reloading the caches. If the update is done (somehow) with a “non-temporal” load (bypassing the caches), you still have the original issue of taking up available memory bandwidth and, possibly, latency too.
You are right. I’ll reorganize the algorithm. I had this stupid hope that if I added one to the whole array it might be able to do it is if it were one operation. Instead of a hundred though individual additions. I was wrong.
That would be a very nice operation for a programmer if it existed, but that is not supported by any current hardware. The Connection Machine of the 1990s might be an exception? On currently available hardware, incrementing an array of length 14348907 requires reading, incrementing, and writing each individual element. There is some opportunity for modest parallelism, based on multiple pipelined vector units and gpu units, but memory bandwidth limits even that to small factors like 4x or 8x speedups. The efficient use of that hardware requires caching and reuse of smaller amounts of memory. So as a rough guide, incrementing 14M elements of an array will cost over a million times the effort of updating a single element or of updating s scalar value which is then used to update individual array elements. Recognizing and implementing these types of algorithm optimizations is one of the most challenging, and rewarding, aspects of programming.