Что будет быстрее работать?

Question

[dollar]

let page = elem.children[1].children[0].children[0].children[0];
//аналогичный поезд может быть из .parentNode

или

let page = document.querySelector('.page'); // То же самое

Если вы знаете подробности о том, как дружат JS и DOM, то интересно услышать ваше мнение.

Comments

[Boris Köln]

Быстрее всего по ID:
let page = document.querySelector('#page');

Answer 1

[Fragman]

document.querySelector ищет по всей странице с помощью обычного перебора элементов, а children[] выполняется за O(1).
Очевидно, что children быстрее, особенно при большом наборе элементов на странице
Доказательство

Comments

[dollar]

Да, но оптимизация селектора может быть сложнее, я точно не знаю. Теоретически движок может искать по хешу, а это O(1)

[Антон Спирин]

Не все так очевидно. Демо. У меня в Chrome поиск по детям более чем в 2 раза медленней в конкретном примере.

[dollar]

Антон Спирин,
Спасибо за тест. Интересно!
Только query, видимо, кешируется до тех пор, пока DOM не будет изменён.
Демо

Более честный пример, где DOM не раздувается:
Демо2
Однако есть мнение, что при удалении или перемещении элемента кеш не сбрасывается.

[dollar]

Антон Спирин,
Демо3
Добавляем элементы до бесконечности, но только после искомого элемента, что даёт query малое число шагов на каждой итерации.

[RAX7]

dollar, Антон Спирин, у меня querySelector в 100 раз медленней получился

spoiler

let container;
let root;
const arr = [];

function genHtml() {
  const ch1 = document.createElement('div');
  const ch2 = document.createElement('div');
  const ch3 = document.createElement('div');
  container = ch3;
  root = ch1;

  ch2.appendChild(ch3);
  ch1.appendChild(ch2);

  for (let i = 0; i < 10000; i++) {
    const el = document.createElement('div');
    el.classList.add(`child-${i}`);
    el.textContent = `child-${i}`;
    container.appendChild(el);
  }

  document.body.appendChild(root);
}

function testChild() {
  const start = performance.now();

  for (let i = 0; i < 10000; i++) {
    let page = root.children[0].children[0].children[i];
    arr.push(page);
  }

  console.log('testChild:', performance.now() - start);
}

function testSelector() {
  const start = performance.now();

  for (let i = 0; i < 10000; i++) {
    let page = document.querySelector('child-' + i);
    arr.push(page);
  }

  console.log('testSelector:', performance.now() - start);
}

genHtml();
testChild();
testSelector();

[Антон Спирин]

dollar, тут множество факторов влияет. Если усложнить древо, то выборка по children начинает просаживаться
Демо

[Антон Спирин]

RAX7, интересно. Потому что одиночным запросом в случайное место querySelector отрабатывает быстрей. Полагаю, движок создает кеш с селекторами и элементами к которым обращался и перед каждым обращением их перебирает.

[dollar]

Антон Спирин, интересно. То есть движок хеширует класс элемента на этапе добавления в DOM?
Если так, то O(1) быстрее, чем O(3). Ну, точнее так нельзя формулировать, но суть понятна, надеюсь.

[RAX7]

Антон Спирин, одиночным запросом толком ничего не померишь. Попробуй сначала с одним тестом померить, потом с другим.
childrens task: 0.20ms (+-0.02ms)
querySelector task: 0.05ms - 0.20ms
как это понимать я не знаю

[dollar]

RAX7, я делал одиночные запуски: 9 из 10 в пользу query. Запускал тест через setTimeout после формирования DOM, менял тесты местами - результат тот же. Что ещё может искажать одиночные результаты?

[Антон Спирин]

dollar, ну насколько я понял не на этапе добавления, а после обращения к нему и потом на всякий перед каждым обращением проверяет там наличие. Так с каждым обращением размер кэша растет и обращение занимает больше времени. По крайней мере эта теория объясняет быстрое одиночное обращение.
Но это все лишь догадки. Интересно было бы узнать как оно происходит на самом деле.

[RAX7]

dollar, посмотри 4й и 5й пункты.
https://threatpost.ru/browser-mitigations-against-...

[Антон Спирин]

