Оптимизация кода
Jan. 17th, 2018 09:42 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
green_frОбъяснил коллеге, зачем нужно преаллокация памяти. Понимаешь, говорю, если добавлять строчку за строчкой в матрицу, то каждый раз MatLab ищет новое место в памяти, копирует туда уже сделанную матрицу и дописывает новую строчку. А если ты сразу сказал ему, сколько у тебя будет строчек — он сразу столько выделил и ничего никуда не копирует.
Понял? Понял!
Сегодня просматриваю написанный им код. В одном месте ему нужна переменная, которую он запишет в Excel. Размер заранее посчитать нетривиально. Преаллокация на 500000 (пятьсот тысяч) строк, из которых реально заполняется две с чем-то тысячи. Команда записи этой матрицы в Excel рушит мой комп...
Понял? Понял!
Сегодня просматриваю написанный им код. В одном месте ему нужна переменная, которую он запишет в Excel. Размер заранее посчитать нетривиально. Преаллокация на 500000 (пятьсот тысяч) строк, из которых реально заполняется две с чем-то тысячи. Команда записи этой матрицы в Excel рушит мой комп...
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2018-01-17 09:19 am (UTC)no subject
Date: 2018-01-17 10:12 am (UTC)no subject
Date: 2018-01-17 09:38 am (UTC)no subject
Date: 2018-01-17 10:14 am (UTC)no subject
Date: 2018-01-17 10:43 am (UTC)no subject
Date: 2018-01-17 01:09 pm (UTC)(проблема аллокации матриц при этом остаётся, даже если вычеркнуть Excel из связки)
no subject
Date: 2018-01-17 01:12 pm (UTC)no subject
Date: 2018-01-17 01:32 pm (UTC)no subject
Date: 2018-01-17 01:50 pm (UTC)no subject
Date: 2018-01-17 02:16 pm (UTC)no subject
Date: 2018-01-17 02:47 pm (UTC)Я думаю, тебе понравится тот факт, что эту программу нам поставила Еврокомиссия в рамках нового закона по контролю страховы компаний :-Р
no subject
Date: 2018-01-17 02:50 pm (UTC)no subject
Date: 2018-01-17 03:02 pm (UTC)Плюс, есть огромное количество людей, которым проще манипулировать данными именно в Excel - для них мы тоже результаты сводим в один файл и отсылаем. То есть это могут быть промежуточные данные, но продолжение рассчётов находится вне нашего отдела, а Excel - это такая lingua franca при общении на разных языках (у нас есть ещё один актуарный отдел, который считает в SAS, и третий на VB.NET).
no subject
Date: 2018-01-17 03:13 pm (UTC)no subject
Date: 2018-01-17 11:00 am (UTC)А то 5е5 указателей зарезервировать - не проблема. Если честно, то и 5е5 256 байтных строк - тоже не проблема.
no subject
Date: 2018-01-17 01:11 pm (UTC)no subject
Date: 2018-01-17 01:27 pm (UTC)no subject
Date: 2018-01-17 01:33 pm (UTC)no subject
Date: 2018-01-17 07:20 pm (UTC)no subject
Date: 2018-01-17 09:01 pm (UTC)no subject
Date: 2018-01-18 07:56 am (UTC)no subject
Date: 2018-01-18 08:39 am (UTC)Прогнал тест. С увеличением в 10 раз количества элементов время, затраченное с преаллокацией увеличивается в 10 раз (логично), но и без преаллокации тоже увеличивается в 10 раз. То есть, отношение остаётся постоянным (в моём примере примерно 1:15). Так что, похоже, ты прав - в моём случае зависимость была бы не линейной, а квадратичной, и отношение времени с преаллокацией : без преаллокации росло бы.
no subject
Date: 2018-01-18 09:13 am (UTC)в тесте ты смешиваешь замеры времени переаллокации и выполнения полезной работы (запись данных). твое соотношение 1:15 очень странное, говорит о том, что матлаб делает еще какую-то чудовищную побочную работу либо переаллокирует как-то сильно через жопу (например, перепроверяет каждую ячейку). если бы он занимался только переаллокацией и записью, то замедление без преаллокации должно было быть несколько процентов максимум, а не в разы.
кстати, вместо переаллокации, они могли бы сделать блочно-цепочечную организацию данных. т.е. аллокировать вначале блок на, скажем, 100 элементов, а при переполнении его, аллокировать новый блок на 100 элементов для новых, а старые никуда не копировать, просто ставить ссылку на продолжение (или хранить список блоков), что-то наподобие файловой системы. тогда будет замедление при векторной обработке, т.к. кэш процессору придется перегружать. тут надо тестировать какой метод лучше подходит для каждой задачи.
я тут слушал лекцию на ютубе про оптимизацию обработки в программах биржевого трейдинга. все идеи надо тестировать на конкретной задаче, практически невозможно предугадать ускорит или замедлит та или иная идея оптимизации выполнение задачи. процессор работает очень хитро, как мы теперь узнали после сообщений о meltdown и spectre.
no subject
Date: 2018-01-18 10:34 am (UTC)Вот в этот момент они чётко рассказали, что каждая матрица у них должна занимать последовательные ячейки памяти.
А про масштаб 1:15 - да, я как-то не задумывался о его вменяемости. Но в примере по ссылке выше у MathWorks примерно такой же результат.
Квадратичный - потому что, если ты переаллокируешь каждые X строчек, и каждый раз копируешь уже накопленные данные, то операция копирования (я предполагаю, что именно она занимает время) будет рости квадратично с размером матрицы. Грубо говоря, ты копируешь 1 строку, потом 2, потом 3 и т.д., а сума арифметической прогрессии - это квадрат. А если аллокация каждые 2^n строчек (как предположил ты), то сумма степенного ряда даст 2^(n+1). То есть, линейный рост с ростом изначальной матрицы.
no subject
Date: 2018-01-18 11:19 am (UTC)no subject
Date: 2018-01-18 10:38 am (UTC)no subject
Date: 2018-01-18 04:24 pm (UTC)есть такая старинная русская пословица: заставь дурака строить таблицу...
разве таблицы в несколько тысяч строк так ощутимо тормозят матлаб,что это имеет смысл?
no subject
Date: 2018-01-18 07:23 pm (UTC)