Оптимизация кода

[green_fr]

Объяснил коллеге, зачем нужно преаллокация памяти. Понимаешь, говорю, если добавлять строчку за строчкой в матрицу, то каждый раз MatLab ищет новое место в памяти, копирует туда уже сделанную матрицу и дописывает новую строчку. А если ты сразу сказал ему, сколько у тебя будет строчек — он сразу столько выделил и ничего никуда не копирует.
Понял? Понял!

Сегодня просматриваю написанный им код. В одном месте ему нужна переменная, которую он запишет в Excel. Размер заранее посчитать нетривиально. Преаллокация на 500000 (пятьсот тысяч) строк, из которых реально заполняется две с чем-то тысячи. Команда записи этой матрицы в Excel рушит мой комп...

Comments

[fima.livejournal.com]

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

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

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

[green-fr.livejournal.com]

Блочной аллокации у него точно нет, про это я читал какие-то их технические статьи, когда нарвался на проблему с дефрагментацией RAM. Мы из-за этого переходили на 64-битную архитектуру, потому что MathWorks нам сказал, что в 32-битной (не помню, у них ли, или у Windows) нет дефрагментации, а в 64-битной есть. А у нас регулярно вылетало out of memory при попытке аллокации матрицы на 200 МБ, например, при свободных (и доступных MatLab) 600 МБ. И проблема зачастую решалась перезагрузкой, после которой память дефрагментировалась автоматически.
Вот в этот момент они чётко рассказали, что каждая матрица у них должна занимать последовательные ячейки памяти.

А про масштаб 1:15 - да, я как-то не задумывался о его вменяемости. Но в примере по ссылке выше у MathWorks примерно такой же результат.

Квадратичный - потому что, если ты переаллокируешь каждые X строчек, и каждый раз копируешь уже накопленные данные, то операция копирования (я предполагаю, что именно она занимает время) будет рости квадратично с размером матрицы. Грубо говоря, ты копируешь 1 строку, потом 2, потом 3 и т.д., а сума арифметической прогрессии - это квадрат. А если аллокация каждые 2^n строчек (как предположил ты), то сумма степенного ряда даст 2^(n+1). То есть, линейный рост с ростом изначальной матрицы.

[fima.livejournal.com]

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

[green-fr.livejournal.com]

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