RAX7, dollar, тут похоже все гораздо проще. Чем дальше элемент тем дольше querySelector его ищет.
Выборка из последних 100 элементов: Демо 1
Выборка из первых 100 элементов: Демо 2
Похоже querySelector ходит каждый раз по всем элементам по порядку и проверяет класс.

[nrgian]

dollar,

может искать по хешу, а это O(1)

Это очень разные О(1)
То ли дело прямая индексация, то ли еще хэш раскрутить надо.

[dollar]

nrgian, и что сложного "раскрутить" хеш? Это практически обращение по индексу.

[nrgian]

dollar,

и что сложного "раскрутить" хеш? Это практически обращение по индексу.

Никто не говорит, что это дико сложно.
Я сказал, что это сложнее относительно работы с индексом.

Просто посчитайте число операций:
для индекса это 1 сложение, 1 умножение, 1 чтение данных. Правда - на каждом уровне. То есть чем больше уровней, тем медленнее.

А теперь посчитайте число операций поиска по хэшу.

[dollar]

nrgian, это вы интересно считаете. А ничего, что ваше "сложение и умножение" может выполняться за пол такта, а чтение - за 150 тактов? С учётом всех L-кешей, конечно. И вообще, все три операции умещаются в одну команду процессора. Точнее, что с чем складываем и умножаем раскидывается по другим регистрам сначала, а вот откуда мы берем смещения - это внезапно ещё больше чтения. То есть нужно прочитать дополнительно: а) переменную с индексом (смещение) б) переменную с указателем на массив (базу). Итого - три чтения, которыми я и предлагаю ограничиться для примерной оценки действия на x86 процессорах, но уже более близкой к правде.

А что хеш-таблица? Также а) считываем сам хеш б) считываем адрес массива. Небольшое вычисление - берем первые N бит хеша и превращаем в число, я даже это считать не буду за операцию. Дальше по сути операция чтения по индексу, т.к. у нас есть смещение. Правда, попадаем мы не на само значение, а на массив коллизий, где нам нужно простым перебором найти нужный элемент. Но массив этот, как правило, состоит из 1-2 элементов. И даже если чуть больше, то он уже у нас весь закеширован в L-кешах, что делает доступ на порядок быстрее. Так что в общем случае это по сути та же операция чтения. Хорошо, если вам угодно, то будем считать это две операции чтения, предположив, что там ещё 10 чтений из кеша.

Итого 3 чтения против 4 чтений. Большая разница?

Это я ещё не учитываю, что в качестве искомых "значений" снова оказываются указатели (на объекты DOM). И другие накладные расходы, которые одинаковы для обоих случаев, на фоне которых способ доступа уже почти не играет роли.

Даже если скорость по хешу в 2-3 раза дольше, по условиям вопроса у нас 4 взятия по индексу. Кстати, плюс ещё 4 поиска по тому же хешу, ведь children - свойство объекта, не забываем про него. Так что если бы querySelector искал класс по хешу из единой хеш-таблицы документа, это наверняка было бы быстрее.

[nrgian]

dollar,

Также а) считываем сам хеш б) считываем адрес массива. Небольшое вычисление - берем первые N бит хеша и превращаем в число, я даже это считать не буду за операцию.

Эка как вы здорово посчитали!
"Не буду считать", "считаем сам хеш".
Какой длины хеш-то, сколько байт считали-то?

[dollar]

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

[nrgian]

dollar,

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

Многовато?
А что там с коллизиями на такой длине?

[nrgian]

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

[dollar]

nrgian, И хеш мы не считаем, а считываем, то есть учитываем обращение к памяти. Хотя тут вы правы, нужно же ещё посчитать хеш. Я имел в виду, что считываем мы ключ.

Ладно, у нас есть ключ, мы к нему обратились, то есть закешировали, доступ к нему относительно быстрый. Поэтому, далеко не бегая, вычисляем всё на месте - пробегаемся по ключу и считаем хеш. Не забываем, что у нас есть команды процессора (например, старый набор SSE4), и где-то по цене за 0.2 такта на байт мы пробегаемся по небольшому ключу-строке. И нам даже не обязательно все байты проверять, можно ограничиться первыми 50ю байтами к примеру. Вы же помните, что хеш не обязан быть уникальным. В общем, можем добавить еще одно "чтение" к общим затратам. Итого соотношение времени 3 к 5.

