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

[@tenshi]

вмешиваться в чужие элементы — грязная практика

как насчёт поддержки неймспейсов?

[@sunnybear]

что имеется в виду под «чужими элементами»? Все описываемые функции являются методами глобальной переменной _

[@tenshi]

children[child].yeasss = 1;

[@gearss]

Обеспечить уникальность DOM элементов, не расширяя их (expandos), сложно.
Добавить к DOM элементу новое свойство считаю небольшим злом.

Если вас беспокоит, что в будущем появится подобный атрибут — не парьтесь, назовите его хитрозаумно.

[@tenshi]

предлагаешь похачить твой фреймворк и потом протягивать патчи из версии к версии?

[@gearss]

Суть задачи: есть N элементов, надо отфильтровать, оставив уникальные.
Если, по вашему, не расширять DOM элементы новыми атрибутами, и учесть, что не у всех элементов есть идентификатор, то задача решается в O(n^2)
Я это имел ввиду.

Про «мой фреймворк» и «патчи» не понял.

[@tenshi]

нет, задача звучит так: получить коллекцию узлов. предикатом принадлежности к которой является селектор.
если использовать индексы, то выборки можно сделать константными, но при каждом изменении дома будет требоваться перестройка индекса. переидексирование — довольно быстрая операция если грамотно составить конечный автомат по проверке предиката. конечный автомат строится по множеству селекторов один раз при инициализации и далее максимально эффективно проверяет узел. по моим прикидкам — сложность n * log( k ), где n — кол-во узлов и k — кол-во селекторов.

но это всё нафиг не нужно, ибо в хтмл можно использовать свои тэги и вместо «выборок» использовать динамические коллекции возвращаемые getElementsByTagName.

то есть, достаточно один раз вначале программы определить индексы:

var collect( name ){ // для ие эта функция будет немного другой
return collect[ name ];
};
collect.all: document.getElementsByTagName( '*' );
collect.users: document.getElementsByTagName( 'xxx:user' );

и везде использовать:
var users= collect( 'users' );

[@sunnybear]

изменение DOM-дерева в таком случае будет происходить на порядок медленнее (это видно из предыдущих версий, когда кэш сбрасывался — сбрасывался, а не перестраивался! — при работе с DOM). Именно поэтому сброс кэша (и само кэширование) в Sizzle в конце концов убрали.

В последней версии YASS кэширование есть, но сброс его только ручной.

[@tenshi]

заполнение кэша — это гораздо более тяжёлая операция, чем переиндексирование, хотя и растянутая по времени…

[@sunnybear]

давайте возьмем реальную ситуацию:

1) Страница с 1000 DOM-узлами
2) Необходимость выбрать 10 элементов по ID, 20 по классу и 5 по тегу (input, например).

В этом случае переиндексирование всего дерева обойдется крайне дорого, скорее всего, дороже, чем все вышезаявленные выборки.

[@tenshi]

а почему бы не проверить?

[@sunnybear]

напиши, плиз, пример переиндексации — его и проверим
примеры выборки на основе YASS делаются за 5 секунд

[@tenshi]

типа мне больше всех надо? ;-)

[@sunnybear]

да нет, я просто идею не очень улавливаю — как будет выглядеть выборка селекторов в случае упорядоченных DOM-узлов. И как для этого нужно менять DOM-дерево.

[@tenshi]

выборка по селектору так: return this.index['p a.link']
переиндексирование проводить между изменением дома и запросом.
дом, конечно, лучше менять централизовано, но можно попробовать и хэндлеры понавешать…

[@sunnybear]

а индексы какие брать? все возможные CSS-селекторы?

[@tenshi]

нет, использование которых задекларированно вначале программы.
var collect= new Collector({ users: 'a.user', paraghaphs: '#content p' });
…
var users= collect.paragraphs();

[@sunnybear]

а чем это будет отличаться от кэширования тогда?

[@tenshi]

1. мы выносим все селекторы в одно место, а не копипастим его по всему коду.
2. первое обращение происходит без задержек — это актуально при реализации гуи.

[@sunnybear]

нет, я не в том смысле спросил. Я имел в виду, чем это лучше концепции кэширования?

Т.е. мы можем повесить на ready

_.ready(function(){
	window.collect = {
		users: _('a.user'),
		paraghaphs: _('#content p')
	}
});

[@tenshi]

я предполагаю, что пробежаться по всем элементам и проверить к каким селекторам они подходят — быстрее, чем для каждого селектора искать подходящие элементы. кроме случаев использования апи, разумеется. но какой толк от супербыстрой работы под правильными браузерами, если под самыми распространёнными будут супертормоза…

[@sunnybear]

т.е. перебрать 1000 элементов и проверить их наследственность быстрее (через reverse engineering замечу), чем выбрать 10 или 100 5 раз? Что-то я логики не понимаю…

У нас каждая выборка по CSS-селектору не содержит всех элементов. А для элементов «проверить к каким селекторам они подходят» может оказаться более ресурсоемко, чем просто выбрать «правильные» элементы.

Я потому и попросил вариант кода, что навскидку не вижу, чтобы он быстро работал.

[@tenshi]

пусть у нас есть селектор: [p a.link]
классическая последовательность действий: выбрать все [p], для каждого [p] выбрать все [а], по каждому списку [а] пройтись фильтром, который будет регуляркой проверять есть ли класс [link], полученные отфильтрованные списки [a] смёржить.

гораздо быстрее: найти все [a], отфильтровать по классу, отфильтровать по наличию среди предков элемента с именем [p].

для селектора [p>a.link] разница будет ещё более существенна, ибо в первом случае придётся перебирать детей, а во втором — просто проверить родителя.

