Многомерные массивы 2
Sep. 28th, 2012 12:13 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stdrayЯ тут проводил какие-то тесты над многомерными массивами дотнета, результаты которых меня несколько удивили.
Во-первых, было непонятно, что такое многомерный массив в дотнете. Он моментально выделяется и имеет относительно большое время доступа к элементам. Хотя в сравнении с моей реализацией на коленке трехмерного массива, он просто летает. Относительно Flat3d-поделки предположили, что дело в дорогих арифметических операциях и вызовах методов, которые не инлайнятся. Убрал лишний метод и немного оптимизировал арифметику. В итоге
Было (http://pastebin.com/mwqnm2re):
Стало (http://pastebin.com/2QVsRuyP):
Из того, что скорость выросла в 2 с лишним раза следует, что компилятор не иинлайнил и JIT ничегошеньки не оптимизировал.
Во-вторых, почему доступ к элементам многомерного массива в два раза медленней по сравнению с ехал массив через массив? Напоминаю:
Читал Рихтера. Он пишет, что CLR умеет нормально работать только с одномерными массивами, начальный индекс которых равен нулю. То есть нумерация элементов может начинаться и с какого-то другого значения. Как-то так:
Тут я создал по порядку: одномерный массив из 10 элементов с индексацией с нуля, потом аналогичный массив, индексируемый с единицы, а потом рассмотрел эти варианты для двухмерного случая. Ситуация очень простая: если тип массива отличен от T[] - будет медленно. Рихтер объясняет это так:
Выходит, что многомерный массив медленней из-за проверки выхода за границы на каждом такте. Это уже интересней. Представил на минутку, что у нас на дворе на 2012 год, а средневековье времен сильной инквизиции, и попробовал написать заполнение все того же многомерного массива, но с ансейфом и указателями:
Скорость работы с многомерным массивом выросла в 2 раза. А что будет с моим Flat3dArray в асейф режиме?
Абсолютно идентичный многомерному результат. По крайней мере, я теперь точно знаю, как представлен в памяти многомерный массив, но вот почему он так быстро выделяется, все равно не понимаю. Вот результаты всех тестов:
Тестовый код: http://pastebin.com/2QVsRuyP
Я еще пробовал увеличить скоростью выделения памяти под jagged array при помощи stackalloc, но в результате получался указатель, с которым можно работать только адресной арифметикой и никак иначе. Минутка кончилась, мы больше не в средневековье. А в современным мире, наверное, за такое наказывают. Решение с unsafe, я думаю, не является приемлемым. Во-первых, оно не будет работать на сильверлайте, хотя казалось бы, где еще как не на телефонах гоняться за производительностью? Во-вторых, это зайчатки ада. Все эти "я смогу аккуратно обращаться с памятью" уже проходили - дошли не все. Скорость доступа jagged array сопоставима с unsafe кодом, а скорость аллокации ситуацию не меняет, потому что не вижу задач, где надо часто выделять массивы.
Интересно, конечно, было поиграться, только вот осталось какое-то двоякое ощущение. С одной стороны, хорошо иметь возможно поднять производительность приложения на ровном месте, а с другой - это очевидный случай протекающей абстракции. Я даже думаю, что о подобных возможностях лучше не знать, иначе появляется соблазн почитерить вместо улучшения характеристик самого алгоритма. В худшем случае, производительность надо достигать распараллеливанием и развертыванием дополнительных машинок. Не думаю, что старое доброе дрочево "а кто же периодически срет в память" выйдет дешевле. Хотя, конечно, я-то со стороны своих задач сужу, в других областях оно, может, как-то по иному.
Во-первых, было непонятно, что такое многомерный массив в дотнете. Он моментально выделяется и имеет относительно большое время доступа к элементам. Хотя в сравнении с моей реализацией на коленке трехмерного массива, он просто летает. Относительно Flat3d-поделки предположили, что дело в дорогих арифметических операциях и вызовах методов, которые не инлайнятся. Убрал лишний метод и немного оптимизировал арифметику. В итоге
Было (http://pastebin.com/mwqnm2re):
Test fill flat array in xyz order: 26059ms (20 repeats, avr 1302ms)Стало (http://pastebin.com/2QVsRuyP):
Test fill flat array in xyz order: 10392ms (20 repeats, avr 519ms)Из того, что скорость выросла в 2 с лишним раза следует, что компилятор не иинлайнил и JIT ничегошеньки не оптимизировал.
Во-вторых, почему доступ к элементам многомерного массива в два раза медленней по сравнению с ехал массив через массив? Напоминаю:
Test fill jagged array in xyz order: 11,9506836 seconds (repeated 20 avr 0,59753418 seconds)
Test fill multidimension in xyz order: 22,6692966 seconds (repeated 20 avr 1,13346483 seconds)Читал Рихтера. Он пишет, что CLR умеет нормально работать только с одномерными массивами, начальный индекс которых равен нулю. То есть нумерация элементов может начинаться и с какого-то другого значения. Как-то так:
- > Array.CreateInstance(typedefof<Int32>, [| 10 |], [| 0 |]).GetType().Name;;
- val it : string = "Int32[]"
- > Array.CreateInstance(typedefof<Int32>, [| 10 |], [| 1 |]).GetType().Name;;
- val it : string = "Int32[*]"
- > Array.CreateInstance(typedefof<Int32>, [| 10; 10 |], [| 0; 0 |]).GetType().Name;;
- val it : string = "Int32[,]"
- > Array.CreateInstance(typedefof<Int32>, [| 10; 10 |], [| 1; 1 |]).GetType().Name;;
- val it : string = "Int32[,]"
Тут я создал по порядку: одномерный массив из 10 элементов с индексацией с нуля, потом аналогичный массив, индексируемый с единицы, а потом рассмотрел эти варианты для двухмерного случая. Ситуация очень простая: если тип массива отличен от T[] - будет медленно. Рихтер объясняет это так:
Доступ к элементам одномерного массива с нулевой нижней границей осуществляется немного быстрее, чем доступ к элементам многомерных массивов или массивов с ненулевой нижней границей. Есть несколько причин такому поведению. Во-первых, специальные команды для работы с одномерными массивами с нулевой нижней границей (newarr, ldelem, ldelema , ldlen и stelem) позволяют JIТ-компилятору генерировать оптимизированный код. При этом предполагается, что первый индекс равен нулю, то есть при доступе к элементам отсутствует необходимость вычислять смещение. Кроме того, в общем случае компилятор умеет выносить код проверки границ за пределы цикла.
Выходит, что многомерный массив медленней из-за проверки выхода за границы на каждом такте. Это уже интересней. Представил на минутку, что у нас на дворе на 2012 год, а средневековье времен сильной инквизиции, и попробовал написать заполнение все того же многомерного массива, но с ансейфом и указателями:
Test fill multidimension in xyz order: 8188ms (20 repeats, avr 409ms)
Test unsafe fill multidimension in xyz order: 3898ms (20 repeats, avr 194ms)Скорость работы с многомерным массивом выросла в 2 раза. А что будет с моим Flat3dArray в асейф режиме?
Test unssafe fill flat array in xyz order: 3850ms (20 repeats, avr 192msАбсолютно идентичный многомерному результат. По крайней мере, я теперь точно знаю, как представлен в памяти многомерный массив, но вот почему он так быстро выделяется, все равно не понимаю. Вот результаты всех тестов:
Тестовый код: http://pastebin.com/2QVsRuyP
Test allocate jagged array: 370ms
Test fill jagged array in xyz order: 5199ms (20 repeats, avr 259ms)
Test allocate multidimension array: 0ms
Test fill multidimension in xyz order: 8173ms (20 repeats, avr 408ms)
Test unsafe fill multidimension in xyz order: 3899ms (20 repeats, avr 194ms)
Test allocate flat array: 23ms
Test fill flat array in xyz order: 10239ms (20 repeats, avr 511ms)
Test unssafe fill flat array in xyz order: 3852ms (20 repeats, avr 192ms)Я еще пробовал увеличить скоростью выделения памяти под jagged array при помощи stackalloc, но в результате получался указатель, с которым можно работать только адресной арифметикой и никак иначе. Минутка кончилась, мы больше не в средневековье. А в современным мире, наверное, за такое наказывают. Решение с unsafe, я думаю, не является приемлемым. Во-первых, оно не будет работать на сильверлайте, хотя казалось бы, где еще как не на телефонах гоняться за производительностью? Во-вторых, это зайчатки ада. Все эти "я смогу аккуратно обращаться с памятью" уже проходили - дошли не все. Скорость доступа jagged array сопоставима с unsafe кодом, а скорость аллокации ситуацию не меняет, потому что не вижу задач, где надо часто выделять массивы.
Интересно, конечно, было поиграться, только вот осталось какое-то двоякое ощущение. С одной стороны, хорошо иметь возможно поднять производительность приложения на ровном месте, а с другой - это очевидный случай протекающей абстракции. Я даже думаю, что о подобных возможностях лучше не знать, иначе появляется соблазн почитерить вместо улучшения характеристик самого алгоритма. В худшем случае, производительность надо достигать распараллеливанием и развертыванием дополнительных машинок. Не думаю, что старое доброе дрочево "а кто же периодически срет в память" выйдет дешевле. Хотя, конечно, я-то со стороны своих задач сужу, в других областях оно, может, как-то по иному.