Къде отива паметта или детективски спрайтове в стил CSS (HTML).

Малко по темата тема. Ще говорим за проблемите на интегрирането на висока производителност и ограничени ресурси. По-специално относно прилагането на решаването на вариант на проблема с раницата във връзка с изображения с CSS спрайтове (проблемът принадлежи към класа NP, времето за решение в този случай е полиномиално).

Забележка: CSS Sprites е техника за оптимизация от страна на клиента (ускоряване на зареждането на уеб страници), която ви позволява да използвате едно и също изходно изображение (различни части от него), за да изобразите различни графични елементи (по-малки изображения) на екрана на браузъра. Благодарение на това можете значително да намалите броя на HTTP заявките при зареждане на страница. Също така в момента е възможна почти пълна автоматизация на създаването на CSS Sprites от оригиналните индивидуални изображения (по-специално проектите Auto Sprites, SpriteMe, Smart Sprites и редица други).

Формулиране на проблема

Всъщност ще решим само един частен случай от посочената задача за създаване на CSS спрайтове - създаване на HTML спрайтове, комбиниране на малки HTML изображения в едно, след това замяна на изображенията с прозрачни (1x1 GIF) и добавянето им като фон към тези прозрачни изображения. Защо това е по-лесна задача? Тъй като е покрит само един случай по отношение на CSS спрайтовете - всички изображения нямат повтарящ се фон и размерите са твърдо кодирани. Пълният алгоритъм за разбор на CSS спрайтове е даден в тази публикация или в Reactive Web Sites.

Забележка: мащабираните HTML изображения засега са оставени настрана: те винаги могат да бъдат преоразмерени, за да отговарят на дадените размери, като се използват графични библиотеки, а след това задачата се свежда до вече познатите.

Така. Трябва по някакъв начин да обединим всички неповтарящи се изображения в едно голямо, използвайки PHP. Кой е най-добрият начин да направите това?

Разтвор в челото

Най-простият и най-ефективен вариант е да създадете "карта" на бъдещия спрайт (всъщност двуизмерен масив) и да преминете през всички изображения, като проверите дали има място за тях. Ако не, разширете "картата" с необходимия брой точки. Тук можем да работим с изображения, които са напълно различни по размер (първото може да бъде дълго и ниско, второто може да бъде високо и тясно). Сортирането по „полезност“ ще ви помогне да изберете оптималното местоположение за тях (както в класическия проблем с раницата).

Отправна точка в полезността може да бъде площта (тъй като трябва да подредите всички изображения в равнината на най-малката площ, би било по-логично да започнете с най-голямата и да запълните останалото пространство с най-малкото в края). Тук ни очаква първата изненада: както вече споменахме, можем да имаме изображения с много различни размери. И по тази логика 100х100 ще трябва да се поставят преди 500х5 или дори 2000х1.

Как да бъдем? Необходимо е да въведете своя собствена функция за „полезност“ на изображенията (всъщност „вредност“: най-„неудобните“ изображения трябва да бъдат поставени на първо място). След няколко опита изборът се спря на сумата от квадратите на измерванията.

В този случай 2000x1 е много по-напред дори от 1000x2, което ни гарантира с голяма вероятност, че общата площ ще бъде оптимална.

Следното изображение (част от спрайт от www.webogroup.com) може да служи като пример за това как работи алгоритъмът. Тук можете да видите, че ракетата беше разположена първа (като най-голямата), след това НЛО (очевидно второто поред), а след това малки икони запълниха останалото пространство.

По принцип тук завършва основният алгоритъм: сортираме изображенията по „неудобство“, след което ги поставяме върху „картата“ на спрайта, последователно запълвайки тази карта. Но тук започва най-интересното.

Споделен хостинг, за да го затрудни

Бележка под линия: ако говорим за масов уеб продукт (вземете същия WordPress), тогава той трябва да работи във възможно най-широк диапазон от уеб среди: от виртуални сайтове до сървърни клъстери. А във виртуалните сайтове ресурсите са много (е, просто изключително) ограничени. Цифрите варират, но като насока можете да дадете 32 MB RAM (в противен случай дори WordPress ще отпадне) и 150 MHz на процесора (но тук трябва да имате предвид времето за изчакване на PHP от 30 секунди и още по-добре - 5-10 секунди изпълнение, така че да има запас от безопасност).

Проблемите с използването на този алгоритъм на виртуален сайт започнаха именно с паметта. PHP, като динамичен парсиращ език, е доста свободен с разпределение на паметта и елемент от двумерна матрица заема (барабанна ролка) 75 байта (например, струва си да цитираме същия C, където дори и с двойна точност - двойна дума - такъв елемент ще отнеме 4 байта, а ако използвате boolean, което обикновено е 1 бит, т.е. точно 600 пъти по-малко).

Така че, нека разберем, ако 16 MB определено ще отидат в ядрото на системата, тогава ще имаме останалите 16 за конвертиране на HTML спрайтове (изчислете "картата" на изображението).

Тези. можем да изчислим (това е ключова дума: отнема много по-малко памет за създаване на изображение със същия размер с 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%).

Естествено, където е възможно, кешираме.

Ние сами кешираме генерираните изображения (защото GD разговорите са доста скъпи). Естествено, ние кешираме набор от изходни файлове, като съпоставяме изображението, така че същият набор да сочи към едно изображение.
Ние кешираме размерите на оригиналните изображения по необходимост (тъй като достъпът до диска е много скъп). Ако планираме да комбинираме няколко десетки файла, тогава искането на техните размери в движение е непростим лукс.
Ние също така кешираме изчислените координати на нашите изображения: в крайна сметка трябва не само да създадем спрайт на тези координати, но и да изпратим CSS правила към HTML документ.
Кешираме всякакви малки неща, като променливи, изчислени в цикъла, и други операции за многократна употреба. Това не дава много по отношение на вече направените точки, но тук всеки удар буквално си струва теглото в злато.