Pull to refresh

Архитектура YASS. Часть 2: выборка по CSS-селектору

JavaScript *
Статья о модульной загрузке была первой ласточкой в ряду заметок, в которых я собираюсь шаг за шагом рассказать, на каких принципах построена YASS, и каковы были результаты тестирования на максимальную производительность каждой части этой библиотеки. Но обо всем по порядку.

Постановка задачи



Насчет с самого простого: чего мы хотим добиться? Мы хотим, задав произвольную строку CSS-селектора, соответствующую спецификации, получить на выходе массив из всех элементов, соответствующих этой самой строке. Вроде пока все просто.

В качестве иллюстрации спецификации можно привести следующие примеры:

//вернет элемент с идентификатором my_id
querySelectorAll('#my_id')
//вернет все элементы с классом external
querySelectorAll('.external')
//вернет все абзацы на странице
querySelectorAll('p')


Однако уже тут можно отметить один момент: очень часто нам нужно выбрать просто элемент по его идентификатору или найти все элементы с определенным классом. Эти операции встречаются достаточно часто во всех JavaScript-библиотеках, поэтому они должны выполняться максимально быстро. Запускать весь механизм анализа входной строки селектора просто в том случае, когда нам нужно вернуть один-единственный элемент, заданный с помощью идентификатора, крайне неосмотрительно. Здесь мы можем воспользоваться принципом ленивого программирования: «не делай того, чего можно не делать», — и достаточно сильно ускорить работу для простейших случаев.

Если посмотреть на современные JavaScript-библиотеки, то везде такая проверка уже осуществляется с помощью регулярного выражения. И тут сразу же небольшая хитрость: инициализация любого регулярного выражения обходится достаточно дорого в браузерах (хотя сложность выражения начинает влиять на затраченное время только при большой его длине), и разумно было бы вообще без него обойтись. И когда можно использоваться просто indexOf для проверки подстроки — этим (в элементарных случаях) всегда нужно пользоваться.

В том же случае, если регулярное выражение обеспечивает корректность, и замена его никак не приведет к потере читаемости кода и непонятному выигрышу (или даже проигрышу) в скорости выполнения, можно заменить, например, exec на связку test и charAt / substr: это позволит увеличить производительность примерно на 20%. Если данный участок кода выполняется в цикле многократно, это может оказаться достаточно существенным.

В YASS данная задача решена следующим образом:

