18 августа 2019 г.

Внутреннее устройство поисковых методов

Материал на этой странице устарел, поэтому скрыт из оглавления сайта.

Эта глава не обязательна при первом чтении учебника.

Если вы хотите действительно глубоко понимать, что происходит при поиске, то посмотрите эту главу. Если нет – её можно пропустить.

Несмотря на схожесть в синтаксисе, поисковые методы get* и querySelector* внутри устроены очень по-разному.

document.getElementById(id)

Браузер поддерживает у себя внутреннее соответствие id -> элемент. Поэтому нужный элемент возвращается сразу. Это очень быстро.

elem.querySelector(query), elem.querySelectorAll(query)

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

Он просто перебирает все подэлементы внутри элемента elem(или по всему документу, если вызов в контексте документа) и проверяет каждый элемент на соответствие запросу query.

Вызов querySelector прекращает перебор после первого же найденного элемента, а querySelectorAll собирает найденные элементы в «псевдомассив»: внутреннюю структуру данных, по сути аналогичную массиву JavaScript.

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

Оптимизации:

В случае поиска по ID: elem.querySelector('#id'), большинство браузеров оптимизируют поиск, используя вызов getElementById.
Последние результаты поиска сохраняются в кеше. Но это до тех пор, пока документ как-нибудь не изменится.

elem.getElementsBy*(…)

Результаты поиска getElementsBy* – живые! При изменении документа – изменяется и результат запроса.

Например, найдём все div при помощи querySelectorAll и getElementsByTagName, а потом изменим документ:

<div></div>
<script>
  var resultGet = document.getElementsByTagName('div');
  var resultQuery = document.querySelectorAll('div');

  alert( resultQuery.length + ', ' + resultGet.length ); // 1, 1

  document.body.innerHTML = ''; // удалить всё содержимое BODY

  alert( resultQuery.length + ', ' + resultGet.length ); // 1, 0
</script>

Как видно, длина коллекции, найденной через querySelectorAll, осталась прежней. А длина коллекции, возвращённой getElementsByTagName, изменилась.

Дело в том, что результат запросов getElementsBy* – это не массив, а специальный объект, имеющий тип NodeList или HTMLCollection. Он похож на массив, так как имеет нумерованные элементы и длину, но внутри это не готовая коллекция, а «живой поисковой запрос».

Собственно поиск выполняется только при обращении к элементам коллекции или к её длине.

Алгоритмы getElementsBy*

Поиск getElementsBy* наиболее сложно сделать эффективно, так как его результат – «живая» коллекция, она должна быть всегда актуальной для текущего состояния документа.

          var elems = document.getElementsByTagName('div');
alert( elems[0] );
// изменили документ
alert( elems[0] ); // результат может быть уже другой
        

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

Чтобы производительность getElementsBy* была достаточно хорошей, активно используется кеширование результатов поиска.

Для этого есть два основных способа: назовём их условно «Способ Firefox» (Firefox, IE) и «Способ WebKit» (Chrome, Safari, Opera).

Для примера, рассмотрим поиск в произвольном документе, в котором есть 1000 элементов div.

Посмотрим, как будут работать браузеры, если нужно выполнить следующий код:

          // вместо document может быть любой элемент
var elems = document.getElementsByTagName('div');
alert( elems[0] );
alert( elems[995] );
alert( elems[500] );
alert( elems.length );
        

Способ Firefox

Перебрать подэлементы document.body в порядке их появления в поддереве. Запоминать все найденные элементы во внутренней структуре данных, чтобы при повторном обращении обойтись без поиска.

Разбор действий браузера при выполнении кода выше:

Браузер создаёт пустую «живую коллекцию» elems. Пока ничего не ищет.
Перебирает элементы, пока не найдёт первый div. Запоминает его и возвращает.
Перебирает элементы дальше, пока не найдёт элемент с индексом 995. Запоминает все найденные.
Возвращает ранее запомненный элемент с индексом 500, без дополнительного поиска!
Продолжает обход поддерева с элемента, на котором остановился (995) и до конца. Запоминает найденные элементы и возвращает их количество.

