C# медленно работает на массивах?

Question

Я работаю с изображениями CT, поэтому мне нужно много работать с массивами 3D, но обнаружил, что C# имеет дело с массивами очень медленно. Я написал простой тест BFS, основанный на https://stackoverflow.com/a/1056091:

struct Vector 
{ 
    public int X, Y, Z; 
} 
int width = 512, height = 512, depth = 200; 
public static int bfs(int[, ,] matrix) 
{ 
    bool[, ,] visited = new bool[width, height, depth]; 
    int sum = 0; 
    Queue<Vector> queue = new Queue<Vector>(); 
    queue.Enqueue(new Vector { X = 0, Y = 0, Z = 0 }); 
    while (queue.Count > 0) 
    { 
     Vector c = queue.Dequeue(); 
     int cx = c.X; 
     int cy = c.Y; 
     int cz = c.Z; 
     sum += matrix[cx, cy, cz]; 
     int x, y, z; 

     if ((x = cx - 1) >= 0 && !visited[x, cy, cz]) 
     { queue.Enqueue(new Vector { X = x, Y = cy, Z = cz }); visited[x, cy, cz] = true; } 
     if ((y = cy - 1) >= 0 && !visited[cx, y, cz]) 
     { queue.Enqueue(new Vector { X = cx, Y = y, Z = cz }); visited[cx, y, cz] = true; } 
     if ((z = cz - 1) >= 0 && !visited[cx, cy, z]) 
     { queue.Enqueue(new Vector { X = cx, Y = cy, Z = z }); visited[cx, cy, z] = true; } 
     if ((x = cx + 1) < width && !visited[x, cy, cz]) 
     { queue.Enqueue(new Vector { X = x, Y = cy, Z = cz }); visited[x, cy, cz] = true; } 
     if ((y = cy + 1) < height && !visited[cx, y, cz]) 
     { queue.Enqueue(new Vector { X = cx, Y = y, Z = cz }); visited[cx, y, cz] = true; } 
     if ((z = cz + 1) < depth && !visited[cx, cy, z]) 
     { queue.Enqueue(new Vector { X = cx, Y = cy, Z = z }); visited[cx, cy, z] = true; } 
    } 
    return sum; 
} 
public static void TestTime<T, TR>(Func<T, TR> action, T obj, int iterations) 
{ 
    Stopwatch stopwatch = Stopwatch.StartNew(); 
    for (int i = 0; i < iterations; ++i) 
     action(obj); 
    Console.WriteLine(action.Method.Name + " took " + stopwatch.Elapsed); 
} 
static void Main(string[] args) 
{ 
    Random random = new Random(); 
    int[, ,] m1 = new int[width, height, depth]; 
    for (int x = 0; x < width; ++x) 
     for (int y = 0; y < height; ++y) 
      for (int z = 0; z < depth; ++z) 
       m1[x, y, z] = random.Next(); 
    const int iterations = 1; 
    TestTime<int[, ,], int>(bfs, m1, iterations); 
    TestTime<int[, ,], int>(bfs, m1, iterations); 
} 

Это занимает ~ 23 секунд (одна итерация). Скомпилирован с VS2012, «Release» d, оптимизирован. Пытался написать аналогичный код на C++ (с выделенными стеками массивами), он занимает ~ 0,08 сек. DFS (со стеком вместо очереди) работает медленнее. 1D или зубчатые массивы дают почти одинаковые результаты. Я должен отметить, что непрерывный доступ (как в Why are multi-dimensional arrays in .NET slower than normal arrays?) работает нормально, 100 итераций массива [512x512x200] в ~ 26 секунд.

Почему не непрерывный доступ к массиву настолько медленный в C#? Есть ли способ ускорить его?

Answer 1

Я изменил использование списка + структуры, чтобы узнать, помогло ли оно. Это сократило вдвое время. Я изменил многомерный массив, чтобы использовать одно измерение и вручную умножил индексатор. Если что-нибудь, это еще хуже.

struct Q 
{ 
    public int X, Y, Z; 
} 
public static int bfs(int[, ,] matrix) 
{ 
    int d1 = matrix.GetLength(0), d2 = matrix.GetLength(1), d3 = matrix.GetLength(2); 
    var visited = new bool[d1, d2, d3]; 
    int sum = 0; 
    var q = new List<Q>(); 
    q.Add(new Q()); 
    while (q.Count > 0) 
    { 
     var last = q[q.Count - 1]; 
     q.RemoveAt(q.Count - 1); 
     int cx = last.X; 
     int cy = last.Y; 
     int cz = last.Z; 
     sum += matrix[cx, cy, cz]; 
     int x, y, z; 

     if ((x = cx - 1) >= 0 && !visited[x, cy, cz]) 
     { q.Add(new Q{X = x, Y = cy, Z = cz}); visited[x, cy, cz] = true; 
...