Многомерные массивы 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

[stdray.livejournal.com]

Я просто вчера писал и запускал на нетбуке, а потом на рабочей машинке. К тому же сделан нормальный замер времени. Отсюда и разница. Вот прогон теста на том же нетбуке:

Test allocate jagged array: 992ms
Test fill jagged array in xyz order: 13522ms (20 repeats, avr 676ms)
Test allocate multidimension array: 0ms
Test fill multidimension in xyz order: 19429ms (20 repeats, avr 971ms)
Test unsafe fill multidimension in xyz order: 8168ms (20 repeats, avr 408ms)
Test allocate flat array: 106ms
Test fill flat array in xyz order: 26256ms (20 repeats, avr 1312ms)
Test unssafe fill flat array in xyz order: 8124ms (20 repeats, avr 406ms)

[sassa-nf.livejournal.com]

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

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

[stdray.livejournal.com]

1) csc компиляет в IL, который JIT'ом компилируется в бинарный. Магия оптимизаций может быть на обоих этапах. В данном случае, я не вижу, на что может влиять прогрев.

2) Похоже, что влияет. Стал прогонять тесты Flat3DArray первыми.
Test allocate flat array: 1ms
Test allocate multidimension array: 2ms
Это многое объясняет, но многомерный выделяется быстро вне зависимости от обстоятельств. Если тесты Flat3DArray запускать не самыми первыми, то его время аллокации возвращается на привычные 100+ms.

[sassa-nf.livejournal.com]

"на что может влиять прогрев"

Расскажу, как в джаве.

JIT может и соптимизировать, но постесняется заместить метод на оптимальный, пока вызов не вернулся из метода.

Количество вызовов метода влияет на количество и типы оптимизаций. (инлайн полиморфного кода - когда есть статистика, какие инстансы появляются чаще всего; глубина инлайна зависит от количества вызовов; loop unrolling зависит от количества времени внутри цикла; condition reversion зависит от наиболее вероятного результата; dead code elimination = пурый код с неиспользуемым результатом удаляется)

Allocation у вас всего по одному разу. Сделать побольше хип и погонять несколько раз в разной последовательности.

Измерить не только среднее, но и stdev. Прогретая машина даст маленький stdev.

[stdray.livejournal.com]

С аллокацией мне не разобраться. Человек, который просил у меня тест для F# прогнал на mono в виртуалке под macos код и получил:

Test allocate jagged array: 540ms
Test fill jagged array in xyz order: 3225ms (20 repeats, avr 161ms)
Test allocate multidimension array: 798ms
Test fill multidimension in xyz order: 10327ms (20 repeats, avr 516ms)
Test unsafe fill multidimension in xyz order: 1485ms (20 repeats, avr 74ms)
Test allocate flat array: 1066ms
Test fill flat array in xyz order: 6741ms (20 repeats, avr 337ms)
Test unssafe fill flat array in xyz order: 1454ms (20 repeats, avr 72ms)

потом я попросил его запустить бинарник собранный студийным компилятором сишарпа:

Test allocate jagged array: 518ms
Test fill jagged array in xyz order: 3232ms (20 repeats, avr 161ms)
Test allocate multidimension array: 278ms
Test fill multidimension in xyz order: 9945ms (20 repeats, avr 497ms)
Test unsafe fill multidimension in xyz order: 1486ms (20 repeats, avr 74ms)
Test allocate flat array: 292ms
Test fill flat array in xyz order: 6463ms (20 repeats, avr 323ms)
Test unssafe fill flat array in xyz order: 1446ms (20 repeats, avr 72ms)

Вот под моно, никаких неувязок нет. Под виндой, видимо, есть какие-то хаки, про которые писал thedeemon.

[sassa-nf.livejournal.com]

"Test fill multidimension in xyz order: 10327ms
Test fill flat array in xyz order: 6741ms

Test fill multidimension in xyz order: 9945ms
Test fill flat array in xyz order: 6463ms"

это улучшенная арифметика, так? Значит, ещё разница на проверке внутренних размерностей, которые у multidimensional есть, а у flat нет.

[stdray.livejournal.com]

Вот это в соответсвует информации в Рихтере. Моно отработал в точности в соответствии с теорией. А для виндовой CLR надо действительно больше тестов, как вы писали.

[thedeemon.livejournal.com]

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

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

[stdray.livejournal.com]