Способ WebKit

Перебирать подэлементы document.body. Запоминать только один, последний найденный, элемент, а также, по окончании перебора – длину коллекции.

Здесь кеширование используется меньше.

Разбор действий браузера по строкам:

Браузер создаёт пустую «живую коллекцию» elems. Пока ничего не ищет.
Перебирает элементы, пока не найдёт первый div. Запоминает его и возвращает.
Перебирает элементы дальше, пока не найдёт элемент с индексом 995. Запоминает его и возвращает.
Браузер запоминает только последний найденный, поэтому не помнит об элементе 500. Нужно найти его перебором поддерева. Этот перебор можно начать либо с начала – вперёд по поддереву, 500-й по счету) либо с элемента 995 – назад по поддереву, 495-й по счету. Так как назад разница в индексах меньше, то браузер выбирает второй путь и идёт от 995-го назад 495 раз. Запоминает теперь уже 500-й элемент и возвращает его.
Продолжает обход поддерева с 500-го (не 995-го!) элемента и до конца. Запоминает число найденных элементов и возвращает его.

Основное различие – в том, что Firefox запоминает все найденные, а Webkit – только последний. Таким образом, «метод Firefox» требует больше памяти, но гораздо эффективнее при повторном доступе к предыдущим элементам.

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

Запомненные элементы сбрасываются при изменениях DOM.

Документ может меняться. При этом, если изменение может повлиять на результаты поиска, то запомненные элементы необходимо сбросить. Например, добавление нового узла div сбросит запомненные элементы коллекции elem.getElementsByTagName('div').

Сбрасывание запомненных элементов при изменении документа выполняется интеллектуально.

Во-первых, при добавлении элемента будут сброшены только те коллекции, которые могли быть затронуты обновлением. Например, если в документе есть два независимых раздела <section>, и поисковая коллекция привязана к первому из них, то при добавлении во второй – она сброшена не будет.

Если точнее – будут сброшены все коллекции, привязанные к элементам вверх по иерархии от непосредственного родителя нового div и выше, то есть такие, которые потенциально могли измениться. И только они.
Во-вторых, если добавлен только div, то не будут сброшены запомненные элементы для поиска по другим тегам, например elem.getElementsByTagName('a').
…И, конечно же, не любые изменения DOM приводят к сбросу кешей, а только те, которые могут повлиять на коллекцию. Если где-то добавлен новый атрибут элементу – с кешем для getElementsByTagName ничего не произойдёт, так как атрибут никак не может повлиять на результат поиска по тегу.

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

Разницу в алгоритмах поиска легко «пощупать». Посмотрите сами:

<script>
  for (var i = 0; i < 10000; i++) document.write('<span> </span>');

  var elements = document.body.getElementsByTagName('span');
  var len = elements.length;

  var d = new Date;
  for (var i = 0; i < len; i++) elements[i];
  alert( "Последовательно: " + (new Date - d) + "мс" ); // (1)

  var d = new Date;
  for (var i = 0; i < len; i += 2) elements[i], elements[len - i - 1];
  alert( "Вразнобой: " + (new Date - d) + "мс" ); // (2)
</script>

В примере выше первый цикл проходит элементы последовательно. А второй – идёт по шагам: один с начала, потом один с конца, потом ещё один с начала, ещё один – с конца, и так далее.

Количество обращений к элементам одинаково.

В браузерах, которые запоминают все найденные (Firefox, IE) – скорость будет одинаковой.
В браузерах, которые запоминают только последний (Webkit) – разница будет порядка 100 и более раз, так как браузер вынужден бегать по дереву при каждом запросе заново.

Задачи

Длина коллекции после удаления элементов

Вот небольшой документ:

          <ul id="menu">
  <li>Главная страница</li>
  <li>Форум</li>
  <li>Магазин</li>
</ul>
        

Что выведет следующий код (простой вопрос)?

          var lis = document.body.getElementsByTagName('li');