//проверяем, удовлетворяет ли селектор простому случаю
if (/^[\w[:#.][\w\]*^|=!]*$/.test(selector)) {
//в случае положительного результата инициализируем переменную,
//которая отвечает за '#', '.' , ':' или '[' в начале селектора
	var firstLetter = selector.charAt(0);
	...
}


От простого к сложному



Но давайте рассмотрим, как решена общая задача по разбору CSS-селекторов. Если принять во внимание, что селектор может быть задан в виде p a.link, form input[type=radio], то логику его разбора можно схематично записать в виде:

  • Выбираем последовательности селекторов, которые находятся между запятыми. Далее работаем с каждой последовательностью в отдельности. На выходе все последовательности объединяем в итоговый массив (sets).
  • В последовательности селекторов у нас есть набор элементарных селекторов, которые «вложены» друг в друга (для нашего примера это p a.link). Нам нужно разбить последовательность на части и разобрать каждую такую часть, учитывая, что родительскими элементами для следующей части будут являться выбранные элементы из предыдущей. За «превращение» дочерних узлов в родительские (прямо процесс взросления получается) отвечает массив nodes.
  • Каждый элементарный элемент уже придется разбирать с помощью регулярного выражения, чтобы вычленить части, отвечающие за идентификатор, класс и модификаторы CSS 2/3. Разбирать быстрее всего при помощи exec, а потом записывать в переменные части полученного массива:
    single = regexp.exec(single);
    tag = single[1];
    id = single[2];
    ...
  • И наконец, третий цикл проходится по всем родительским элементам и пытается выбрать из них дочерние узлы, соответствующие заданным в CSS-селекторе параметрам.


Как мы видим, основная логика данной задачи включает, как минимум, одно регулярное выражение (использование indexOf и substring будет при такой сложности намного более ресурсоемко) и 3 цикла (которые нужно сделать максимально быстрыми). Недавно была статья о наиболее быстрых методах перебора элементов, я не буду перечислять все возможности, просто сделаю акцент на некоторых аспектах.

Перебор массива



Пусть у нас объявлен некоторый массив a, с элементами которого мы совершаем какие-либо действия. Нам нужно перебрать все элементы строго по возрастанию (порядок важен), т.е. просто while(i--) мы использовать не можем. Наиболее распространенным сейчас способом будет обычный for:

var j = 0,
	item,
	len = a.length;
for (var j=0, item = a[j]; item; item = a[j++]) {
	item++;
}


Естественно, он на 30–40% медленнее следующего while:

var j = 0,
	item,
	len = a.length;
while (j < len) {
	item = a[j++];
	item++;
}


Однако если нам нужно выполнить какие-либо действия с элементом массива, то без кэширования его в локальную переменную никак не обойтись. В этом случае следующий вариант с while (через проверку существования элементов при инкременте) будет еще быстрее на 5–10%:

var j = 0,
	item;
while (item = a[j++]) {
	item++;
}


Очевидно, что для всех трех циклов в YASS используется именно он.

Если же нам абсолютно не важен порядок элементов (например, просто нужно найти нужный или вернуть false), то логично будет воспользоваться обратным while:

while (idx--) {
	sets[idx].yeasss = null;
}


Именно такой код используется для сброса у элемента флага, отмечающего состояние «выбран». Давайте рассмотрим, зачем этот флаг нужен, и зачем его сбрасывать.

Уникальность элементов



Одной из основных проблем в ходе выбора элементов по CSS-селектору является корректность конечного набора. В случае div p у нас могут оказаться вложенные div, и если мы просто переберем все родительские элементы и объединим получившиеся дочерние, то конечный набор будет содержать дубли. Чтобы избежать такого рода ошибок, нам нужно как-то отмечать элементы, которые мы выбрали.

Это стандартная задача, и решается она, в принципе, тоже стандартно: во всех библиотеках заводится определенное свойство DOM-узлов, которое отвечает за состояние «выбран». У этого подхода есть несколько минусов (например, нужно расширить это решение на случай асинхронных выборок элементов и понимать, что каждое обращение к элементам дерева ресурсоемко), но в подавляющем большинстве случаев оно позволяет устранить неуникальность элементов.

Схематично представить работу данного флага можно следующим образом.

for (child in children) {
	if (!children[child].yeasss) {
		if (last) {
			children[child].yeasss = 1;
		}
		newNodes = children[child];
	}
}


В процессе перебора нужных нам дочерних узлов мы проверяем, выставлен ли у этого потомка флаг yeasss (естественно, что кроме этой проверки мы должны удостовериться, что данный потомок нам действительно нужен). Далее мы выставляем флаг только в том случае, если работаем с последним звеном в цепочке «детей-родителей», и записываем дочерний узел в массив новых узлов, которые станут «родителями» на следующей итерации цикла.

Прекрасно видно, что флаг yeasss будет выставлен только в том случае, если мы работаем с последним звеном: для промежуточных звеньев он никогда не будет выставлен, поэтому на родительские элементы мы никакие ограничения не распространяем. Вполне возможно, что можно было бы сокращать массив родителей на каждой итерации (чтобы не выбирать заведомо один и те же элементы), однако, данный шаг не увеличит (в общем случае только уменьшит) производительность выборок, поэтому здесь такой подход и не используется.

Сброс флага (о котором шла речь в предыдущем разделе) осуществляется уже для окончательного массива элементов (после завершения всех циклов) и необходим как для корректности дальнейших выборок, так и для предотвращения утечек памяти в IE (расширенные свойства элементов вызывают микро-утечки в IE6/7).

Подводя черту



YASS создавалась и создается для поиска и реализации наиболее производительных методов для решения определенного круга задач. Ее можно использовать как в учебных целях, так и в чисто практических (например, для составления набора неиспользуемых на сайте CSS-селекторов — с помощью YASS это реализуется быстрее всего).

Продолжение следует...
Tags:
Hubs:
Total votes 25: ↑23 and ↓2 +21
Views 894
Comments Comments 41