very slow array indexing

Question

0.00/5 (No votes)

See more:

Hello everyone,

I have a severe performance decrease when I am accessing random locations in a C-array. So, I have a function which is briefly as follows:

template<typename t="">
int fill_histogram(T *hist)
{
   for (int i = 0; i < num_pixels; ++i)
   {
       valid = true;
       if (some_checks) valid = false;
       if (valid) hist[some_index + (another_index *offset)]++;
   }
}
</typename>

Now, 500 iterations of this take about 130 seconds. When I replace the last line with something like:

if (valid) hist[0]++;

The computation time drops to 30 sec.

The indexes are calculated within the loop at the same time as when I check if the conditions are valid. I am pretty sure nothing is getting optimized away and the array indexing seems to be really slow.

Can I do something to speed this up?

Thanks,

Keith

Posted 18-Nov-10 12:47pm

Keith Vitali

Add a Solution

4 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

AspDotNetDev · Answer 1 · 2010-11-18T13:16:00

If you index by zero, you are removing a multiply and an addition (and perhaps a second addition if you count the addition performed in the pointer arithmetic that may be occurring under the hood) per iteration, which may account for the difference in speed.

Can you calculate the another_index * offset outside of the for loop? Or use additions instead of multiplications? That might help you speed things up.

Keith Vitali · Answer 2 · 2010-11-18T14:02:00

Hi,

It's a bit tricky.

So, to elaborate the function is something as follows:

template<typename t="">
int fill_histogram(T *hist)
{
   for (int i = 0; i < num_pixels; ++i)
   {
       valid = true;
       for(int j = 0; j < someVal; ++j)
       {
          if (some_checks) { valid = false; break; }
          index_1 += value * offset_1[j]);
       }
       for(int j = 0; j < someOtherVal; ++j)
       {
          if (some_checks) { valid = false; break; }
          index_2 += value * offset_2[j]);
       }

       if (valid) hist[index_1 + (index_2 *some_offset)]++;
   }
}
</typename>

I will try and do some simplifications but still quite surprised that these operations almost increase the computation time 3 fold. Was not expecting it to be that slow, somehow.

Cheers,
Keith

Keith Vitali · Answer 3 · 2010-11-18T14:13:00

Solution 3

Ok, it turns out that the real culprit is this line!

<br />
index += static_cast<int>(floorf((float)values[i]) * offsets[i]);<br />

This line seems to slow things down to a halt...Seems excessive, I agree but is the floorf function that slow? Any better way to do this?

Thanks,
K

Posted 18-Nov-10 14:13pm

Keith Vitali

Comments

T2102 18-Nov-10 21:41pm

How many conversions are you performing implicitly on the line above? What are the types?
You also do not need to use static_cast if index is an int already...
If your arrays are small, you should use a struct that has value and offset as a members.
You should profile your page faults to increase speed.

T2102 · Answer 4 · 2010-11-18T16:07:00

You should use only one j variable; not two.
Then you should set j = someOtherVal+1 if not valid.
Get rid of the bool valid and replace with a test for whether j==someOtherVal.
Since false if faster, set it up as
if (j==someOtherVal)
; //do nothing since invalid
else
++hist[index_1 + (index_2 *some_offset)]; //prefix faster than postfix

very slow array indexing

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0

very slow array indexing

4 solutions

Solution 1

Solution 2

Solution 3

Solution 4

Add your solution here

Preview 0

Existing Members

...or Join us