document.body.innerHTML = "";

alert( lis.length );

А такой код (вопрос посложнее)?

          var menu = document.getElementById('menu');
var lis = menu.getElementsByTagName('li');

document.body.innerHTML = "";

alert( lis.length );

Ответ на первый вопрос

Ответ: 0, пустая коллекция.

<ul id="menu">
  <li>Главная страница</li>
  <li>Форум</li>
  <li>Магазин</li>
</ul>
<script>
  var lis = document.body.getElementsByTagName('li');

  document.body.innerHTML = "";

  alert( lis.length );
</script>

Это потому, что все элементы из BODY удаляются, а коллекция – живая.

Ответ на второй вопрос

Ответ на второй вопрос зависит от браузера. В большинстве браузеров будет 3, коллекция не изменилась, так как она теперь привязана не к BODY, а к элементу, на котором идёт поиск, т.е. к menu.

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

Поэтому результат кода ниже в большинстве браузеров: 3, а в IE10: 0.

<ul id="menu">
  <li>Главная страница</li>
  <li>Форум</li>
  <li>Магазин</li>
</ul>
<script>
  var menu = document.getElementById('menu');
  var lis = menu.getElementsByTagName('li');

  document.body.innerHTML = "";

  alert( lis.length );
</script>

Сравнение количества элементов

Для любого документа сделаем следующее:

          var aList1 = document.getElementsByTagName('a');
var aList2 = document.querySelectorAll('a');
        

Что произойдёт со значениями aList1.length, aList2.length, если в документе вдруг появится ещё одна ссылка <a href="#">...</a>?

Значение aList1 изменится, потому что getElementsByTagName – живая коллекция. Она автоматически дополнится новым элементом a и её длина увеличится на 1.

А вот querySelector, наоборот, возвращает статичный список узлов. Он ссылается на те же самые элементы, что бы не происходило с документом. Поэтому длина aList2.length останется неизменной.

Бенчмаркинг методов поиска в DOM

Какой метод поиска элементов работает быстрее: getElementsByTagName(tag) или querySelectorAll(tag)?

Напишите код, который измеряет разницу между ними.

P.S. В задаче есть подвох, все не так просто. Если разница больше 10 раз – вы решили её неверно. Тогда подумайте, почему такое может быть.

Открыть песочницу для задачи.

Для бенчмаркинга будем использовать функцию bench(f, times), которая запускает функцию f times раз и возвращает разницу во времени:

          function bench(f, times) {
  var d = new Date();
  for (var i = 0; i < times; i++) f();
  return new Date() - d;
}
        

Первый вариант (неверный) – замерять разницу между функциями runGet/runQuery, вот так:

          function runGet() {
  var results = document.getElementsByTagName('p');
}

function runQuery() {
  var results = document.querySelectorAll('p');
}

alert( bench(runGet, 10000) ); // вывести время 1000*runGet
        

Он даст неверные результаты, т.к. getElementsByTagName является «живым поисковым запросом». Если не обратиться к его результатам, то поиска не произойдёт вообще, т.е. runGet ничего по сути не ищет.

…А querySelectorAll всегда производит поиск и формирует список элементов.

Более правильный тест – это не только запустить поиск, но и получить все элементы, как это делается в реальной жизни.

Открыть решение в песочнице.

Получить второй LI

Есть длинный список ul:

          <ul>
  <li>...</li>
  <li>...</li>
  <li>...</li>
  ...
</ul>
        

Как наиболее эффективно получить второй LI?

Можно так:

var li = ul.getElementsByTagName('li')[1];

Или так:

var li = ul.querySelector('li:nth-child(2)');

Оба этих вызова будут перебирать детей UL и остановят перебор на найденном элементе.

А вот так – браузер найдёт все элементы, а затем выберет второй. Это дольше:

var li = ul.querySelectorAll('li')[1];

На практике разница в производительности будет видна только для действительно больших списков, либо при частом выполнении запроса. Браузер перебирает элементы весьма шустро.

Карта учебника