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

[stdray]

Выбирает, видимо, себе язык под проект мой, можно сказать, знакомый. Набигает с нехитрой задачей: создать трехмерный массив определенного размера, а потом пробежаться по нему 20 раз, присваивая значения счетчика. Потрать 5 минут, говорит, сделай на F#, чтобы его показатели тоже были. Мне нетрудно - взял и написал не идиоматический код с мутабельностью и форами.

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

1. open System  
2. open Microsoft.FSharp.Collections  
3.   
4. let beforeAllocation = DateTime.Now  
5. let yobaArray        = Array3D.zeroCreate 512 512 128  
6. let afterAllocation  = DateTime.Now  
7. let mutable i = 0  
8. for n in 1..20 do   
9.     for x in 0..511 do   
10.     for y in 0..511 do   
11.     for z in 0..127 do   
12.         yobaArray.[x, y, z] <- i  
13.         i <- i + 1  
14. let afterLoop       = DateTime.Now  
15. let totalLoopTime   = afterLoop - afterAllocation  
16. let averageLoopTime = new TimeSpan(totalLoopTime.Ticks / 20L)  
17. printfn "Allocation time: %A"   <| afterAllocation - beforeAllocation  
18. printfn "Total loop time: %A"   <| totalLoopTime  
19. printfn "Average loop time: %A" <| averageLoopTime   

Да и фиг бы с ними, явно речь идет про скорость аллокации и доступа. Для такой задачи, оно может и лучше даже. И выдает это чудо какое-то время

Allocation time: 00:00:00.0290017
Total loop time: 00:00:57.4592865
Average loop time: 00:00:02.8729643

и фиг его знает, нормальное оно или нет. Тут даже корявый подсчет через DateTime.Now роли не играет, большие чиcла же. Поглядели другие кусочки кода, результаты почитали. Хотя какой смысл сравнивать, если у всех машины разные и результаты в вакууме получаются. Питон попробовали покормить такой-то аллокацией таких-то массивов, наблюдая как он крашится, хотя списки списков списков нам создать таки удалось, а вот заполнения дождались с трудом. Нету никаких массивов в питоне кроме тех, что в нумпае лежат. Еще руби пытались заставить делать такое, только он массив выделил, а шевелился медленно-медленно, автор так и не дождался результатов и спать ушел. А я декомпильнул фишарповское приложение в додиез с вопросом "Array3d ты кто такой? дава"

На удивление мало собачек и циферок я разлядел. Ну а Array3d - это многомерный массив. Только я забыл, что он из себя представляет и как под него память аллоцирутеся. Точно помню, был момент, мол чем же [1][2] от [1,2] отличается. Но, видать, так не сильно нужно было. Потом я набросал небольшой тест для 3 видов трехмерных интовых массивов.

Можно посмотреть писанину: http://pastebin.com/mwqnm2re

Test allocate ragged array: 0,8430482 seconds
Test fill ragged array in xyz order: 11,9506836 seconds (repeated 20 avr 0,59753418 seconds)
Test allocate multidimension array: 0,0010001 seconds
Test fill multidimension in xyz order: 22,6692966 seconds (repeated 20 avr 1,13346483 seconds)
Test allocate flat array: 0,0900052 seconds
Test fill flat array in xyz order: 38,1171802 seconds (repeated 20 avr 1,90585901 seconds)
Test fill flat array in xzy order: 38,8362213 seconds (repeated 20 avr 1,941811065 seconds)

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

Кароче, как-то я потерялся за этот вечер. Устройства дотнетов не знаю. Надо доставать Рихтера, хотя читал уже. Досадно. Хотя, в любом случае, надо отметить, что clr с задачей справляется, как вообщем-то и jvm. А вот модные скрипто-игрушки совершенно не але, по крайней мере в лоб стандартными средствами языка. А ведь за всем этим гламурным кодом и рассуждениями за чистоту и функторы легко забываешь, что где-то внутри выделяется память, кешируется что-то и вообще все всё за тебя решают.

Comments

[thedeemon.livejournal.com]

Как минимум можно заметить, что в ragged во внутреннем цикле идет просто обращение по индексу (одно сложение), а в других вариантах каждый раз из x,y,z вычисляется индекс - несколько умножений, сложений и обращений к полям. Поскольку больше в цикле почти ничего не происходит, это дает большую разницу в итоге. Можно также предположить, что вычисление индекса во встроенном многомерном массиве сделано эффективнее, чем тут рукопашное, отсюда разница между ними.

[stdray.livejournal.com]

sassa_nf чуть ниже предлагает оптимизацию вычисления индекса, кроме нее я не вижу, что там можно сделать более эффективным.

[sassa-nf.livejournal.com]

как "что"? сделать массиву итератор нормальный. :)

[stdray.livejournal.com]

