Многомерные массивы 2

[stdray]

Я тут проводил какие-то тесты над многомерными массивами дотнета, результаты которых меня несколько удивили.

Во-первых, было непонятно, что такое многомерный массив в дотнете. Он моментально выделяется и имеет относительно большое время доступа к элементам. Хотя в сравнении с моей реализацией на коленке трехмерного массива, он просто летает. Относительно 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 умеет нормально работать только с одномерными массивами, начальный индекс которых равен нулю. То есть нумерация элементов может начинаться и с какого-то другого значения. Как-то так:

copy to clipboardподсветка кода

1. > Array.CreateInstance(typedefof<Int32>, [| 10 |], [| 0 |]).GetType().Name;;  
2. val it : string = "Int32[]"  
3. > Array.CreateInstance(typedefof<Int32>, [| 10 |], [| 1 |]).GetType().Name;;  
4. val it : string = "Int32[*]"  
5. > Array.CreateInstance(typedefof<Int32>, [| 10; 10 |], [| 0; 0 |]).GetType().Name;;  
6. val it : string = "Int32[,]"  
7. > Array.CreateInstance(typedefof<Int32>, [| 10; 10 |], [| 1; 1 |]).GetType().Name;;  
8. 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 кодом, а скорость аллокации ситуацию не меняет, потому что не вижу задач, где надо часто выделять массивы. А, в-третьих, работу через указатели поддерживают массивы лишь органиченного числа типов, то есть решение совсем не общее.

Интересно, конечно, было поиграться, только вот осталось какое-то двоякое ощущение. С одной стороны, хорошо иметь возможно поднять производительность приложения на ровном месте, а с другой - это очевидный случай протекающей абстракции. Я даже думаю, что о подобных возможностях лучше не знать, иначе появляется соблазн почитерить вместо улучшения характеристик самого алгоритма. В худшем случае, производительность надо достигать распараллеливанием и развертыванием дополнительных машинок. Не думаю, что старое доброе дрочево "а кто же периодически срет в память" выйдет дешевле. Хотя, конечно, я-то со стороны своих задач сужу, в других областях оно, может, как-то по иному.

Comments

[sassa-nf.livejournal.com]

а чё у вас теперь Test fill multidimension in xyz order: 8188ms, а было Test fill multidimension in xyz order: 22,6692966 seconds

[sassa-nf.livejournal.com]

1. если у вас JIT (я думал, статический компилятор), то не нужно ли машину греть.

2. если у вас GC, то не влияет ли порядок аллокации на время аллокации (на этапе, когда нужно выделить плоский массив, у вас память всё ещё занята мультиdimensional массивом)

[thedeemon.livejournal.com]

Глупый вопрос: на старых и новых тестах флаг компилятора /optimize был включен? Говорят, он не всегда по умолчанию включен даже в release.

Ну а в целом картина совершенно ожидаемая. Оптимизаций в C# и CLR немного (быстро компиляет, быстро запускает, думать некогда вообще), bounds checks убираются только в самом примитивном случае, шаг в сторону - и они остаются. За все это приходится платить тактами.

[wizzard]

я еще хотел бы сказать что аттач дебаггера мгновенно вырубает половину оптимизаций джиттера