Многовато?
А что там с коллизиями на такой длине?

С коллизиями там всё очень хорошо. Шанс коллизии 1/2^64. Именно поэтому, если у нас около 100 ключей для поиска, то имеет смысл размер хеш-таблицы сделать 128 или 256, а индекс у нас - первые (или последние) 8 бит хеша, которые дадут шанс коллизии 1/256, но с учетом размера массива это норм.

[dollar]

nrgian,

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

И что вас смущает? В этом суть хеширования. Мы любые данные (например, ключ), которые "не влазят" в регистр, превращаем в хеш, который уже влазит, чтобы дальше операции сравнения сводились к сравнению хешей, а не исходных данных побайтово. (Конечно, я имею в виду кейс, когда хеширование используется для ускорения поиска, а не для других целей).

[nrgian]

dollar,

И что вас смущает?

Да я вообще слишком уж поторопился, они далеко не эквивалетные.

а) Индекс в массиве - это практически прямое смещение - одно умножение и одно сложение.
б) А имея хэш вы так просто смещение не посчитаете. Там еще операций немало.

Нотация O() говорит только об росте стоимости операции по мере роста данных.
Но ничего не говорит о том, сколько стоит единичная операция

Так вот - единичная операция извлечения по индексу в массиве - это ничтожно малое количество - 1 умножение, 1 сложение.

Поиск по хэшу - это очень много операций.

Исходник на языке, который копилируется в машинный код:

package main

import ("fmt")

var adata []int
var bdata map[int]int

func aFunc(i int) int {
		return adata[i]
}

func bFunc(i int) int {
              	return bdata[i]
}

func main() {
	bdata := make(map[int]int)

	for i:= 0; i<10; i++ {
		adata = append(adata, i)
		bdata[i] = i
	}
	

	fmt.Println(aFunc(5))
	fmt.Println(bFunc(5))
}

Во что сгенерировалось для доступа по индексу массива:

"".aFunc STEXT nosplit size=58 args=0x10 locals=0x8
	0x0000 00000 (aaa.go:8)	TEXT	"".aFunc(SB), NOSPLIT|ABIInternal, $8-16
	0x0000 00000 (aaa.go:8)	SUBQ	$8, SP
	0x0004 00004 (aaa.go:8)	MOVQ	BP, (SP)
	0x0008 00008 (aaa.go:8)	LEAQ	(SP), BP
	0x000c 00012 (aaa.go:8)	FUNCDATA	$0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
	0x000c 00012 (aaa.go:8)	FUNCDATA	$1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
	0x000c 00012 (aaa.go:8)	FUNCDATA	$3, gclocals·9fb7f0986f647f17cb53dda1484e0f7a(SB)
	0x000c 00012 (aaa.go:9)	PCDATA	$2, $1
	0x000c 00012 (aaa.go:9)	PCDATA	$0, $0
	0x000c 00012 (aaa.go:9)	MOVQ	"".adata(SB), AX
	0x0013 00019 (aaa.go:9)	MOVQ	"".i+16(SP), CX
	0x0018 00024 (aaa.go:9)	CMPQ	"".adata+8(SB), CX
	0x001f 00031 (aaa.go:9)	JLS	51
	0x0021 00033 (aaa.go:9)	PCDATA	$2, $0
	0x0021 00033 (aaa.go:9)	MOVQ	(AX)(CX*8), AX
	0x0025 00037 (aaa.go:9)	MOVQ	AX, "".~r1+24(SP)
	0x002a 00042 (aaa.go:9)	MOVQ	(SP), BP
	0x002e 00046 (aaa.go:9)	ADDQ	$8, SP
	0x0032 00050 (aaa.go:9)	RET
	0x0033 00051 (aaa.go:9)	CALL	runtime.panicindex(SB)
	0x0038 00056 (aaa.go:9)	UNDEF
	0x0000 48 83 ec 08 48 89 2c 24 48 8d 2c 24 48 8b 05 00  H...H.,$H.,$H...
	0x0010 00 00 00 48 8b 4c 24 10 48 39 0d 00 00 00 00 76  ...H.L$.H9.....v
	0x0020 12 48 8b 04 c8 48 89 44 24 18 48 8b 2c 24 48 83  .H...H.D$.H.,$H.
	0x0030 c4 08 c3 e8 00 00 00 00 0f 0b                    ..........
	rel 15+4 t=15 "".adata+0
	rel 27+4 t=15 "".adata+8
	rel 52+4 t=8 runtime.panicindex+0

