![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Многомерные массивы
Выбирает, видимо, себе язык под проект мой, можно сказать, знакомый. Набигает с нехитрой задачей: создать трехмерный массив определенного размера, а потом пробежаться по нему 20 раз, присваивая значения счетчика. Потрать 5 минут, говорит, сделай на F#, чтобы его показатели тоже были. Мне нетрудно - взял и написал не идиоматический код с мутабельностью и форами.
Да и фиг бы с ними, явно речь идет про скорость аллокации и доступа. Для такой задачи, оно может и лучше даже. И выдает это чудо какое-то время
и фиг его знает, нормальное оно или нет. Тут даже корявый подсчет через DateTime.Now роли не играет, большие чиcла же. Поглядели другие кусочки кода, результаты почитали. Хотя какой смысл сравнивать, если у всех машины разные и результаты в вакууме получаются. Питон попробовали покормить такой-то аллокацией таких-то массивов, наблюдая как он крашится, хотя списки списков списков нам создать таки удалось, а вот заполнения дождались с трудом. Нету никаких массивов в питоне кроме тех, что в нумпае лежат. Еще руби пытались заставить делать такое, только он массив выделил, а шевелился медленно-медленно, автор так и не дождался результатов и спать ушел. А я декомпильнул фишарповское приложение в додиез с вопросом "Array3d ты кто такой?дава"
На удивление мало собачек и циферок я разлядел. Ну а Array3d - это многомерный массив. Только я забыл, что он из себя представляет и как под него память аллоцирутеся. Точно помню, был момент, мол чем же [1][2] от [1,2] отличается. Но, видать, так не сильно нужно было. Потом я набросал небольшой тест для 3 видов трехмерных интовых массивов.
Можно посмотреть писанину: http://pastebin.com/mwqnm2re
Там наверное ошибки есть, которых я не замечаю. Но суть должна быть ясна. Сначала протестировал массив массивов, потом многомерные эти, потом выделил плоскую лапшу и руками смапил на нее трехмерные координаты. Во-первых, как-то забываешь, что по массивам надо ползать в правильном направлении, иначе можно схлопотать какую-то жуткую потерю скорости на ровном месте. Во-вторых, чем этот многомерный массив занимается, я так и не понял. Он _медленнее_ массива массивов при доступе, хотя выделяется моментально, да. Но, блин, если уж массив создаем, значит с ним работать надо, иначе можно иммутабельными структурами обойтись. А плоская моя самоделка - совсем ни в какие ворота, хотя тоже непонятно почему. Вроде вот тебе указатель, вот тебе смещение... Хотя, конечно, мы не с няшной сишкой дело имеем, хотя и тут какой-то адов ансейф на указателях устраивать можно, но ну его нафиг, бе.
Кароче, как-то я потерялся за этот вечер. Устройства дотнетов не знаю. Надо доставать Рихтера, хотя читал уже. Досадно. Хотя, в любом случае, надо отметить, что clr с задачей справляется, как вообщем-то и jvm. А вот модные скрипто-игрушки совершенно не але, по крайней мере в лоб стандартными средствами языка. А ведь за всем этим гламурным кодом и рассуждениями за чистоту и функторы легко забываешь, что где-то внутри выделяется память, кешируется что-то и вообще все всё за тебя решают.
- open System
- open Microsoft.FSharp.Collections
- let beforeAllocation = DateTime.Now
- let yobaArray = Array3D.zeroCreate 512 512 128
- let afterAllocation = DateTime.Now
- let mutable i = 0
- for n in 1..20 do
- for x in 0..511 do
- for y in 0..511 do
- for z in 0..127 do
- yobaArray.[x, y, z] <- i
- i <- i + 1
- let afterLoop = DateTime.Now
- let totalLoopTime = afterLoop - afterAllocation
- let averageLoopTime = new TimeSpan(totalLoopTime.Ticks / 20L)
- printfn "Allocation time: %A" <| afterAllocation - beforeAllocation
- printfn "Total loop time: %A" <| totalLoopTime
- 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. А вот модные скрипто-игрушки совершенно не але, по крайней мере в лоб стандартными средствами языка. А ведь за всем этим гламурным кодом и рассуждениями за чистоту и функторы легко забываешь, что где-то внутри выделяется память, кешируется что-то и вообще все всё за тебя решают.
no subject
no subject
алсо, аррей такой, кажется, jagged а не ragged
алсо, попробуй повключать-повыключать array bounds check и overflow check
алсо, обход массива не в том порядке - это да, в десятки раз скорость отличаться может, особенно если идти по двум-трем массивам, чтоб кэш лучше смывало....
no subject
no subject
no subject
no subject
Решение наше фортртраное, не то чтобы поражало воображение скоростью. Мы, правда, не вспомнили, как там правильно память выделять, но не суть.
>алсо, аррей такой, кажется, jagged а не ragged
Не знаю, о чем я там вчера думал)
>алсо, попробуй повключать-повыключать array bounds check и overflow check
Overflow check по умолчаю вроде выключен. А вот с проверкой выхода за границы массива можно поиграться. Что, кстати, если я проверки выключу и за границы выползу?
>алсо, обход массива не в том порядке - это да, в десятки раз скорость отличаться может
Я запускал zxy-обход, там на 2 порядка проседение было.
no subject
no subject
>Не в 20, а в 256000 раз больше.
Не понял. В случае с flat имеет 1 массив, а с jagged - один, в который вложено 512, в кадом из которых 128, итого 65537.
no subject
no subject
Я подумал, а как встроенный многомерный массив может выделяться так быстро? Кроме того, что это массив-массивов, которые вылеляются при первом обращении, ничего в голову не приходит. В таком случае, первый проход должен быть много-много медленней остальных. Это объясняет разницу с скорости доступа. Доберусь до комьютера - проверю догадку.
no subject
Они могли сэкономить на инициализации - обнулять память не вручную при выделении, а через механизмы ОС, которые выдают виртуальную память уже обнуленную.
Еще одна причина тормозов второго и третьего вариантов - слишком много вызовов методов, они нифига не инлайнятся, скорее всего. В случае jagged такого нет, там IL проще намного.
no subject
512х512х128 = 512 массивов 512 х 128 = 512 массивов по 512 массивов по 128. Итого 512х512 раз выделить по 128. Не?..
я про CLR не знаток, но если у них generational heap, то да, большой кусок выделить раз нужно из другой области памяти; маленькие массивы могут размещаться в thread-local куске, а то и вообще на стеке остаться.
no subject
no subject
Ещё они должны были сэкономить на вычислении индекса: размеры массива известны в том же scope и они являются power of 2. В случае же самопального Flat3dArray для подобной оптимизации нужно заинлайнить всё по самую ручку, а уж потом применить подобные евристики на вычислениях индекса.
no subject
no subject
no subject
no subject
no subject
no subject