Integer vs double arithmetic performance?

Question

Hi,
i'm writing a C# class to perform 2D separable convolution using integers to obtain better performance than double counterpart. The problem is that i don't obtain a real performance gain.

This is the X filter code (it is valid both for int and double cases):

foreach (pixel)
{
      int value = 0;
      for (int k = 0; k < filterOffsetsX.Length; k++)
      {
          value += InputImage[index + filterOffsetsX[k]] * filterValuesX[k];  //index is relative to current pixel position
      }
      tempImage[index] = value;
 }

In the integer case "value", "InputImage" and "tempImage" are of "int", "Image<byte>" and "Image<int>" types.
In the double case "value", "InputImage" and "tempImage" are of "double", "Image<double>" and "Image<double>" types.
(filterValues is int[] in each case)
(The class Image<T> is part of an extern dll. It should be similar to .NET Drawing Image class..).

My goal is to achieve fast perfomance thanks to int += (byte * int) vs double += (double * int)

The following times are mean of 200 repetitions.
Filter size 9 = 0.031 (double) 0.027 (int)
Filter size 13 = 0.042 (double) 0.038 (int)
Filter size 25 = 0.078 (double) 0.070 (int)

The performance gain is minimal. Can this be caused by pipeline stall and suboptimal code?

EDIT: simplified the code deleting unimportant vars.

EDIT2: i don't think i have a cache miss related problema because "index"iterate through adjacent memory cells (row after row fashion). Moreover "filterOffstetsX" contains only small offsets relatives to pixels on the same row and at a max distance of filter size / 2. The problem can be present in the second separable filter (Y-filter) but times are not so different.

Answer 1

at least it is not fair to compare int (DWORD, 4 bytes) and double (QWORD, 8 bytes) on 32-bit system. Compare int to float or long to double to get fair results. double has increased precision, you must pay for it.

PS: for me it smells like micro(+premature) optimization, and that smell is not good.

Edit: Ok, good point. It is not correct to compare long to double, but still comparing int and double on 32 CPU is not correct even if they have both intrinsic instructions. This is not magic, x86 is fat CISC, still double is not processed as single step internally.

Answer 2

It seems like you are saying you are only running that inner loop 5000 times in even your longest case. The FPU last I checked (admittedly a long time ago) only took about 5 more cycles to perform a multiply than the integer unit. So by using integers you would be saving about 25,000 CPU cycles. That's assuming no cache misses or anything else that would cause the CPU to sit and wait in either event.

Assuming a modern Intel Core CPU clocked in the neighborhood of 2.5Ghz, You could expect to have saved about 10 microseconds runtime by using the integer unit. Kinda paltry. I do realtime programming for a living, and we wouldn't sweat that much CPU wastage here, even if we were missing a deadline somewhere.

digEmAll makes a very good point in the comments though. If the compiler and optimizer are doing their jobs, the entire thing is pipelined. That means that in actuality the entire innner loop will take 5 cycles longer to run with the FPU than the Integer Unit, not each operation in it. If that were the case, your expected time savings would be so small it would be tough to measure them.

If you really are doing enough floating-point ops to make the entire shebang take a very long time, I'd suggest looking into doing one or more of the following:

1. Parallelize your algorithm and run it on every CPU available from your processor.
2. Don't run it on the CLR (use native C++, or Ada or Fortran or something).
3. Rewrite it to run on the GPU. GPUs are essentially array processors and are designed to do massively parallel math on arrays of floating-point values.

Answer 3

On my machine, I find that floating-point multiplication is about the same speed as integer multiplication.

I'm using this timing function:

static void Time<T>(int count, string desc, Func<T> action){
    action();

    Stopwatch sw = Stopwatch.StartNew();
    for(int i = 0; i < count; i++)
        action();

    double seconds = sw.Elapsed.TotalSeconds;

    Console.WriteLine("{0} took {1} seconds", desc, seconds);
}

Let's say you're processing a 200 x 200 array with a 25-length filter 200 times, then your inner loop is executing 200 * 200 * 25 * 200 = 200,000,000 times. Each time, you're doing one multiply, one add, and 3 array indices. So I use this profiling code

const int count = 200000000;

int[]  a = {1};
double d = 5;
int    i = 5;

Time(count, "array index", ()=>a[0]);
Time(count, "double mult", ()=>d * 6);
Time(count, "double add ", ()=>d + 6);
Time(count, "int    mult", ()=>i * 6);
Time(count, "int    add ", ()=>i + 6);

On my machine (slower than yours, I think), I get the following results:

array index took 1.4076632 seconds
double mult took 1.2203911 seconds
double add  took 1.2342998 seconds
int    mult took 1.2170384 seconds
int    add  took 1.0945793 seconds

As you see, integer multiplication, floating-point multiplication, and floating-point addition all took about the same time. Array indexing took a little longer (and you're doing it three times), and integer addition was a little faster.

So I think the performance advantage to integer math in your scenario is just too slight to make a significant difference, especially when outweighed by the relatively huge penalty you're paying for array indexing. If you really need to speed this up, then you should use unsafe pointers to your arrays to avoid the offset calculation and bounds checking.

By the way, the performance difference for division is much more striking. Following the pattern above, I get:

double div  took 3.8597251 seconds
int    div  took 1.7824505 seconds

---

One more note:

Just to be clear, all profiling should be done with an optimized release build. Debug builds will be slower overall, and some operations may not have accurate timing with respect to others.

Answer 4

If the times you measuerd are accurate, then the runtime of your filtering algorithm seems to grow with the cube of the filter size. What kind of filter is that? Maybe you can reduce the number of multiplications needed. (e.g. if you're using a separable filter kernel?)

Otherwise, if you need raw performance, you might consider using a library like the Intel Performance Primitives - it contains highly optimized functions for things like this that use CPU SIMD instructions. They're usually a lot faster than hand-written code in C# or C++.

Answer 5

Did you try looking at the disassembled code? In high-level languages i'm pretty much trusting the compiler to optimize my code. For example for(i=0;i<imageSize;i++) might be faster than foreach. Also, arithmetic operrations might get optimized by the compiler anyway.... when you need to optimize something you either optimize the whole "black-box" and maybe reinvent the algorithm used in that loop, or you first take a look at the dissasembled code and see whats wrong with it

Answer 6

Your algorithm seems to access large regions of memory in a very non-sequential pattern. It's probably generating tons of cache misses. The bottleneck is probably memory access, not arithmetic. Using ints should make this slightly faster because ints are 32 bits, while doubles are 64 bits, meaning cache will be used slightly more efficiently. If almost every loop iteration involves a cache miss, though, you're basically out of luck unless you can make some algorithmic or data structure layout changes to improve the locality of reference.

BTW, have you considered using an FFT for convolution? That would put you in a completely different big-O class.