Немного о теме топика. Речь пойдет о проблемах интеграции высокой производительности и ограниченности ресурсов. В частности, о реализации решения варианта задачи о рюкзаке применительно к изображениям с CSS Sprites (задача относится к классу NP, время решения в данном случае полиномиально).
Примечание: CSS Sprites — метод клиентской оптимизации (ускорения загрузки веб-страниц), который позволяет использовать одно и то же исходное изображение (разные его части) для отрисовки на экране браузера различных графических элементов (изображений меньшего размера). Благодаря этому можно существенно сократить число HTTP-запросов при загрузке страницы. Также на данный момент возможна, практически, полная автоматизация создания CSS Sprites из исходных отдельных изображений (в частности, проекты Auto Sprites, SpriteMe, Smart Sprites, и ряд других).
На самом деле, мы будем решать только один частный случай указанной задачи создания CSS Sprites — создание HTML Sprites, объединение небольших HTML-изображений в одно, с дальнейшей заменой изображений на прозрачные (1x1 GIF) и добавлением их в качестве фона к данным прозрачным изображениям. Почему это более простая задача? Потому что покрывается только один случай относительно CSS Sprites — у всех изображений фон не повторяется, и размеры жестко заданы. Полный алгоритм разбора CSS Sprites приведен в этой заметке или в книге Реактивные веб-сайты.
Примечание: масштабированные HTML-изображения пока оставим в стороне: они всегда могут быть изменены под заданные размеры с помощью графических библиотек, и дальше задача сводится к уже известной.
Итак. Нам нужно каким-то образом объединить все неповторяющиеся изображения в одно большое с помощью PHP. Как это лучше сделать?
Самый простой и самый действенный вариант: создать «карту» будущего спрайта (двумерный массив, фактически) и перебирать все изображения, проверяя, есть ли для них место. Если нет, то расширять «карту» на нужное число точек. Здесь мы можем иметь дело с совершенно разными по размеру изображениями (первое может быть длинное и низкое, второе — высокое и узкое). Подобрать для них оптимальное местоположение поможет сортировка по «полезности» (как в классической задаче о рюкзаке).
Отправной точкой в полезности может послужить площадь (так как надо расположить все изображения на плоскости наименьшей площади, то логичнее будет начать с самых крупных и в конце забивать оставшееся место самыми маленькими). Здесь нас ждет первый сюрприз: как уже было сказано, у нас могут быть изображения очень разного размера. И 100x100 придется по данной логике располагать перед 500x5 или даже 2000x1.
Как быть? Надо вводить свою функцию «полезности» изображений (фактически, «вредности»: самые «неудобные» изображения должны быть расположены первыми). После нескольких проб выбор остановился на сумме квадратов измерений.
вредность = x*x + y*y
В этом случае 2000x1 вырывается сильно вперед даже 1000x2, что с хорошей вероятностью гарантирует нам, что общая площадь получится оптимальной.
Как пример работы алгоритма можно привести следующее изображение (часть спрайта с www.webogroup.com). Здесь видно, что сначала была расположена ракета (как наиболее крупное), затем НЛО (видимо, второе в очереди), а затем мелкие иконки заполнили остающееся место.
В принципе, на этом основной алгоритм заканчивается: сортируем изображения по «неудобности», затем располагаем их на «карте» спрайта, последовательно эту карту заполняя. Но тут начинается самое интересное.
Сноска: если мы говорим о массовом веб-продукте (взять тот же WordPress), то он должен работать на максимально широком спектре веб-окружений: от виртуальных площадок до серверных кластеров. А на виртуальных площадках очень (ну просто крайне сильно) ограничены ресурсы. Цифры колеблются, но в качестве ориентира можно привести 32 Мб оперативной памяти (иначе даже WordPress будет вываливаться) и 150 МГц процессора (но тут надо иметь в виду PHP-таймаут в 30 секунд, а еще лучше — 5-10 секунд выполнения, чтобы был запас по прочности).
Проблемы с применением данного алгоритма на виртуальной площадке начались именно с памяти. PHP как язык динамического разбора довольно свободно обходится с выделением памяти, и элемент двумерной матрицы занимает (барабанная дробь) 75 байт (для примера стоит привести тот же C, где даже при двойной точности — double word — такой элемент будет занимать 4 байта, а если использовать boolean, что вообще 1 бит, т.е. ровно в 600 раз меньше).
Итак, прикидываем, если 16 Мб у нас точно уйдет на системное ядро, то для преобразования HTML-спрайтов (расчета «карты» изображения) у нас будет оставшиеся 16. Их хватит на
16 000 000 / 75 = 213 333 точек = 461 в квадрате
Т.е. мы можем рассчитать (это ключевое слово: для создания изображения такого же размера с помощью GD требуется гораздо меньше памяти, примерно по 10 байт на 1 точку) квадратный спрайт со стороной около 500 точек.
В принципе, не так уж и плохо. Проблема в том, что на клиентскую производительность это повлияет слабо. Ведь если мы хотим объединять HTML-изображения (размером хотя бы до 100-200 точек), то уже при 10-20 таких изображениях у нас закончится память. А цель стоит — объединить если не пару сотен, то хотя бы гарантированно несколько десятков. И в реальных условиях спрайты имеют обычно сторону в 1000-1500 точек (текущий пример с www.webogroup.com, 1614x1311).
Отлично. Задача тривиальная: снизить потребление памяти при создании «карты» изображения. Самый простой вариант: записывать в одно значение массива состояние не каждой точки, а некоторой группы, например, клетки 4x4 (16 точек, 2^16 = 65536 значений), или же «сжать» одно из измерений в такой же пропорции (т.е. записывать не одну точку по горизонтали, а сразу 16).
Конечный программный код здесь тоже тривиален: надо каким-то образом «разделить» координату (x,y) на саму координату (x1, y1) и ее значение (f(x, y, 1)), и записать новое значение по новой координате. Общая экономия памяти здесь составит, естественно, 16 раз, что нам вполне подходит. Однако, как показали предварительные тесты, даже оптимизированная (т.е. используются остатки от деления и побитовые сдвиги вместо округления и возведения в степень) реализация первого варианта (сжимаем клетками) примерно в 20 раз «тяжелее», чем просто обращение с двумерным массивом. В итоге, мы упираемся в PHP-таймаут (хотя и можем обработать уже большее изображение) — не забываем, что у нас в распоряжении всего 300 Mhz (на самом деле, даже еще меньше: ведь мы не можем эффективно потребить 100% ресурсов площадки, везде нужен запас по прочности).
Более выигрышным здесь оказывается второй вариант (когда сжимаем по одной координате), но соотношение сохраняется. Очередной тупик?
Так, думаем. В самом алгоритме у нас 2 составляющих производительности: проверка, можем ли мы расположить изображение по заданной координате, и число этих самых проверок. Будем считать, что элементарную проверку (вычисление координаты из значения элемента массива) мы уже оптимизировали. Что дальше?
Здесь стоит упомянуть про сущность проверки, свободна ли текущая точка для расположения изображения. Изображение — это большое количество точек (ну, очевидно :). Мы не можем проверить каждую точку изображения относительно всех соответствующих точек на «карте»: в этом просто нет необходимости, и это ну очень ресурсоемко. В самых простых случаях (когда у нас все изображения одинакового размера) мы можем проверить только 1 точку — левый верхний угол. В более сложных (изображения не сильно различаются по размеру, отсортированы по уменьшению «вредности» и имеют соотношения сторон, скажем, не больше 1 к 5) мы можем проверять только 4 точки (угловые). В остальных случаях (когда вообще нет никакой определенности) можно проверить 9 точек (дополнительно середины сторон и центральную точку) — и успокоиться на этом.
Итак, для простейшего случая мы можем сократить число проверок в 9 раз относительно самого сложного варианта. Или хотя бы в 2 раза, если у нас есть предварительные данные о нашем наборе изображений (в этом случае речь идет именно про HTML-изображения, почти всегда они удовлетворяют указанным критериям).
Также мы можем проверять не каждую точку, а, например, через одну точку, через 8 точек, или (при одинаковом размере изображений) вообще увеличивая счетчик на длину и ширину изображений. Это несколько (в самом плохом случае на 7*число изображений) увеличит размеры спрайта, но мы получим существенный выигрыш в процессорной производительности за счет небольшого (1-10%) проигрыша в памяти. Это допустимо.
Уже после двух указанных оптимизаций общее сокращение издержек для средне плохого случая составит 2x8 = 16 раз (изначально у нас процессорные затраты подскочили примерно на эту же величину, поэтому можно считать, что процессор мы побороли).
На выходе: мы уменьшили потребление памяти в 16 раз, не увеличив при этом процессорных издержек (точнее, они увеличились, но очень незначительно, где-то на 30%).
Естественно, везде, где только можно, мы кэшируем.
В результате: возможность первоначального создания и обсчета весьма больших изображений (в примере 4910x163 = 800 000 точек) за весьма небольшое время (порядка 2-5 секунд на самой слабой виртуальной площадке). При этом кэширующий вариант отдается вообще моментально (фактически, время уходит только на замену адресов изображений в HTML-коде) — за 2-10 мс.
Весь исходный код расположен в репозитории WEBO Site SpeedUp (в частности, библиотеки html.sprites или css.sprites.optimize), войдет в WEBO Site SpeedUp версии 1.0.2.
