Algorithm: taking out every 4th item of an array

Question

I have two huge arrays (int source[1000], dest[1000] in the code below, but having millions of elements in reality). The source array contains a series of ints of which I want to copy 3 out of every 4.

For example, if the source array is:

int source[1000] = {1,2,3,4,5,6,7,8....};
int dest[1000];

Here is my code:

for (int count_small = 0, count_large = 0; count_large < 1000; count_small += 3, count_large +=4)
    {
      dest[count_small] = source[count_large];
      dest[count_small+1] = source[count_large+1];
      dest[count_small+2] = source[count_large+2];
    }

In the end, dest console output would be:

1 2 3 5 6 7 9 10 11...

But this algorithm is so slow! Is there an algorithm or an open source function that I can use / include?

Thank you :)

Edit: The actual length of my array would be about 1 million (640*480*3)

Edit 2: Processing this for loop takes about 0.98 seconds to 2.28 seconds, while the other code only take 0.08 seconds to 0.14 seconds, so the device uses at least 90 % cpu time only for the loop

Answer 1

You could try memcpy instead of the individual assignments:

memcpy(&dest[count_small], &source[count_large], sizeof(int) * 3);

Answer 2

Well, the asymptotic complexity there is as good as it's going to get. You might be able to achieve slightly better performance by loading in the values as four 4-way SIMD integers, shuffling them into three 4-way SIMD integers, and writing them back out, but even that's not likely to be hugely faster.

With that said, though, the time to process 1000 elements (Edit: or one million elements) is going to be utterly trivial. If you think this is the bottleneck in your program, you are incorrect.

Answer 3

Before you do much more, try profiling your application and determine if this is the best place to spend your time. Then, if this is a hot spot, determine how fast is it, and how fast you need it to be/might achieve? Then test the alternatives; the overhead of threading or OpenMP might even slow it down (especially, as you now have noted, if you are on a single core processor - in which case it won't help at all). For single threading, I would look to memcpy as per Sean's answer.

@Sneftel has also reference other options below involving SIMD integers.

One option would be to try parallel processing the loop, and see if that helps. You could try using the OpenMP standard (see Wikipedia link here), but you would have to try it for your specific situation and see if it helped. I used this recently on an AI implementation and it helped us a lot.

#pragma omp parallel for
for (...)
{
   ... do work
}

Other than that, you are limited to the compiler's own optimisations.

You could also look at the recent threading support in C11, though you might be better off using pre-implemented framework tools like parallel_for (available in the new Windows Concurrency Runtime through the PPL in Visual Studio, if that's what you're using) than rolling your own.

parallel_for(0, max_iterations,
    [...] (int i)
    {
        ... do stuff
    }
);

Inside the for loop, you still have other options. You could try a for loop that iterates and skips every for, instead of doing 3 copies per iteration (just skip when (i+1) % 4 == 0), or doing block memcopy operations for groups of 3 integers as per Seans answer. You might achieve slightly different compiler optimisations for some of these, but it is unlikely (memcpy is probably as fast as you'll get).

for (int i = 0, int j = 0; i < 1000; i++)
{
  if ((i+1) % 4 != 0)
  { 
    dest[j] = source[i];
    j++;
  }
}

You should then develop a test rig so you can quickly performance test and decide on the best one for you. Above all, decide how much time is worth spending on this before optimising elsewhere.

Answer 4

Is your array size only a 1000? If so, how is it slow? It should be done in no time! As long as you are creating a new array and for a single threaded application, this is the only away AFAIK.

However, if the datasets are huge, you could try a multi threaded application.

Also you could explore having a bigger data type holding the value, such that the array size decreases... That is if this is viable to your real life application.

Answer 5

If you have Nvidia card you can consider using CUDA. If thats not the case you can try other parallel programming methods/environments as well.