так вот, при построении индекса будет один большой цикл (вместо множества маленьких) в котором большинство селекторов будут быстро обламываться по имени последнего тэга или по его классу.

[@sunnybear]

:) попробуйте решить данную задачу — получите массу удовольствия.

Когда мы будет находить всех родителей a, мы не только переберем все абзацы, которые действительно являются родителями, так и еще кучу других элементов. Загвоздка в том, что parentNode * N выполняется гораздо медленее, чем getElementByTagName + while

Я реализую описанный подход и наглядно покажу, что быстрее работает

[@sunnybear]

Хмм. Видимо, это тот случай, когда мне придется взять свои слова обратно:

var cycles = 100, newNodes = [];
var s = new Date();
while (cycles--) {
var items = document.getElementsByTagName('img'),
	i = 0,
	item,
	klass,
	idx = 0,
	parent;
while (item = items[i++]) {
	if (!item.yeasss && /(^| )photo($| )/.test(item.className)) {
	    parent = item.parentNode;
    	    do {
		if (parent.nodeName.toLowerCase() === 'div') {
			newNodes[idx++] = !(item.yeasss = 1) || item;
			break;
		}
	} while (parent = parent.parentNode);
        }
}
while (idx--) {
	newNodes[idx].yeasss = null;
}
}
alert(new Date() - s);
cycles = 100, newNodes = [];
s = new Date();
while (cycles--) {
var items = document.getElementsByTagName('div'),
	i = 0,
	item,
	klass,
	idx = 0,
	children,
	child,
	h = 0;
while (item = items[i++]) {
	children = item.getElementsByTagName('img');
h = 0;
	while (child = children[h++]) {
		if (!child.yeasss && /(^| )photo($| )/.test(child.className)) {
			newNodes[idx++] = !(child.yeasss = 1) || child;
		}
	}
}
while (idx--) {
	newNodes[idx].yeasss = null;
}
}
alert(new Date() - s);

В IE6/i7, Fx3 «классический» вариант на 40-60% медленнее «обратного»

P.S. expando нужно в любом случае, ибо все равно надо будет склеивать селекторы, заданные через запятую

[@tenshi]

а вот при построении индекса expando не нужен, ибо не надо мёржить наборы узлов…

[@sunnybear]

что такое «построение индекса»? Мы каждому узлу ставим в соответствие какое-то число из области JavaScript?

Т.е. у нас есть, фактически, закэшированное дерево и массив селекторов, каждый из который состоит из массив номеров узлов в этом дереве?

[@tenshi]

нет, индекс — это набор селекторов, каждому из которых, соответствует массив узлов дерева.

[@sunnybear]

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

У нас есть вторая задача: реверсивный (снизу вверх) поиск узлов по CSS-селектору. В простых случаях он работает раза в полтора-два быстрее, чем обычный (сверху вниз) поиск узлов. Возможно, его идею можно воплотить в YASS. Покопаюсь. Спасибо :)

[@tenshi]

не, разница в способе заполнения «кэша». не по селекторам ищутся узлы (получается множество наборов, которые приходится мёржить), а по узлам определяется к каким селекторам они относятся.

[@sunnybear]

это относится ко второй задаче — у нас на входе все равно набор селекторов, поэтому поиск будет по селекторам (хотя, на самом деле, по узлам).

[@gearss]

спасибо за развёрнутый ответ.
вообще, на селекторах свет клином не сошёлся. по собственному опыту скажу, что в большом проекте использую CSS селекторы (на яваскрипте) всего в 2-3 местах, из 100К+ кода.

самое важное — конечное приложение, а детали реализации не имеют значения.
т.е. сначало лучше сделать что-то полезное, а когда этим начнут пользоваться реально, тогда уже заботиться об оптимизации.

[@sunnybear]

:) давайте еще это дружно John'у напишем и разработчикам YUI? Да, это «грязная» практика, но наиболее быстрая.

[@tenshi]

напиши. заодно спроси, куда у них вдруг пропадает естественная упорядоченность элементов?

[@gearss]

Могу предложить оптимизацию на уровне «Уникальность элементов».

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

Пояснения:
uid — обычный счётчик, увеличивается на 1 при обработке нового селектора.
В данном случае сброс флага ".yeasss" не понадобится, что уменьшает количество обращений к DOM-дереву, и, в конечном итоге, увеличивает производительность.

[@Bonch]

for (child in children) {}

Это медленно работает. Прочитайте все же это: webo.in/articles/habrahabr/78-javascript-constructions-performance/

[@sunnybear]

не очень понятна логика увеличения счетчика: у нас элементы в поддеревьях могут быть «вразброс», т.е. у следующего выбираемого «ребенка» uid не обязательно по порядку будет идти.

В общем, хорошо бы более развернутый пример.

[@Octane]

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

Так вроде еще быстрее в Фаерфоксе:

var j = -1;
while (a[++j]) a[j]++;

Да и короче :-)

[@sunnybear]

в примере с while(i--) так и есть. Просто иногда нужно чуть больше, чем просто ++ — z я так и написал — тогда кэширование в локальную переменную неизбежно

[@Bonch]

Sunnybear, я не спец, но почему бы в FF не генерировать XPATH запрос из css селектора? Возможно, оно будет быстрее работать?

// Получить все h1.title

var headings = document.evaluate('//h1[contains(@class, "title")]', document, null, XPathResult.ANY_TYPE, null)

var thisHeading = headings.iterateNext(); 
var alertText = ''
while (thisHeading) {
  alertText += thisHeading.textContent + "\n";
  thisHeading = headings.iterateNext();
}
alert(alertText);

[@sunnybear]

я пробовал уже XPATH — он работает медленнее (даже без учета перевода CSS-селектора в XPATH). querySelectorAll работает явно быстрее и прозрачнее (и включен в IE8!)