В нашем проекте возникла серьёзная проблема.
Необходимо было обработать файл с данными, чуть больше ста мегабайт.
У нас уже была программа на ruby, которая умела делать нужную обработку.
Она успешно работала на файлах размером пару мегабайт, но для большого файла она работала слишком долго, и не было понятно, закончит ли она вообще работу за какое-то разумное время.
Я решил исправить эту проблему, оптимизировав эту программу.
Для начала я запустил небольшой бенчмарк, чтобы понять, какая асимптотика у программы. Для каждого измерения взял первые n строк из файла с полными данными. Результаты бенчмарка выглядели так:
user system total real
line_count = 10 0.001417 0.000258 0.001675 ( 0.011769)
line_count = 50 0.001417 0.000258 0.001675 ( 0.011346)
line_count = 100 0.002608 0.000000 0.002608 ( 0.013075)
line_count = 500 0.002582 0.009544 0.012126 ( 0.022563)
line_count = 1000 0.009544 0.010132 0.019676 ( 0.030331)
line_count = 5000 0.218717 0.020935 0.239652 ( 0.253703)
line_count = 10000 0.979160 0.000000 0.979160 ( 1.010272)
line_count = 20000 4.887525 0.017847 4.905372 ( 4.930110)
line_count = 30000 13.817134 0.099889 13.917023 ( 13.935027)
line_count = 40000 29.488743 0.109932 29.598675 ( 29.619598)
line_count = 50000 50.501303 0.109971 50.611274 ( 50.648952)
График зависимости времени работы программы от объёма входных данных выглядел так:
Судя по графику, программа работала с асимптотикой O(n^2).
Для того, чтобы понимать, дают ли мои изменения положительный эффект на быстродействие программы я придумал использовать такую метрику: время работы программы на полном объёме данных.
Программа поставлялась с тестом. Выполнение этого теста в фидбек-лупе позволяет не допустить изменения логики программы при оптимизации.
Для того, чтобы иметь возможность быстро проверять гипотезы я выстроил эффективный feedback-loop, который позволил мне получать обратную связь по эффективности сделанных изменений за время, которое у вас получилось
Вот как я построил feedback_loop:
- Запуск профилировщик
rbspyна малом объёме данных. - Анализ отчёта профилировщика и выявление главной точки роста.
- Оптимизация главной точки роста.
- Запуск теста идущего в комплекте с программой.
- Запуск бенчмарка на малых объёмах данных и проверка попадания в бюджет.
- Закрепление изменений в системе контроля версий.
- Обновление бюджета в бенчмарке.
Для того, чтобы найти "точки роста" для оптимизации я воспользовался инструментами, которыми вы воспользовались
Вот какие проблемы удалось найти и решить
-
Использовался отчёт профилировщика
rbspyпри запуске на файле с 10000 строк. Отчёт показал, что больше всего времени программа тратит на выборку сессий по пользователю из массива сессий. -
Было принято решение вынести эту строку из цикла и вместо этого выполнить
Array#group_by. -
Время выполнения программы на файле с 10000 строками уменьшилось с 1.010272 до 0.283054 секунды.
-
Также уменьшилось время выполнения программы на файлах большего размера.
user system total real line_count = 11 0.001461 0.000487 0.001948 ( 0.012805) line_count = 51 0.002695 0.000898 0.003593 ( 0.009555) line_count = 100 0.003591 0.001197 0.004788 ( 0.010995) line_count = 501 0.006650 0.000000 0.008918 ( 0.019601) line_count = 1000 0.012564 0.000000 0.015094 ( 0.029157) line_count = 5000 0.050438 0.019783 0.073774 ( 0.103414) line_count = 10000 0.160801 0.000000 0.170127 ( 0.283054) line_count = 20001 0.400933 0.048675 0.455922 ( 0.547208) line_count = 30000 0.637398 0.019211 0.666364 ( 0.770074) line_count = 40000 0.978085 0.010174 1.003803 ( 1.200759) line_count = 50000 1.290851 0.019795 1.325995 ( 1.518988) -
График зависимости времени работы программы от объёма входных данных стал выглядеть так (синие точки):
Судя по изменившейся форме графика можно сделать вывод, что асимптотика стала линейной в данном диапазоне обрабатываемых строкб возможно на более крупном масштабе мы увидим ещё одну степенную асимптоту. -
Отчёт профилировщика изменился значительно: исправленная проблема перестала быть главной точкой роста, время подключения библиотек стало основным.
- какой отчёт показал главную точку роста
- как вы решили её оптимизировать
- как изменилась метрика
- как изменился отчёт профилировщика - исправленная проблема перестала быть главной точкой роста?
- какой отчёт показал главную точку роста
- как вы решили её оптимизировать
- как изменилась метрика
- как изменился отчёт профилировщика - исправленная проблема перестала быть главной точкой роста?
В результате проделанной оптимизации наконец удалось обработать файл с данными. Удалось улучшить метрику системы с того, что у вас было в начале, до того, что получилось в конце и уложиться в заданный бюджет.
Какими ещё результами можете поделиться
Для защиты от потери достигнутого прогресса при дальнейших изменениях программы о performance-тестах, которые вы написали