вторник, 25 марта 2008 г.

Двумерные массивы и foreach

Известно, что если сделать список List<TestObject> list и перебирать его через foreach:


foreach(TestObject obj in list)
{
..
}

скорость будет меньше, чем если бы у нас был массив TestObject [] array и мы перебирали его поэлементно или тем же foreach:

foreach(TestObject obj in array)
{
..
}

Разница в скорости примерно в 2-3 раза, но зачастую это не критично, т.к. сами операции над объектами занимают такое время, что на их фоне перебор коллекции лишь песчинка в песочных часах.

Причина скорости работы с массивами в том, что компилятор и JIT отслеживают такие операции и машинный код перебора массива уже сравним с тем, что был бы в чистом С - наращивание указателя на элемент массива с каждым шагом. В случае же с List<> создается енумератор, выполняется каждый раз вызов MoveNext и прочие действия.

Не так давно я столкнулся с развитием этой темы для двумерных массивов. Коллекция объектов карты (тайлов) представляла собой двумерный массив, который полностью перебирался с некоторой периодичестью. Раньше это было реализовано в два цикла, примерно так:

for(int x=0; x<max_x; x++)
for(int y=0; y<max_y; y++)
{
   TestObject obj = array[x,y];
..
}


Через какое-то время коллекцию пришлось вынести в другое место, а массив получать как TestObject[,]. Тогда же и появилась идея написать перебор в один цикл с стандартным foreach:

TestObject [,] array = getArray();
foreach(TestObject obj in array)
{
..
}

Компилятор остался недоволен такой конструкцией, потому массив был приведен к Array и следующий пример без проблем компилировался и работал:

Array array = (Array)getArray();
foreach(TestObject obj in array)
{
..
}


Через несколько дней я заметил, что нагрузка на процессор после этой "оптимизации" заметно возросла. Детальное изучение показало, что после приведения к Array перебор коллекции перестал оптимизироваться и свелся к работе с Array.GetEnumerator(), оптимальность которого, мягко говоря, невысокая.

Был вариант вернуться к двойному перебору массива, но в результате был выбран более простой путь - отказаться от двумерных массивов. Действительно, с zero-based индексами мы совершенно спокойно можем заменить обращение array[x,y] на array[x + y*max_x], а для перебора коллекции получать просто массив TestObject[] и работать с ним как с foreach/for/while, положившись на оптимизацию компилятора и JIT.

В качестве вывода я процитирую Mike Stall (http://blogs.msdn.com/jmstall/):


Optimizing for the wrong scenario can kill performance