Преимущество очереди denque перед javascript массивом, внутренняя реализация и немного про движок v8.
Пару лет назад я работал над драйвером tarantool для nodejs. Одной из задач было ускорить очередь запросов в базу, которая была дефолтным js массивом.
v8 под капотом старается оптимизировать операции над структурами данных, в том числе над массивами. Например, массивы с разными типами элементов будут оптимизированы по-разному и скорость выполнения операций над ними будет разная. Подробнее почитать про это можно тут.
Основная оптимизация Denque заключается в «ручном» управлении частотой увеличения массива, содержащего очередь. Например, каждый раз когда вызывается нативный Array.push(), длина массива увеличивается: аллоцируется новая память и весь массив копируется туда с добавлением нового элемента. Частое увеличение массива влияет производительность, поэтому в denque длина массива увеличивается в два раза каждый раз, когда в нем уже не остается места для будущих элементов. Тем самым сильно сокращая количество аллокаций. Кроме того, denque редко укорачивает массив, что также ускоряет shift и unshift.
Очередь представляет собой js массив, использует указатели на начало и конец и шестнадцатеричную маску, равную размеру массива минус 1. Внутренние методы получают индекс нужного элемента в массиве после наложения индекса в очереди на маску.
Пару лет назад я работал над драйвером tarantool для nodejs. Одной из задач было ускорить очередь запросов в базу, которая была дефолтным js массивом.
Производительность операций над массивами в js
v8 под капотом старается оптимизировать операции над структурами данных, в том числе над массивами. Например, массивы с разными типами элементов будут оптимизированы по-разному и скорость выполнения операций над ними будет разная. Подробнее почитать про это можно тут.
Как сделать массив быстрее
Основная оптимизация Denque заключается в «ручном» управлении частотой увеличения массива, содержащего очередь. Например, каждый раз когда вызывается нативный Array.push(), длина массива увеличивается: аллоцируется новая память и весь массив копируется туда с добавлением нового элемента. Частое увеличение массива влияет производительность, поэтому в denque длина массива увеличивается в два раза каждый раз, когда в нем уже не остается места для будущих элементов. Тем самым сильно сокращая количество аллокаций. Кроме того, denque редко укорачивает массив, что также ускоряет shift и unshift.
Бенчмарк Shift-Push, 1000 элементов:
Platform info:
Darwin 18.7.0 x64
Node.JS 10.15.3
V8 6.8.275.32-node.51
Intel® Core(TM) i5-5257U CPU @ 2.70GHz × 4
denque shift-push x 46,107,484 ops/sec ±1.71% (82 runs sampled)
native array shift-push x 3,703,895 ops/sec ±1.77% (88 runs sampled)
Darwin 18.7.0 x64
Node.JS 10.15.3
V8 6.8.275.32-node.51
Intel® Core(TM) i5-5257U CPU @ 2.70GHz × 4
denque shift-push x 46,107,484 ops/sec ±1.71% (82 runs sampled)
native array shift-push x 3,703,895 ops/sec ±1.77% (88 runs sampled)
Реализация
Очередь представляет собой js массив, использует указатели на начало и конец и шестнадцатеричную маску, равную размеру массива минус 1. Внутренние методы получают индекс нужного элемента в массиве после наложения индекса в очереди на маску.
Cсылка на автора библиотеки.