Я провел бенчмаркинг нескольких алгоритмов очередей

Несколько недель назад я опубликовал фрагмент кода об асинхронной очереди. Я ошибочно предположил, что эта очередь была производительной, но это было не так (я в основном говорил, что она была производительной в соответствии с другими решениями, которые я анализировал в то время), как утверждает @peerreynders.

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

Чтобы упростить бенчмаркинг, я отбросил весь слой обработки async, чтобы сосредоточиться только на самой очереди.

Я протестировал 4 различных алгоритма. Соответствующий код доступен на Github, если вы хотите увидеть различные реализации и бенчмарк:

• первый алгоритм: вызовы Array.shift() (это то, что я использовал); при выгрузке мы просто вызываем shift() в списке элементов
• второй алгоритм: обмен массивами (решение @peerreynders); он использует два массива, один для зачисления элементов, другой для их выгрузки; когда массив выгрузки пуст, массивы быстро изменяются в размере и меняются местами
• третий алгоритм: кольцевой массив; этот код использует два индекса с одним массивом для отслеживания начального и конечного смещения; при выгрузке вызывается операция delete для текущего индекса
• четвертый алгоритм: half size clean up; при достижении половины размера очереди при операции dequeuing массив нарезается на кусочки.

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

Вот результаты:

При постановке/размещении в очередь 1 элемента:

  queue1.ts is the fastest
   2.89x faster than queue4.ts
   4.73x faster than queue2.ts
   11.67x faster than queue3.ts

Для 1000 элементов:

  queue2.ts is the fastest
   1.17x faster than queue4.ts
   7.18x faster than queue1.ts
   10.21x faster than queue3.ts

Для 10 000 элементов:

  queue2.ts is the fastest
   1.2x faster than queue4.ts
   8.63x faster than queue1.ts
   12.81x faster than queue3.ts

Для 100 000 элементов:

  queue2.ts is the fastest
   1.19x faster than queue4.ts: enqueue/dequeue 100_000 items
   8.26x faster than queue3.ts: enqueue/dequeue 100_000 items
   5523.86x faster than queue1.ts: enqueue/dequeue 100_000 items

Первый алгоритм работает лучше, когда в очереди всего несколько элементов. Но производительность резко падает при достижении нескольких сотен элементов, и становится действительно критичной при достижении тысяч элементов, когда для вызова/допуска только одного элемента в очереди из 100 000 элементов требуется 4.5s…

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

Третий алгоритм является более медленной реализацией, после первого. Это происходит из-за операции delete, выполняемой при каждом вызове dequeue().

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

В заключение: Мне нужно обновить мой фрагмент кода 😀.

Последнее замечание: Array.shift() оптимизируется на некоторых платформах, но нам не стоит полагаться на это при реализации алгоритмов, ИМХО.

Кредиты: Фото Adrien Delforge на Unsplash