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

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

Условное ветвление

Начнем с наиболее очевидной составляющей любой логики: ветвления. В любом алгоритме встречается место, в котором нужно выбрать то или иное продолжение в зависимости от проверяемого условия. Давайте рассмотрим следующие примеры. В первом случае у нас три простых вложенных проверки:

var a = 1,
	b = 2,
	c = 3;
if(a == 1) {
	if (b == 2) {
		if (c == 3) {
			...
		}
	}
}

Это, самое интересное, работает так же быстро, как и совмещенный if:

if(a == 1 && b == 2 && c == 3){
	...
}

Однако последний немного меньше по размеру. Если не стоит задача минимального размера кода, то для улучшения читаемости стоит использовать первый вариант. Если же мы минимизируем все, то можно рассмотреть возможность использования if-then-else выражения. Но нужно иметь в виду, что производительность таких конструкций:

var v = a == 1 ? b == 2 ? c == 3 ? 1 : 0 : 0 : 0;

примерно на 10-50% меньше, чем у обычного ветвления, рассмотренного чуть выше.

В том случае, когда все переменные у нас числовые, то проверка равенства их суммы заданной будет выполняться на 5–10% быстрее:

if (a + b + c == 6) {
	...
}

Если же нам нужно проверить просто существование переменных и их неотрицательность (т.е. то, что переменные не undefined, не NaN, не null, не '' и не 0), то следующий вариант будет работать еще на 5–10% быстрее, чем предыдущий случай (и на 10–20% быстрее, чем самый первый пример):

if (a && b && c) {
	...
}

Очень часто нам нужно проверить что-то сложнее, чем просто число. Например, совпадение строки с заданной или равенство объектов. В этом случае нам просто необходимо следующее сравнение:

var a = 1,
	b = 2,
	c = '3';
if (a == 1 && b == 2 && c === '3') {
	...
}

Здесь мы используем сравнение без приведения типов ===, которое в случае нечисловых переменных работает быстрее обычного сравнения на 10–20%.

Выбор в зависимости от строки

Достаточно часто нам нужно выбрать одну из условных ветвей, основываясь на заданной строке. Обычно для этого используется либо методы объекта RegExp (exec, test), либо строковые методы (match, search, indexOf). Если нам нужно просто проверить соответствие строки какому-то регулярному выражению, то лучше всего для этого подойдет именно test:

var str = 'abc',
	regexp = new RegExp('abc');
if (regexp.test(str)) {
	...
}

Такая конструкция отработает на 40% быстрее, чем аналогичный exec:

if (regexp.exec(str)[1]) {
	...
}

Строковый метод match аналогичен методу exec у создаваемого объекта RegExp, но работает на 10–15% быстрее в случае простых выражений. Однако метод search работает чуть медленнее (5–10%), чем test, потому что последний не возвращает найденную подстроку.

В том случае, если регулярное выражение требуется «на один раз», то подойдет более быстрая (примерно на 10% относительно варианта с инициализацией нового объекта) запись:

if (/abc/.test(str)) {
	...
}

Если же, наконец, нам нужно проверить просто нахождение подстроки в заданной строке, то тут бесспорным лидером будет именно indexOf, который работает в 2 раза быстрее разбора регулярных выражений:

if (str.indexOf('abc') != -1) {
	...
}

Точное соответствие и хэши

Давайте теперь рассмотрим следующий вариант регулярного выражения: /a|b|c/. В этом случае нам нужно проверить в заданной строке наличие одного из возможных вариантов (или равенство строки этому варианту). В случае точного соответствия быстрее регулярного выражения (на 50%) будет проверка строки как ключа какого-либо хэша:

var hash = {'a':1, 'b':1},
	str = 'a';
if (h[str]) {
	...
}

Быстрее (на 20%) такого хэша будет только точная проверка строки на определенные значения:

if (str === 'a' || str === 'b'){
	...
}

Если рассмотреть 3 конструкции: вложенный if, switch с соответствующими значениями и проверка значений в хэше, — то стоит отметить следующую интересную особенность. При небольшом уровне вложенности if (если всего значений немного, или мы очень часто выходим по первому-второму значению), конструкции if и switch обгоняют по производительности хэш примерно на 10%. Если же у нас значений много, и они все примерно равновероятны, то хэш отрабатывает в общем случае быстрее уже на 20%. Это в равной степени относится как к установлению значений переменных, так и к вызову функций. Т, е. для создания ветвления с вызовом функций лучше всего использовать именно хэш.

Возвращаясь к YASS. При анализе CSS-селектора можно выделить несколько подзадач, описываемых как «проблема выбора»:

• Ветвление для простого случая выполнено при помощи проверки входной строки через test:
  

  if (/^[\w[:#.][\w\]*^|=!]*$/.test(selector)) {
  	...
  } else {
  	...
  }

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

  switch (firstLetter) {
  	case '#':
  		...
  		break;
  	case '.':
  		...
  		break;
  	case ':'
  		...
  		break;
  	case '[':
  		...
  		break;
  	default:
  		...
  		break;
  }

• Абсолютно аналогичную картину мы наблюдаем для выбора правильного отношения «родитель-ребенок» (>, +, ~, ): тут тоже только switch:
  

  switch (ancestor) {
  	case ' ':
  		...
  		break;
  	case '~':
  		...
  		break;
  	case '+':
  		...
  		break;
  	case '>':
  		...
  		break;
  }

• Наконец, выбор соответствующей проверочной функции для child-модификаторов (first-child, last-child, nth-child, и т.д.) и выбор проверочной функции для атрибутов (~=, *=, = и т.д.) осуществляется уже через специальные хэши:
  

  _.attr = {'': ... , '=': ... , '&=': ... , '^=': ... ... }

  
  

Итоговая таблица

Подводя небольшой итог для различных способов проверки строки, можно составить такую таблицу:

Задача	Средство решения
Проверка числового значения	Обычное сравнение (==)
Проверка нескольких числовых значений	Сравнение их суммы
Проверка, что число не нуль, или проверка на существование	Проверка отрицания к заданной переменной (!)
Разбор строки и выделение частей в массив	String.match(RegExp) или RegExp.exec(String)
Проверка строки на соответствие регулярному выражению	RegExp.test(String)
Проверка строки на наличие подстроки	String.indexOf(String)
Проверка строки на точное соответствие (либо соответствие одному из набора значений)	if без приведения типов (===)
Выбор в зависимости от точного значения (значений 1–2)	Условная конструкция if
Выбор в зависимости от точного значения (значений 3–8)	switch
Выбор в зависимости от точного значения (значений больше 8)	Хэш с ключами, соответствующим значениям

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

Продолжение следует...