Ну итератор разве что для единообразия. Для массива главное - доступ к произвольному элементу за O(1), а проблема моего Flat3dArray, что он именно в этом медленный.

[stdray.livejournal.com]

>Можно также предположить, что вычисление индекса во встроенном многомерном массиве сделано эффективнее

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

[thedeemon.livejournal.com]

Не, он внутре должен быть один большой flat.

Они могли сэкономить на инициализации - обнулять память не вручную при выделении, а через механизмы ОС, которые выдают виртуальную память уже обнуленную.

Еще одна причина тормозов второго и третьего вариантов - слишком много вызовов методов, они нифига не инлайнятся, скорее всего. В случае jagged такого нет, там IL проще намного.

[sassa-nf.livejournal.com]

Обнуление памяти вещь совершенно необязательная. Компиляторы следят за использованием полей объектов и массивов, и если они заполняются полностью и без чтения, то обнуление не выполняется.

Ещё они должны были сэкономить на вычислении индекса: размеры массива известны в том же scope и они являются power of 2. В случае же самопального Flat3dArray для подобной оптимизации нужно заинлайнить всё по самую ручку, а уж потом применить подобные евристики на вычислениях индекса.

[thedeemon.livejournal.com]

Вы переоцениваете ум шарповского компилятора. Теоретически такие оптимизации предположить можно, но реально их тут ожидать я бы не стал.

[sassa-nf.livejournal.com]

Да вот же ж, переоцениваю. Его вообще даже и не видно. Всякие оптимизации power of 2 имели бы место, если бы разница между multidimension: 22 sec и flat: 38 sec была более существенной.

[stdray.livejournal.com]

Я тут еще один пост (http://stdray.livejournal.com/73674.html) написал. Из оптимизаций возможно только вынесение провером на границы за тело цикла. И оно не применимо к двухмерному случаю.

[sassa-nf.livejournal.com]

стоп-стоп-стоп. в двумерном случае с проверкой границ как раз ништяк: раз в 128 записей проверить попадание каких-то границ (и то ещё не известно, может и реже); а вот плоская самопальная реализация - вообще-то нужно проверять попадание в границы во время каждого обращения.

[wizzard]

только фортран, только хардкор!

алсо, аррей такой, кажется, jagged а не ragged

алсо, попробуй повключать-повыключать array bounds check и overflow check

алсо, обход массива не в том порядке - это да, в десятки раз скорость отличаться может, особенно если идти по двум-трем массивам, чтоб кэш лучше смывало....

[stdray.livejournal.com]

>только фортран, только хардкор!
Решение наше фортртраное, не то чтобы поражало воображение скоростью. Мы, правда, не вспомнили, как там правильно память выделять, но не суть.

>алсо, аррей такой, кажется, jagged а не ragged
Не знаю, о чем я там вчера думал)

>алсо, попробуй повключать-повыключать array bounds check и overflow check
Overflow check по умолчаю вроде выключен. А вот с проверкой выхода за границы массива можно поиграться. Что, кстати, если я проверки выключу и за границы выползу?

>алсо, обход массива не в том порядке - это да, в десятки раз скорость отличаться может
Я запускал zxy-обход, там на 2 порядка проседение было.

[sassa-nf.livejournal.com]

а чо allocate jagged array всего в 10 раз медленнее, чем allocate flat array, а количество массивов должно быть в 20 раз больше? аяяй.

[sassa-nf.livejournal.com]

шото я погнал. Не в 20, а в 256000 раз больше. Это по количеству. По объёму-то занимаемой памяти должно быть примерно то же самое. Так что, здесь ещё какая-то фигня замешана.

[stdray.livejournal.com]

Я тоже этого не понял, смотрел в код вчера, но ничего криминального не нашел. Может clr трудно выледить большой скопом? Занимаемую память тоже надо как-то посмотреть, хотя это не так просто, как замерить время.

>Не в 20, а в 256000 раз больше.
Не понял. В случае с flat имеет 1 массив, а с jagged - один, в который вложено 512, в кадом из которых 128, итого 65537.

[sassa-nf.livejournal.com]

ээээ.... ну, щас давай на мою математику посмотрим:

512х512х128 = 512 массивов 512 х 128 = 512 массивов по 512 массивов по 128. Итого 512х512 раз выделить по 128. Не?..

я про CLR не знаток, но если у них generational heap, то да, большой кусок выделить раз нужно из другой области памяти; маленькие массивы могут размещаться в thread-local куске, а то и вообще на стеке остаться.

[stdray.livejournal.com]

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

[sassa-nf.livejournal.com]

x * SizeY * SizeZ + y * SizeZ + z => (x * SizeY + y) * SizeZ + z

[stdray.livejournal.com]

Протестирую. Если верить thedeemon сэкономленное умножение должно быть ощутмо сказаться на этой задаче.