Недавно написал скептический комментарий по поводу необходимости алгоритмических интервью. Вспомнил примеры из своей практики, один из них вполне подходящий, можно сделать патч в opensource проекте.
Разработчики зачастую пишут код (скелет), используя наивные алгоритмы и не используя валидаторы (предполагая изменить код позже либо ошибочно предположив что объем данных будет небольшим).
Не так давно попался один тикет с жалобой на зависание in‑house приложения которое обрабатывает adobe pdf документы (печатает в png изображение для web клиентов).
Приложение использует библиотеку apache pdfbox.
Запустил тест с проблемным pdf документом в котором использовались формы — компьютер «пошел на взлет». Похоже на длинный цикл, хорошо пошел.
Жду пару минут, стало интересно.
Начался тротлинг CPU (перегрев, рабочая коробочка у меня небольшая, мобильная, с воздушным охлаждением и быстро нагревается при большой длительной нагрузке).
Открыл отладчик, нашел проблемный учаток кода в библиотеке pdfbox который держал поток:
Полное имя класса
org.apache.pdfbox.pdmodel.interactive.form.PlainText
Метод разбивает текст хранящийся в строковой переменной «word» на подстроки длиной не более «width» условных пикселей.
Вызов font.getStringWidth() достаточно дорогой.
Классический «наивный» алгоритм с циклом.
Очевидно что разработчики не предполагали что текст в форме может быть большим, либо забыли улучшить алгоритм.
В тестовом pdf документе от клиента строка оказалась больше 100 тыс символов (хороший такой абзац в таблице).
Требуемая ширина столбца подходила для строки длиной 12 символов.
Стоимость наивного алгоритма
В методе используется двойной цикл сканирование строки от 100 тыс символов, до 12, в цикле, с уменьшением стартовой длины на 12 во вложенном цикле.
Сумма арифметической прогрессии равно половине суммы крайних членов прогрессии на их количество, в нашем случае необходимая длина строки в каждой строчке 12 элементов, для получения числа строк делим 100 тысяч на 12, для вычисления стоимости умножаем количество строк на 50 тыс, получаем округленно 416 миллионов вычислений длины строки в 50 тыс элементов (от 100 тыс до 12 символов, в среднем получается 50 тыс символов)
Заглянул в Apache Jira — есть такой тикет: https://issues.apache.org/jira/browse/PDFBOX-5049, висит с 2020 года, последнее обновление в 2024. Скорее всего, исправления уже не будет в этой версии pdfbox. Глянул более свежую версию — то же самое.
Лечение
Первое, что приходит на ум — замена перебора бинарным поиском. Следующая мысль — использовать ожидаемое среднее и максимальное количество символов в столбце — к примеру, принять 20 символов за среднее количество символов (принять как стартовое значение) и 200 за максимум. Вычисление ширины столбца для 100К от большего к меньшему лишено смысла — человек не может читать настолько мелкий текст в таблице.
Можно (и нужно) использовать метрику (среднюю ширину символа) и обновлять в процессе.
Начинаем поиск ширины с 20 символов, затем вычисляем метрику, рассчитываем нужное количество символов зная метрику. В процессе усредняем метрику зная количество символов и ширину рядов. В среднем, думаю что стоимость вычисления ряда будет от 1 до 5 шагов в зависимости от длины строки (ошибка выше на длинных строчках).
Улучшать алгоритм можно до бесконечности, применяя различные стратегии в зависимости от длины текста который нужно нарезать, и ширины столбца.
По быстрому набросал патч, перекрыл класс в исходниках (чтобы не заводить бранч и сборку всего pdfbox, хотя так было бы правильнее) — тест прошел меньше чем за секунду.
Оценим примерную разницу в стоимости алгоритмов (для конкретного примера документа с шириной строки 12 символов в среднем).
Предполагаем что алгоритм вычисления ширины строки линейный, внутри него скорее всего цикл.
Расчеты делаем «на пальцах», на уровне порядка.
Наивный алгоритм: примерно 400 миллионов вычислений строки шириной 50 тысяч символов или 20 миллиардов вычислений ширины строки длиной в 1 символ.
Алгоритм с метрикой: 8333 строки в столбце, по 3 вычисления (скорее всего будет 1) в каждой ряду ширины строки в 12 символов; это будет 25к по 12 или 300 тыс вычислений ширины строки длиной в 1 символ.
Разница в производительности алгоритмов примерно в 20 000 000 000 / 300 000 = 67 000 раз (5 порядков, неплохо).
Возможные последствия
Мы несем ответственность за тех кого приручили, или как может повлиять подобный просчет в SLA в библиотеке которую мы используем, на SLA нашего приложения, и наш карман, собственно.
Если рассуждать формально, то функциональность библиотеки pdfbox не нарушена — нарушен SLA или точнее, наши ожидания о времени выполнения. Используя pdfbox, мы предполагали определенный временные рамки обработки pdf документа, которые повлияли на SLA нашего приложения и которые, возможно, указаны в контракте (а также штрафы за нарушение SLA).
В контексте пользовательского интерфейса SLA может использовать типичный интервал времени от 0 до 10 секунд для обработки запроса от пользователя.
Если операция занимает длительное время, потребуется блокировка повторного выполнения и индикатор статуса (прогресса). Возможно, для этого придется изменить архитектуру приложения (асинхронное выполнение или отдавать результат сразу в виде потока (скачивание в случаe web приложение; это потребует изменения в коде и возможно, замену библиотек, ту же pdfbox на itext, к примеру и тд). В любом случае, длительное время выполнения скорее всего нарушит SLA если приложение декларируется как «real time» операция с временем выполнения до 10 секунд.
Оценка времени выполнения
Оценим время выполнения: предположим что 300 тыс вызовов по вычислению ширины односимвольной строки займет 10 мсек (30 вызовов за миллисекунду). Можно использовать microbenchmark и оценить точнее, но для начала посчитаем «на пальцах».
Наивный алгоритм потратит 670 секунд (терпимо, хотя не факт что пользователь будет ждать 11 минут). Если предположить что улучшенный алгоритм займет 100 мсек (не так и плохо), то пользователь точно не будет ждать печать странички pdf документа 2 часа.
От 11 минут до 2х часов на документ с 100К символов? Неплохо. Под нагрузкой часы могут превратиться в дни.
Оценка энергоэффективности
Оценим по нижней планке.
Предположим что энергопотребление процессора 65 ватт (моя работая станция), 16 ядер, 4 ядра загружены на 100 процентов. Уменьшил энергозатраты, на самом деле нагрузка была выше, но для вычисления с точностью до порядка, это не имеет большого значения.
Примем потребляемую приложением мощность в 33 Вт или 0.033 кВт.
Улучшенный алгоритм: время выполнения 100 мсек — потребленная энергия 0.0 000 009 кВтч (киловатт‑час)
Наивный алгоритм: время выполнения 2 часа — потребленная энергия 0.066 кВтч
У одного из клиентов приложение было развернуто на 500 нодах (максимальное значение). Предположим что документы с подобной формой не исключение а созданы автоматизированным средством и начали применяться массово начиная с определенной даты: результатом будет паралич работы, массовые жалобы, штрафы за нарушение SLA и т. д.
Сравнение потребленной мощности в течении часа на 500 нодах:
0.00 045 кВтч против 33 кВтч. Наивный алгоритм это отопление для зала площадью 300 кв.м, а улучшенный алгоритм с потреблением 0.45 Ваттч это тепло от смартфона.
33 кВтч напомнило мне ЭВМ Урал, которую мы разбирали всей школой на уроках труда лет пять и набрали пару ведер припоя (а также натаскали себе много лампочек домой, к сожалению их рабочее напряжение было не подходящим для фонарика и свечение тусклое).
Выводы
Для начала, оценить качество библиотеки которую собираетесь использовать. pdfbox был достаточно медленным и содержал много ошибок. Не всегда есть возможно выбрать лучшее (по причине неподходящей лицензии или стоимости), руководство может принять решение использовать определенную библиотеку не по техническим причинам.
Второе, улучшить тестирование перед созданием SLA, для лучшего определения качественных характеристик.
Мониторить выполнение задачи в отдельном потоке и прерывать выполнение по таймауту и/или по используемым ресурсам, ограничивать выполнение разумным интервалом времени. Как правило, наивные алгоритмы используют циклы и не блокируют потоки надолго (за исключением эпических случаев использования длинных блокировок, к примеру сетевых вызовов, в цикле).
В данном примере критическим ресурсом оказалось время выполнения, в других случаях ограничением может быть память. Например, обработка больших изображений используя небольшой объем памяти — у меня был проект, в котором для обработки TIFF изображения до 300 мегапикселей в Java требовалось потратить не более 15 мегабайт памяти, но это материал для другой публикации.