Byte comparison uses so much CPU

Question

Well i have this function to compare Red, Blue, Green, and Alpha Pixels in an image comparison for loop comparing two images

Code:

var o = 255 - c1.A;
var t = tolerance < o ? o : tolerance;
var b = AreSimiliar(ref c1.B, ref c2.B, ref t);
var g = AreSimiliar(ref c1.G, ref c2.G, ref t);
var r = AreSimiliar(ref c1.R, ref c2.R, ref t);
if (b && g && r) continue;

[MethodImpl(MethodImplOptions.AggressiveInlining)] 
private static bool AreSimiliar(ref byte v1, ref byte v2, ref double tolerance)
{
    var z = v1 - v2;
    var t = z > 0 ? z : -z;
    return t <= tolerance;
}

The problem is it uses so much CPU although no external code is being used, and testing narrowed it down to that code that causes the load.

I doubt it will be useful to optimize just this code. Likely any realistic optimization will require looking carefully at the surrounding code as well. — David Schwartz, Mar 01 '16 at 01:05
dont use ref on byte unless you want to change them ... your passing a pointer of 32 bit or 64 bit instead of 8 bits... in fact remove all ref from that method — Fredou, Mar 01 '16 at 01:09
Also, `tolerance` could be an int since the delta will be as well. — 500 - Internal Server Error, Mar 01 '16 at 01:10
Using CPU just means its doing something. What's the problem? — Jon Hanna, Mar 01 '16 at 01:40
Can you change the tolerance type into byte, at least for AreSimilar? Since you don't seem to use it for division, byte should do the job faster. Heck you could just XOR both images as byte array to find the difference, then run threshold operation on the difference image with tolerance array. — Martheen, Mar 01 '16 at 02:29

Fredou · Answer 1 · 2016-03-01T01:53:14.130

2

try this instead

var o = 255 - c1.A;
var t = tolerance < o ? o : tolerance;
if (AreSimiliar(c1.B, c2.B, t) && 
    AreSimiliar(c1.G, c2.G, t) &&
    AreSimiliar(c1.R, c2.R, t)) continue;

[MethodImpl(MethodImplOptions.AggressiveInlining)] 
private static bool AreSimiliar(byte v1, byte v2, double tolerance)
{
    var z = v1 - v2;
    var t = z > 0 ? z : -z;
    return t <= tolerance;
}

this might be even better

        var o = 255 - c1.A;
        var t = tolerance < o ? o : tolerance;
        if (Abs(c1.B - c2.B) <= t) & //or &&
            Abs(c1.G - c2.G) <= t) & //or &&
            Abs(c1.R - c2.R) <= t)) continue;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int Abs(int d)
    {
        int y = (d >> 31);

        return (d ^ y) - y;
    }

edited Mar 01 '16 at 01:53

answered Mar 01 '16 at 01:12

Fredou

19,848
10
58
113

2

Using `&&` to shortcircuit the actual calculation rather than the comparison of the results should speed it up nicely! – stuartd Mar 01 '16 at 01:13
It would also be worthwhile profiling the opposite, of using `&` to avoid the branching that `&&` adds. The code in the question was the worse of both worlds (duplicate effort AND branching), but the work done in `AreSimilar` is neither large enough to make short-circuiting the no-brainer obvious choice nor small enough to make avoiding the branch the no-brainer obvious choice, so it would be worth profiling both with realistic data. – Jon Hanna Mar 01 '16 at 01:43
@JonHanna, agree, added another possible solution – Fredou Mar 01 '16 at 01:53
Could it run faster if t is a byte so all comparisons are between bytes? – Martheen Mar 01 '16 at 02:44
@Martheen byte - byte = int so what is best? casting a int to byte or keeping everything at int? good question benchmark would tell – Fredou Mar 01 '16 at 03:09
The problem is after testing your code i still get 20~30% cpu usage and that is insanely high for an application – Ahmed T. Yousef Mar 01 '16 at 05:56
@AhmedT.Yousef you cannot achieve 0% and depend on the computer it is run and finally it depend what the application do. at that point it's up to you to find what else can be optimized. this answer is for this question only. – Fredou Mar 01 '16 at 15:54

score 0 · Answer 2 · answered Mar 01 '16 at 01:17

0

make your code branch free

use native SIMD (avx,sse) code https://en.wikipedia.org/wiki/SIMD

answered Mar 01 '16 at 01:17

Multivac

56
6

1

It's not clear what SIMD support .NET has; what steps are required by DEVs to enable it; and what types support it. http://www.drdobbs.com/windows/64-bit-simd-code-from-c/240168851 and http://stackoverflow.com/questions/31906215/how-to-enable-simd-in-a-new-net-framework-4-6. Quite exciting though – Mar 01 '16 at 01:23

Byte comparison uses so much CPU

2 Answers2