А вот что сгенерировалось при доступе по хэшу:

"".bFunc STEXT size=104 args=0x10 locals=0x28
	0x0000 00000 (aaa.go:12)	TEXT	"".bFunc(SB), ABIInternal, $40-16
	0x0000 00000 (aaa.go:12)	MOVQ	TLS, CX
	0x0009 00009 (aaa.go:12)	MOVQ	(CX)(TLS*2), CX
	0x0010 00016 (aaa.go:12)	CMPQ	SP, 16(CX)
	0x0014 00020 (aaa.go:12)	JLS	97
	0x0016 00022 (aaa.go:12)	SUBQ	$40, SP
	0x001a 00026 (aaa.go:12)	MOVQ	BP, 32(SP)
	0x001f 00031 (aaa.go:12)	LEAQ	32(SP), BP
	0x0024 00036 (aaa.go:12)	FUNCDATA	$0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
	0x0024 00036 (aaa.go:12)	FUNCDATA	$1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
	0x0024 00036 (aaa.go:12)	FUNCDATA	$3, gclocals·9fb7f0986f647f17cb53dda1484e0f7a(SB)
	0x0024 00036 (aaa.go:13)	PCDATA	$2, $1
	0x0024 00036 (aaa.go:13)	PCDATA	$0, $0
	0x0024 00036 (aaa.go:13)	LEAQ	type.map[int]int(SB), AX
	0x002b 00043 (aaa.go:13)	PCDATA	$2, $0
	0x002b 00043 (aaa.go:13)	MOVQ	AX, (SP)
	0x002f 00047 (aaa.go:13)	PCDATA	$2, $1
	0x002f 00047 (aaa.go:13)	MOVQ	"".bdata(SB), AX
	0x0036 00054 (aaa.go:13)	PCDATA	$2, $0
	0x0036 00054 (aaa.go:13)	MOVQ	AX, 8(SP)
	0x003b 00059 (aaa.go:13)	MOVQ	"".i+48(SP), AX
	0x0040 00064 (aaa.go:13)	MOVQ	AX, 16(SP)
	0x0045 00069 (aaa.go:13)	CALL	runtime.mapaccess1_fast64(SB)
	0x004a 00074 (aaa.go:13)	PCDATA	$2, $1
	0x004a 00074 (aaa.go:13)	MOVQ	24(SP), AX
	0x004f 00079 (aaa.go:13)	PCDATA	$2, $0
	0x004f 00079 (aaa.go:13)	MOVQ	(AX), AX
	0x0052 00082 (aaa.go:13)	MOVQ	AX, "".~r1+56(SP)
	0x0057 00087 (aaa.go:13)	MOVQ	32(SP), BP
	0x005c 00092 (aaa.go:13)	ADDQ	$40, SP
	0x0060 00096 (aaa.go:13)	RET
	0x0061 00097 (aaa.go:13)	NOP
	0x0061 00097 (aaa.go:12)	PCDATA	$0, $-1
	0x0061 00097 (aaa.go:12)	PCDATA	$2, $-1
	0x0061 00097 (aaa.go:12)	CALL	runtime.morestack_noctxt(SB)
	0x0066 00102 (aaa.go:12)	JMP	0
	0x0000 65 48 8b 0c 25 28 00 00 00 48 8b 89 00 00 00 00  eH..%(...H......
	0x0010 48 3b 61 10 76 4b 48 83 ec 28 48 89 6c 24 20 48  H;a.vKH..(H.l$ H
	0x0020 8d 6c 24 20 48 8d 05 00 00 00 00 48 89 04 24 48  .l$ H......H..$H
	0x0030 8b 05 00 00 00 00 48 89 44 24 08 48 8b 44 24 30  ......H.D$.H.D$0
	0x0040 48 89 44 24 10 e8 00 00 00 00 48 8b 44 24 18 48  H.D$......H.D$.H
	0x0050 8b 00 48 89 44 24 38 48 8b 6c 24 20 48 83 c4 28  ..H.D$8H.l$ H..(
	0x0060 c3 e8 00 00 00 00 eb 98                          ........
	rel 12+4 t=16 TLS+0
	rel 39+4 t=15 type.map[int]int+0
	rel 50+4 t=15 "".bdata+0
	rel 70+4 t=8 runtime.mapaccess1_fast64+0
	rel 98+4 t=8 runtime.morestack_noctxt+0

Обратите внимание - при обращении по индексу - все нужные операции вообще можно на месте сделать.
При поиске через хэш - вызывается отдельная функция. Потому что вставлять каждый раз ее код в виде inline слишком накладно.

Сама функция поиска по хэшу:

func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {

	if raceenabled && h != nil {

		callerpc := getcallerpc()

		racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast64))

	}

	if h == nil || h.count == 0 {

		return unsafe.Pointer(&zeroVal[0])

	}

	if h.flags&hashWriting != 0 {

		throw("concurrent map read and map write")

	}

	var b *bmap

	if h.B == 0 {

		// One-bucket table. No need to hash.

		b = (*bmap)(h.buckets)

	} else {

		hash := t.key.alg.hash(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))

		m := bucketMask(h.B)

		b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

		if c := h.oldbuckets; c != nil {

			if !h.sameSizeGrow() {

				// There used to be half as many buckets; mask down one more power of two.

				m >>= 1

			}

			oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))

			if !evacuated(oldb) {

				b = oldb

			}

		}

	}

	for ; b != nil; b = b.overflow(t) {

		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {

			if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) {

				return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize))

			}

		}

	}

	return unsafe.Pointer(&zeroVal[0])

}