Компилял в релиз со включенной оптимизаций оба раза.

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

Что касается тактов, то мне скинули варианты этой задачи на фортране и си, так они в 2 раза проигрывают худшему из вариантов на дотнете.

[thedeemon.livejournal.com]

>на фортране и си, так они в 2 раза проигрывают

А вот это уже удивительно. Как и чем собирались?

[stdray.livejournal.com]

Я думаю, что авторы сишного и фортранного кода ненастоящие байтолюбы.

Сишный код (сам код смогу дать лишь вечером, поскольку он остался на нетбуке) я сначала собрал плюсовым gcc со всеми оптимизациями, потом компилятором c++ из студии. Время заполенения превысилос 100 и 130 скунд соответственно. Ад.

Фортрановый код (http://pastebin.com/1C2x6pwd) был собран вот этим поделием (http://www.silverfrost.com/11/ftn95_overview.aspx), поскольку мне было лениво разбираться с gcc фортраном под cygwin'ом.

Думаю, и там и там есть ошибки.

[stdray.livejournal.com]

сишечка

allocate: 0.00ms memset: 329.00ms fill: 120040.00ms average: 6002.00ms

http://pastebin.com/0EmGCkGp

[thedeemon.livejournal.com]

Так тут же порядок обхода совсем другой! Понятно, что это во много раз медленнее. Надо сделать порядок обхода как в шарпе, тогда уже сравнивать.

[thedeemon.livejournal.com]

Запустил у себя, собирал в VS2010.
Оригинал:
allocate: 0.00ms memset: 78.00ms fill: 25069.00ms average: 1253.45ms

Теперь делаем его ближе к варианту на С#. Во-первых, массив там инициализируется нулем, поэтому вместо явного заполнения его говядиной просто заменяем malloc на calloc:

allocate & memset: 0.00ms fill: 25568.00ms average: 1278.40ms

Во-вторых, приводим в соответствие тело главного цикла:
array[128*(512*x + y) + z] = i++;

Получаем:
allocate & memset: 0.00ms fill: 1014.00ms average: 50.70ms

Разогнали в 25 раз.

[stdray.livejournal.com]

Ага. Интересно, там что-нибудь векторизуется? Хотя, вроде, видел, что ms cpp не может в подобные оптимизации.

[thedeemon.livejournal.com]

Не, не векторизуется.

	mov	edx, 128				; 00000080H
$LL3@wmain:
; 21   :	array[128*(512*x + y) + z] = i++;
	mov	DWORD PTR [eax], ecx
	inc	ecx
	add	eax, 4
	dec	edx
	jne	SHORT $LL3@wmain

[thedeemon.livejournal.com]

Запустил у себя С# тест из поста для сравнения:

Test allocate jagged array: 314ms
Test fill jagged array in xyz order: 2864ms (20 repeats, avr 143ms)
Test allocate multidimension array: 0ms
Test fill multidimension in xyz order: 3788ms (20 repeats, avr 189ms)
Test unsafe fill multidimension in xyz order: 1064ms (20 repeats, avr 53ms)
Test allocate flat array: 14ms
Test fill flat array in xyz order: 1877ms (20 repeats, avr 93ms)
Test unssafe fill flat array in xyz order: 1119ms (20 repeats, avr 55ms)

Теперь картина ожидаемая - unsafe чуть медленнее С++, safe сильно медленнее.

[stdray.livejournal.com]

>allocate & memset: 0.00ms fill: 1014.00ms average: 50.70ms
>Test fill flat array in xyz order: 1877ms (20 repeats, avr 93ms)
> safe сильно медленнее

Не так уж сильно, разницы на порядки нет. Может посмотрю, как ведут другие яп высокого уровня, позиционируемые как производительные: D, OCaml, ObjC. Пока результаты дотнета мне представляются весьма неплохими.

[thedeemon.livejournal.com]

Чтобы на порядки - это нужен Руби. :) А тут 2-4 раза. Для каких-то задач приемлемо, для каких-то не очень.

В окамле массивы сравнительно медленные, а в 32-битной версии еще и заметно ограниченные по длине: jagged сделать получится, а для flat придется брать bigarray.

[wizzard]

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

[thedeemon.livejournal.com]

HeisenJIT ;)

[stdray.livejournal.com]

В данном случае, дебагер не участвовал.

[wizzard]

А, эт хорошо.