Skip to content

case-study.md

Latest commit

 

History

History
234 lines (188 loc) · 11.1 KB

case-study.md

File metadata and controls

234 lines (188 loc) · 11.1 KB

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

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

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

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

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

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

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

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

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

Предварительно на

  • 10_000 строк из файла используется MEMORY USAGE: без GB 360 MB(c GB 82 MB) скороть работы 1.765 сек
  • 20_000 строк из файла используется MEMORY USAGE: без GB 1292 MB(c GB 92) скороть работы 7.57 сек

Видно что с увеличеине объема данных в 2 раза, память и время увеличивается без GB (1292 / 360 ≈ 3.59) почти в 4 раза это почти квадратичная сложность O(n^2) C GB ситуация лучше, но надо понимать что это большая нагрузка на постоянную очистку.

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

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

Так же добавился тест чтобы проверить используемую память и отслеживать изменения

Feedback-Loop

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

Вот как я построил feedback_loop:

  1. поделил входные данные на по 10_000, 20_000 и тд
    • для быстрого сбора всех отчетов SIZE=10000 make all_reports
    • подобрал данные по которым видны точки роста
    • провел анализ всех отчтетов и поредедлил точку роста
    • внес правки
    • запустил все отчтеты
    • если результат есть, закомитился
    • зациклил весь 2й пункт

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

Для того, чтобы найти "точки роста" для оптимизации я воспользовался в освновном использовались данные из benchmark и memory_profiler, иногда для разнообразия смотрел через qcachegrind.

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

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

  • по отчету memory_profiler первоночально показала что проблема есть тут:
MEMORY USAGE: БЕЗ GB 360 MB (c GB 38 MB)

allocated memory by location
-----------------------------------
287.67 MB  rails-optimization-task2/work.rb:56

allocated memory by class
-----------------------------------
 416.75 MB  Array
=> 
sessions = sessions + [parse_session(line)] if cols[0] == 'session'

подрзреваем что проблема с массивами

  • первым решением заменить сложение массивов на sessions << parse_session(line)
  • по результатам изменений видим что потребление памяти уменьшилось в данном месте c 287 MB -> 0.4 MB что означает уменьшение в 717.5 раз
 MEMORY USAGE: 77 MB

  allocated memory by location
  -----------------------------------
  400.00 kB  rails-optimization-task2/work.rb:56

скорость выполнения почти не поменялась 1.765 -> 1.678075

  • Тк определили что складывать массивы затраратно сразу определяем похожие места
users = users + [parse_user(line)]
9.97 MB  rails-optimization-task2/work.rb:55


users_objects = users_objects + [user_object]
9.57 MB  rails-optimization-task2/work.rb:104

заменяем на операцию добавления в конец массива

  • по резульататам всех изменений получаем
MEMORY USAGE: 58 MB

allocated memory by location
-----------------------------------
  400.00 kB  rails-optimization-task2/work.rb:56
  400.00 kB  rails-optimization-task2/work.rb:55
  rails-optimization-task2/work.rb:104 # даже не попал в отчет


allocated memory by class
-----------------------------------
 110.48 MB  Array
  15.22 MB  String

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

  • для большей наглядности повысим файл нагрузки до 20_000 (SIZE=20000 make all_reports)

замеры через benchmark и сисемный замер памяти

SIZE  20000
MEMORY USAGE: без GB 95 MB (c GB 54 MB)
6.934339999977965

замеры через memory_profiler.rb

MEMORY USAGE: 207 MB
Total allocated: 476.27 MB (887788 objects)
Total retained:  4.14 kB (9 objects)

413.26 MB  rails-optimization-task2/work.rb:102

allocated memory by class
-----------------------------------
 425.92 MB  Array
  30.41 MB  String

подозреваем 102 строку user_sessions = sessions.select { |session| session['user_id'] == user['id'] }, тут происходит работа с select в оффициальной документации

select () - Returns a new array containing all elements of
  • как решение вводим HASH и ищем через него.
sessions_by_users = sessions.group_by { |session| session['user_id'] }

users.each do |user|
  attributes = user
  user_object = User.new(attributes: attributes, sessions: sessions_by_users[user['id']] || [])
  users_objects << user_object
end
  • смотрим на результат, память потребляемя уменьшилась не не сильно с 95 до 84 MB (c GB 54 -> 42)
SIZE  20000
MEMORY USAGE: 84 MB (с GB 42 MB)
0.3854719999944791

но потребляемая память в конкретном месте уменьшилась до

 700.82 kB  rails-optimization-task2/work.rb:100
 633.61 kB  rails-optimization-task2/work.rb:103

allocated memory by class
-----------------------------------
  30.53 MB  String
  14.24 MB  Hash

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

  • исходя из отчетов большую часть памяти занимает цикл, когда мы проходим по всем строкам файла. Посмотрев через qcachegrind, и memory_profiler находим новуб точку роста это split
  MEMORY USAGE: 84 MB(c GB 42 MB)

  9.48 MB  rails-optimization-task2/work.rb:54
  8.14 MB  rails-optimization-task2/work.rb:28
  • заменяб сохранение после split не в массив, а в переннеыю type, user_id, second, third, fourth, fifth = line.split(','), так же parse_user и parse_session убрал split и пользуюсь уже готовыми переменными.
  • Резульатты улучшения появились, уменьшенеие но не крититчно всег она 14 MB
SIZE  20000
MEMORY USAGE: 70 MB (c GB 32 MB)

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

  • Подняд нагрузку до 200_000
  • Воспользовшись подсказкой о том что надо посмотреть на потоковую реализацию, сделал акцент на то а как память уделяется на по объектам:
SIZE  200000
MEMORY USAGE: 515 MB (c GB 274 MB)
4.325512000000344


allocated memory by class
-----------------------------------
 108.42 MB  String
  71.43 MB  Hash
  44.68 MB  Array
  • так же вижу что начинает расти размер память на чтение файла, соответвенно при использовании максимального файла будет только ухуодшаться:
12.94 MB  rails-optimization-task2/work.rb:46

  • Было принято решение переписать логику

    1. читать с файла по строкам и сразу собирать статистику
    2. записывать в файл результат тоже сразу в новый файл
    3. хранить уникальные бразуеры через Set
    4. соотвественно вся статитскика собирается на лету не хранится в памяти

  • Как результат измеенний собераем бенчмарки: без GB

SIZE  200000
MEMORY USAGE: 198 MB
0.8822719999998299

с GB

SIZE  200000
MEMORY USAGE: 20 MB
0.5364520000002813
  • Пробуем запустить _large файл, видем что всё удовлетворяет условиям мы уложились в заданый бюджет.
SIZE  _large
MEMORY IN PROCESS USAGE: 21 MB
MEMORY IN PROCESS USAGE: 21 MB
MEMORY USAGE RESULT: 22 MB
MEMORY USAGE: 22 MB
8.345943000000261

Результаты

В результате проделанной оптимизации наконец удалось обработать файл с данными.
Удалось улучшить метрику системы с потребления памяти примерно в 22 Мб и уложиться в заданный бюджет.

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

Для защиты от потери достигнутого прогресса при дальнейших изменениях программы были написан перформанс тест, который следит за потребляемой памятью