Почему array.include на порядок быстрее, чем set.has в javascript?

Question

Хорошо вырос в C ++, я всегда осознаю, какой алгоритм подойдет для чего. Поэтому, когда я заметил, что приложение стало работать вяло на мобильных телефонах, я сразу же начал смотреть на структуры данных и то, как они представлены.

Я заметил очень странный эффект Array.includes на порядок быстрее, чем Set.has. Несмотря на то, что Set.has гораздо больше возможностей для оптимизации для поиска: вся идея использования набора.

Мой код инициализации (этот код выходит за рамки времени тестирования):

function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
}

const arr = []
for (let i = 0; i < 1000; i+=1) {
    arr.push(i);
};

shuffle(arr);
const prebuildset=new Set(arr);

И тесты:

(new Set(arr)).has(-1); //20.0 kOps/s
arr.includes(-1); //632 kOps/s
(new Set(arr)).has(0); //20.0 kOps/s
arr.includes(0); //720 kOps/s
prebuildset.has(-1); //76.7 kOps/s
prebuildset.has(0); //107 kOps/s

Протестировано с хромом 73.0.3683.103 в Ubuntu 18.04 с использованием https://jsperf.com/set-array-has-test/1

Я могу ожидать, что версии, которые создают набор на лету, будут медленнее, чем прямое тестирование массива на включение. (Хотя я удивляюсь, почему chrome не оптимизирует JIT-массив - я также протестировал использование литерального массива, а литеральный массив против использования переменной вообще не имеет значения). Однако даже готовые наборы на порядок медленнее, чем тест включения массива: даже для самого отрицательного случая (запись не внутри массива).

Почему это? Что за чёрная магия происходит?

РЕДАКТИРОВАТЬ: я обновил тесты, чтобы перетасовать результаты, чтобы не слишком сильно искажать для досрочной остановки для array.includes() - Хотя он больше не работает в 10 раз медленнее, он все еще во много раз медленнее, очень актуален и выходит из строя. что я ожидаю, что это будет.

Answer 1

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

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

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

Например, я отредактировал ваши тесты , просто увеличив размер массива до 100 000.Результаты на моем бедном старом ноутбуке выглядят так:

arr.includes(-1); //3,323 Ops/s
arr.includes(0); //6,132 Ops/s
prebuildset.has(-1); //41,923,084 Ops/s
prebuildset.has(0); //39,613,278 Ops/s

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