Функция - очень и очень немаленькая.
Ну и сравните с несколькими ассемблерными инструкциями для доступа по индексу.

[nrgian]

dollar, вывод - О() нельзя брать в качестве отправной точки при сравнении столь разных способов доступа.
Ну и в реальности, конечно, следует замерять, а не умозрительно сравнивать.

Там много чего может быть: и кэширование DOM, и дополнительное индексирование для более быстрого доступа, и отсутствие/наличие JIT и пр. и пр.

Ну и понятно, что чем глубже по иерархии вы пытаетесь по индексу проникнуть - тем более предпочтительнее по хэшу.

Answer 2

[profesor08]

Первое быстрее. Второе удобнее. Если грубо проверить в консоли:

start = Date.now();
for (let i = 0; i < 10000; i++) {
  let el = document.querySelector(".layout__body");
}
console.log(Date.now() - start);

Разница в скорости примерно в три раза, а чтоб ее увидеть в консоли, надо, хотя бы, 10000 раз выполнить действие. И даже так счет 4 против 12 миллисекунд.

Преимущества и недостатки обоих способов очевидны без тестов и скорость тут имеет не приоритетное значение. Любители стрелять себе в ногу могут пользоваться первым способом для выборки. Нормальные же люди пользуются первым способом когда программно надо пробежаться по потомкам/родителям и что-то найти.

Comments

[Alfieros]

Любители стрелять себе в ногу могут пользоваться первым способом для выборки. Нормальные же люди пользуются первым способом когда программно надо пробежаться по потомкам/родителям и что-то найти.

Ответ огонь!)))

[Юрий Костин]

Да, сэр, у вас явно опечатка.

Любители стрелять себе в ногу могут пользоваться первым способом для выборки. Нормальные же люди пользуются первым способом когда программно надо пробежаться по потомкам/родителям и что-то найти.

[profesor08]

Юрий Костин, и в чем же опечатка?

[Юрий Костин]

Хм.. Возможно я вас неверно понял. Противопоставление не очень понятным выглядело. Ожидал, что будет речь про второй метод.

Прошу прощения.

Answer 3

[Alfieros]

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

Comments

[profesor08]

Сломается если придется выполнить это действие после того, как произойдет изменение dom дерева. А если выполнится до, то ссылка на элемент сохранится, даже если он переместится в другое место в дереве. Да даже если он удалится из дерева ).

[Alfieros]

profesor08, Кто же знает в какой момент и для чего он обращается к этому элементу, и что происходит с DOM до и после?) Поэтому второй вариант был предпочтительней, и логичней)

[profesor08]

Alfieros, так вот дело то в нюансах и их надо учитывать

[Сергей delphinpro]

Alfieros, но ведь вопрос в том, что быстрее, а не лучше =))