case-study.md

Case-study оптимизации

Актуальная проблема

В нашем проекте возникла серьёзная проблема.

Необходимо было обработать файл с данными, чуть больше ста мегабайт.

У нас уже была программа на ruby, которая умела делать нужную обработку.

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

Я решил исправить эту проблему, оптимизировав эту программу.

Формирование метрики

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

Гарантия корректности работы оптимизированной программы

Программа поставлялась с тестом. Выполнение этого теста в фидбек-лупе позволяет не допустить изменения логики программы при оптимизации.

Feedback-Loop

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

Вот как я построил feedback_loop: предоставленные данные разбиваются на меньшие объемы (100, 1000 ... 10000 строк), и уже на основе них строятся тесты для фиксирования текущей производительности и используемой памяти в процессе работы как отправной точки. Для этого код самой программы незначительно модифицируется, чтобы поддерживать параметры запуска: имя файла с данными и режим работы Garbage Collector. Самая первая итерация представляла из себя написание тестов производительности (время выполнения программы, объем используемой памяти в процессе работы). В данном случае это можно отнести к шагу Profile & Test & Benchmark. Полученные при первом запуске значения бенчмарка мы можем записать в цели теста для исключения регрессий на последующих итерациях. С этого момента наш feedback loop создан, и мы можем переходить к профилированию и изменению кода, после чего запускать уже написанные тесты для сравнения результатов с отправным шагом (или шагом предыдущей итерации).

Вникаем в детали системы, чтобы найти главные точки роста

Для того, чтобы найти "точки роста" для оптимизации я воспользовался инструментами memory-profiler, ruby-prof и stackprof после завершения первого этапа, в котором исходный код был изменен, чтобы файл с данными читался и обрабатывался построчно, а не загружался целиком в память перед обработкой. Я так же заморозил все строчные литералы.

Вот какие проблемы удалось найти и решить

Ваша находка №1

• какой отчёт показал главную точку роста
  • memory_profiler с профилем на 10.000 строк указал на MEMORY USAGE: 103 MB, Total allocated: 18.92 MB (259923 objects), Total retained: 4.79 kB (9 objects). Строка, где создавалось больше всего объектов - это та, где происходит конвертация формата даты пользовательской сессии. Эта строка станет главной точкой роста
• как вы решили её оптимизировать
  • на этой ознакомительной итерации были удалены избыточные преобразования дат во время обработки полученной информации о сессиях для каждого пользователя
• как изменилась метрика
  • MEMORY USAGE: 76 MB, Total allocated: 11.63 MB (155267 objects), Total retained: 40.00 B (1 objects)
• как изменился отчёт профилировщика
  • на первое место в отчете профилировщика теперь попала строка cols = line.split(','), за ней следует операция помещения прочитанных в строке данных сессии во временный объект.

Ваша находка №2

• какой отчёт показал главную точку роста
  • ruby-prof не смог предоставить отчеты по аллокации памяти на версии 2.7.7 без патчей и на версии 2.7.7 с патчами, поэтому я перешел на ruby-prof в режиме MEMORY с просмотром отчета в qcachegrind. Отчет показал следующую точку роста внутри функции сбора статистики по всем сессиям одного пользователя: String::upcase 27.61% и Array::map 18.07%. Использование памяти на данном этапе составило порядка 40 MB.
• как вы решили её оптимизировать
  • очевидно, что после незначительной модернизации блока кода, ответственного за перебор сессий пользователя, следует довести рефакторинг этого блока до конца, избавившись от ненужных map операций, занимающих память временными объектами, и постаравшись сбор статистики совершать в процессе итерации обхода сессий.
• как изменилась метрика
  • MEMORY USAGE: 67 MB, Total allocated: 10.93 MB (134691 objects), Total retained: 40.00 B (1 objects)
• как изменился отчёт профилировщика
  • String::upcase 12.72% и Array::each 5.87%. Использование памяти на данном этапе составило порядка 40 MB.

Ваша находка №3

• какой отчёт показал главную точку роста
  • после того, как предыдущие итерации оптимизации снизили сложность алгоритма до линейного, стало возможным запускать бенчмарк и профилировщики на полном наборе данных.
  • бенчмарк показал MEMORY USAGE: 1245 MB, Finished in 10.06
  • memory_profiler показал MEMORY USAGE: 7188 MB, Total allocated: 3.55 GB (43771136 objects), Total retained: 40.00 B (1 objects)
  • stackprof на 10.000 строках показал, что уровень аллокаций для блока с обработкой данных по сессиям по-прежнему высок
• как вы решили её оптимизировать
  • т.к. мы уже оптимизировали число итераций и привели алгоритм к линейному, что позволяет совершать обход конечного большого файла с данными целиком, на данной итерации придется сразу записывать итоговые данные по каждому пользователю в конечный файл. Мы все еще создаем промежуточные переменные, куда складываем получаемые на итерациях результаты, а затем передаем эти переменные обратно в верхние циклы обхода строк данных. Число аллокаций говорит нам о том, что все эти переменные для каждой сессии и пользователя так и остаются лежать в памяти, хотя их можно было бы высвободить на каждой новой итерации. Идея здесь в том, чтобы как только мы переходим к следующему пользователю, очищать предыдущие накопленные аллокации для временных вычислений статистики по предыдущему пользователю. Одновременно с этим получится и не раздувать итоговый отчет, который до изменений включает итоговые данные по абсолютно всем пользователям из файла данных.
• как изменилась метрика
  • MEMORY USAGE: 33 MB, Finished in 7.69
• как изменился отчёт профилировщика
  • скриншот из valgrind_massif показал, что в пике во время обработки файла со всеми данными использование памяти не выходит за рамки 37,1 MB
  • MEMORY USAGE: 7089 MB, Total allocated: 3.71 GB (42019996 objects), Total retained: 11.38 kB (6 objects)

Результаты

В результате проделанной оптимизации наконец удалось обработать файл с данными. Удалось улучшить метрику системы со 103 MB при 10.000 строк из исходного файла до 37 MB при всем объеме строк из data_large и уложиться в заданный бюджет.

Время выполнения обработки исходного файла с данными на полном объеме строк составило почти в 2 раза меньше времени, чем в первом задании с оптимизацией по вычислительной мощности.

Защита от регрессии производительности

Для защиты от потери достигнутого прогресса при дальнейших изменениях программы я использовал аналогичные первому заданию тесты на производительность алгоритма при числе строк 100, 1000, 1000, а так же тест на линейность алгоритма