4

I have an array,

int a[size];

I want to set all the array elements to 1

because some of the indexes in the array are already set to 1 so would it better checking each element using a conditional statement like,

for (int index = 0; index < size; index++)
{
    if (a[index] != 1)
      a[index] = 1;
}

or set all the indexes no matter what. what would be the difference?

John
  • 43
  • 1
  • 1
  • 3
  • 6
    Profile and see! – Stephen Jul 29 '10 at 02:45
  • Thanks, I should learn to do that. – John Jul 29 '10 at 02:53
  • Very Sleepy is a good free C profiler if you don't have one on hand. Generally the fewer branches the better so just set them all to 1. – Daniel Jul 29 '10 at 03:06
  • How many of the array elements will already contain a `1`? If it's less than 98 percent, just overwrite them without checking. Otherwise, but only then, you might want to measure which alternative is more efficient. – Roland Illig Jul 29 '10 at 04:44

6 Answers6

15

Your code has two paths in the loop, depending on each value:

  1. Read from array, comparison, and branch
  2. Read from array, comparison, and write

That's not worth it. Just write.

If you want, you can do the same by calling

std::fill(a, a + size, 1);

If the array is of type char instead of int, it will likely call memset. And platform-specific implementations of fill can offer the compiler optimization hints.

Jon Reid
  • 20,545
  • 2
  • 64
  • 95
  • 3
    `std::fill(&a[0], &a[size], 1)` may invoke [undefined behavior](http://stackoverflow.com/questions/3144904/may-i-take-the-address-of-the-one-past-the-end-element-of-an-array-closed), so I would replace it with the kosher version `std::fill(a, a + size, 1)`. – fredoverflow Jul 29 '10 at 05:25
14

Just set all the elements to 1. Code for simplicity and readability first. If you find that the code runs too slow, profile it to see where improvements need to be made (although I highly doubt performance problems can come from setting elements of an array of integers to a certain value).

In silico
  • 51,091
  • 10
  • 150
  • 143
  • And usually the compiler can optimise such routines fairly well, unlike filling an array with pointers to objects constructed during the loop. – Matthew Iselin Jul 29 '10 at 03:00
  • 4
    I should add that either way there will be a memory access and branch operations are relatively expensive on most CPUs, so even without a profiler, simply assigning is likely to be more efficient. – Michael Aaron Safyan Jul 29 '10 at 03:29
5

I'm guessing you are just looking for understanding and not battling a real performance issue... this just wouldn't show up under measurement and here's why:

Normally whenever a cached memory processor (i.e. most of today's desktop CPUs) has to write a value to memory, the cache line that contains the address must be read from (relatively slow) RAM. The value is then modified by a CPU write to the cache. The entire cache line is eventually written back to main RAM.

When you are performing operations over a range of continuous addresses like your array, the CPU will be able to perform several operations very quickly over one cache line before it is written back. It then moves on to the next cache line which was previously fetched in anticipation.

Most likely performing the test before writing the value will not be measurably different than just writing for several reasons:

  1. Branch prediction makes this process extremely efficient.
  2. The compiler will have done some really powerful optimizations.
  3. The memory transfer to cache RAM will be the real rate determining step.

So just write your code for clarity. Measure the difference if you are still curious.

Amardeep AC9MF
  • 18,464
  • 5
  • 40
  • 50
3

Use an std::vector instead.

#include <vector>
...
std::vector<int> a(10, 1);

// access elements just as you would with a C array

std::cout << "Second element is: " << a[1] << std::endl;

Now you have an array of 10 integers all set to 1. If you already have an initialised vector, i.e. a vector filled with values other than one, you can use fill, like this:

#include <algorithm>
...
std::fill(a.begin(), a.end(), 1);
dreamlax
  • 93,976
  • 29
  • 161
  • 209
  • Isn't it too much complication for a simple problem? – user401947 Jul 29 '10 at 06:40
  • @m141: No. What is complicated about it? In the first example, you construct a vector, but rather than initialising with the default value for int (0), you initialise each element with 1. In the second example, the function to do the job is already there (for any iterable). A compiler may be able to determine your intentions much easier if you use the fill function over an array. You should take advantage of C++'s vector unless you can prove it is the bottleneck. – dreamlax Jul 29 '10 at 07:23
  • This gets a `+1` from me, although I would feel much better about it without the `using namespace std;`. See here why: http://stackoverflow.com/questions/2879555/c-stl-how-to-write-wrappers-for-cout-cerr-cin-and-endl/2880136#2880136 – sbi Jul 29 '10 at 07:35
  • @sbi: Ordinarily I would omit the `using namespace std` as well, I just figured it was slightly more readable in this small example. – dreamlax Jul 29 '10 at 07:37
  • IME, _"do as I say, not as I do"_ doesn't work particularly well in teaching. – sbi Jul 29 '10 at 07:52
0

With C++11, you can use a the range-based for to set all values:

int a[size];
for(auto &v: a) {
    v = 1;
}

The &v iterates by reference, so the loop variable is assignable.

This format is a nice alternative to std::fill, and really comes into its own if there if the assignment is a more complicated expression.

Will
  • 73,905
  • 40
  • 169
  • 246
0

I wouldn't expect there to be a noticeable difference unless size is a very large value - however, if you're wanting the optimal variant then just setting all values to 1 would be the more performant option - I'm certain that the conditional will take more time than a simple assignment even if the assignment is then deemed not needed.

Will A
  • 24,780
  • 5
  • 50
  • 61