Итерация через ILArray <double> очень медленно

Question

Когда я пытался профилировать алгоритм медленной оптимизации, я обнаружил, что следующий метод занимает гораздо больше времени, чем ожидалось:

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; 
    } 
} 

Затем я заменил его на следующей реализации а скорость увеличивается на огромное количество.

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; 
} 

Я не понимаю этого и попытался написать тест, чтобы сравнить разницу. Ниже приведен код проверки:

[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; 
} 

Я был в шоке от полученного причудливого результата. Я ожидал, что ILArray будет немного медленнее, чем системный массив с точки зрения последовательной индексации, но в 1000 раз слишком много. Может кто-то помочь диагностировать мою проблему здесь:

[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. 

---

Следующие предложения Haymo, в следующий тест проводится для сравнения скорости различных реализаций. Я думаю, что в этом случае, поскольку никакие промежуточные массивы не должны создаваться с использованием DominateSys, его производительность является самой быстрой.

[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; 
} 

Результаты являются следующие:

[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

Ваши тайминги слишком малы. Возможно, и ваши проблемы. Увеличьте оба (количество итераций, размер проблемы), чтобы получить более надежные результаты. Кроме того, не забудьте исключить первую итерацию из измерения (из-за гораздо больших издержек для компиляции JIT).

Уверен, что фактор 1000 надежный. Но в целом ясно, что итерация по ILArray в том виде, как вы делаете, не может принести такую ​​же производительность, как и итерация по двойному []. Способ работы ILNumerics (и вы должны адаптироваться) - это векторизация. Перепишите свой алгоритм таким образом, чтобы все массивы участвовали в вычислении, а не в одиночных элементах.

Если это невозможно, нет ничего страшного, чтобы вырваться из ILArray для таких микроядер. Способ, которым вы пользовались (GetArrayForRead(), GetArrayForWrite()), является прекрасным, чтобы получить доступ к базовому системному массиву и использовать его для таких поэлементных вычислений.

Другим способом вы можете попробовать следующий:

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; 
    } 
} 

Но более перспективным, IMO будет что-то вроде этого:. (Ожидая кода в контексте класса, производного от ILMath, так ILMath будет опущен)

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); 
    } 
} 

Просьба снова измерить и сообщить нам свои результаты! Благодаря

@Edit: думать снова, есть еще один вариант:

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; 
    } 
} 

Если p1.Length != p2.Length, вы можете настроить p1 - p2 соответственно ...