Iteration through ILArray<double> is very slow

Question

When I tried to profile a slow optimization algorithm, I discovered that the following method is taking much longer than expected:

protected virtual bool Dominates(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> p1In = p1;
        ILArray<double> p2In = p2;
        bool strong = false;
        for (int i = 0; i < nObjectives; i++)
        {
            using (ILScope.Enter())
            {
                if (p1In[i] > p2In[i])
                    strong = true;
                else if (p1In[i] < p2In[i])
                {
                    return false;
                }
            }
        }
        return strong;
    }
}

I then replaced it with the following implementation and the speed increases by a huge multiple.

protected virtual bool DominatesSys(double[] p1, double[] p2, int nObjectives)
{
    bool strong = false;
    for (int i = 0; i < nObjectives; i++)
    {
        if (p1[i] > p2[i])
            strong = true;
        else if (p1[i] < p2[i])
        {
            return false;
        }
    }
    return strong;
}

I don't understand it and tried to write a test to compare the difference. Below is the test code used:

[Test]
public void TestILNumericsSpeed()
{
    ILArray<double> p1Il = ILMath.rand(100);
    ILArray<double> p2Il = p1Il - 0.01;
    double[] p1 = p1Il.GetArrayForRead();
    double[] p2 = p2Il.GetArrayForRead();
    int length = p1.Length;
    Func<bool> func1 = () =>
        {
            Dominates(p1Il, p2Il, length);
            return true;
        };
    Func<bool> func2 = () =>
        {
            DominatesSys(p1, p2, length);
            return true;
        };
    var stats1 = CollectStats(func1, 20, 1000);
    var stats2 = CollectStats(func2, 20, 1000);
    log.InfoFormat("Mean time taken by ILNumerics = {0}.", stats1.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by system array = {0}.", stats2.Skip(1).Average(t => t.TotalSeconds));
}

protected virtual IList<TimeSpan> CollectStats(Func<bool> func, int n = 100, int nPerRound = 100)
{
    Stopwatch watch = new Stopwatch();
    var stats1 = new List<TimeSpan>();
    watch.Reset();
    for (int i = 0; i < n; i++)
    {
        using (ILScope.Enter())
        {
            watch.Reset();
            watch.Start();
            for (int j = 0; j < nPerRound; j++)
            {
                bool ret = func();
                Assert.IsTrue(ret);
            }
            watch.Stop();
            stats1.Add(watch.Elapsed);
        }
    }
    return stats1;
}

I was quite shocked by the bizarre result obtained. I expected ILArray to be a little slower than system array in terms of sequential indexing, but 1000 times is too much. Can someone help diagnose my problem here:

[INFO ] | 14:38:19,974 | [odes] |         NumericsTest   383 | Mean time taken by ILNumerics = 0.294103963157895.
[INFO ] | 14:38:20,036 | [odes] |         NumericsTest   383 | Mean time taken by system array = 0.000271984210526316.

---

Following Haymo's suggestions, the following test is run to compare the speed of different implementations. I think in this case, since no intermediate arrays need to be created using DominatesSys, its performance is the fastest.

[Test]
public void TestILNumericsSpeed()
{
    ILArray<double> p1Il = ILMath.rand(1000);
    ILArray<double> p2Il = p1Il - 0.01;
    double[] p1 = p1Il.GetArrayForRead();
    double[] p2 = p2Il.GetArrayForRead();
    int length = p1Il.S[0];
    Func<bool> func1 = () =>
        {
            Dominates1(p1Il, p2Il, length);
            return true;
        };
    Func<bool> func2 = () =>
        {
            Dominates2(p1Il, p2Il, length);
            return true;
        };
    Func<bool> func3 = () =>
        {
            Dominates3(p1Il, p2Il, length);
            return true;
        };
    Func<bool> func4 = () =>
    {
        Dominates4(p1Il, p2Il, length);
        return true;
    };
    Func<bool> func5 = () =>
    {
        Dominates5(p1Il, p2Il, length);
        return true;
    };
    Func<bool> funcSys = () =>
        {
            DominatesSys(p1, p2, length);
            return true;
        };
    var stats1 = IO.CollectStats(func1, 10, 1000);
    var stats2 = IO.CollectStats(func2, 10, 1000);
    var stats3 = IO.CollectStats(func3, 10, 1000);
    var stats4 = IO.CollectStats(func4, 10, 1000);
    var stats5 = IO.CollectStats(func5, 10, 1000);
    var statsSys = IO.CollectStats(funcSys, 10, 1000);
    log.InfoFormat("Mean time taken by Dominates1 = {0}.", stats1.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by Dominates2 = {0}.", stats2.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by Dominates3 = {0}.", stats3.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by Dominates4 = {0}.", stats4.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by Dominates5 = {0}.", stats5.Skip(1).Average(t => t.TotalSeconds));
    log.InfoFormat("Mean time taken by system array = {0}.", statsSys.Skip(1).Average(t => t.TotalSeconds));
}

protected virtual bool Dominates1(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> p1In = p1;
        ILArray<double> p2In = p2;
        bool strong = false;
        for (int i = 0; i < nObjectives; i++)
        {
            using (ILScope.Enter())
            {
                if (p1In[i] > p2In[i])
                    strong = true;
                else if (p1In[i] < p2In[i])
                {
                    return false;
                }
            }
        }
        return strong;
    }
}

protected virtual bool Dominates2(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> n = p1[r(0, nObjectives - 1)] - p2[r(0, nObjectives - 1)];
        if (any(n < 0)) return false;
        return any(n > 0);
    }
}

protected virtual bool Dominates3(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> n = p1[r(0, nObjectives - 1)] - p2[r(0, nObjectives - 1)];
        var strong = false;
        foreach (var d in n)
        {
            if (d < 0) return false;
            if (d > 0) strong = true;
        }
        return strong;
    }
}

protected virtual bool Dominates4(ILInArray<double> p1, ILInArray<double> p2, int nObjectives)
{
    using (ILScope.Enter(p1, p2))
    {
        ILArray<double> p1In = p1;
        ILArray<double> p2In = p2;
        bool strong = false;
        for (int i = 0; i < nObjectives; i++)
        {
            using (ILScope.Enter()) {  // probably does not help with such tiny arrays ...
                if (p1In.GetValue(i) > p2In.GetValue(i))
                    strong = true;
                else if (p1In.GetValue(i) < p2In.GetValue(i))
                {
                    return false;
                }
            }
        }
        return strong;
    }
}

protected virtual bool Dominates5(ILArray<double> p1, ILArray<double> p2, int nObjectives)
{
    bool strong = false;
    for (int i = 0; i < nObjectives; i++)
    {
        if (p1.GetValue(i) > p2.GetValue(i))
            strong = true;
        else if (p1.GetValue(i) < p2.GetValue(i))
            return false;
    }
    return strong;
} 


protected virtual bool DominatesSys(double[] p1, double[] p2, int nObjectives)
{
    bool strong = false;
    for (int i = 0; i < nObjectives; i++)
    {
        if (p1[i] > p2[i])
            strong = true;
        else if (p1[i] < p2[i])
        {
            return false;
        }
    }
    return strong;
}

Results are as follow:

[INFO ] | 12:55:01,911 | [odes] |         NumericsTest   379 | Mean time taken by Dominates1 = 2.85064264444444.
[INFO ] | 12:55:01,976 | [odes] |         NumericsTest   380 | Mean time taken by Dominates2 = 0.0402656666666667.
[INFO ] | 12:55:01,977 | [odes] |         NumericsTest   381 | Mean time taken by Dominates3 = 0.173880833333333.
[INFO ] | 12:55:01,978 | [odes] |         NumericsTest   382 | Mean time taken by Dominates4 = 0.148000711111111.
[INFO ] | 12:55:01,979 | [odes] |         NumericsTest   383 | Mean time taken by Dominates5 = 0.0593142444444444.
[INFO ] | 12:55:01,980 | [odes] |         NumericsTest   383 | Mean time taken by system array = 0.00180445555555556.

Answer 1

Your timings are much too small. Probably your problem sizes also. Increase both (number of iterations, problem size) in order to get more reliable results. Also, do not forget to exlude the first iteration from the measurement (due to a much larger overhead for JIT compilation).

I doubt, the factor of 1000 is reliable. But in general it is clear, that iterating over ILArray in the manner you do cannot bring the same performance than iterating over double[]. The way ILNumerics works (and you should adapt) is vectorization. Rewrite your algorithm in a way that whole arrays are involved in a computation rather than single elements.

If this is not possible, there is nothing wrong to break out of ILArray for such micro-kernels. The way you have used (GetArrayForRead(), GetArrayForWrite()) is just fine, in order to access the underlying system array and use that for such elementwise computations.

Another way you could try is the following:

protected virtual bool Dominates(ILInArray<double> p1, ILInArray<double> p2, int nObjectives) {
    using (ILScope.Enter(p1, p2)) {
        ILArray<double> p1In = p1;
        ILArray<double> p2In = p2;
        bool strong = false;
        for (int i = 0; i < nObjectives; i++) {
            //using (ILScope.Enter()) {  // probably does not help with such tiny arrays ...
                if (p1In.GetValue(i) > p2In.GetValue(i))
                    strong = true;
                else if (p1In.GetValue(i) < p2In.GetValue(i)) {
                    return false;
                }
            //}
        }
        return strong;
    }
} 

But more promising, IMO would be something like that: (expecting the code in the context of a class derived from ILMath, so ILMath. is ommited)

protected virtual bool Dominates(ILInArray<double> p1, ILInArray<double> p2, int nObjectives) {
    using (ILScope.Enter(p1, p2)) {
        ILArray<double> n = p1 - p2;
        if (any(n < 0)) return false;
        return any(n > 0); 
    }
} 

Please measure again and let us know your results! Thanks

@Edit: thinking again, there is another option:

protected virtual bool Dominates(ILInArray<double> p1, ILInArray<double> p2, int nObjectives) {
    using (ILScope.Enter(p1, p2)) {
        ILArray<double> n = p1 - p2;
        var strong = false; 
        foreach (var d in n) {
            if (d < 0) return false;
            if (d > 0) strong = true; 
        }
        return strong; 
    }
} 

If p1.Length != p2.Length, you may adjust p1 - p2 accordingly...