Эффективная FIFO-обработка для Node.js и Chrome

[SGordon123]

интересно, если запруженную систему на ц переписать, че будет?

[Kilor]

Будет достаточно много как возможностей, так и неудобств - начиная от ручного управления памятью и заканчивая не всегда удобными способами работы со строками, регулярными выражениями и "асинхронщиной" в C/C++.

[gev]

а если на Rust или Haskell? =)

[rock]

создание и последующая подчистка Garbage Collector'ом подобных избыточных объектов и полей - непозволительная роскошь

При этом, генератор по Symbol.iterator на каждый шаг итерации создает эти самые объекты и поля - хотя, возможно, движок это и оптимизирует.

Вообще, интересно было бы посмотреть на сравнение производительности с очередью, реализованной классически, с цепочкой объектов.

[rock]

Простая очередь:

class Queue {
  #tail = null;
  #head = null;
  length = 0;

  push(value) {
    const element = { next: null, value };
    if (this.#head) this.#head.next = element;
    if (this.#tail === null) this.#tail = element;
    this.#head = element;
    this.length++;
  }

  shift() {
    const element = this.#tail;
    if (element === null) return;
    this.#tail = element.next;
    if (this.#head === element) this.#head = null;
    this.length--;
    return element.value;
  }
}

Результаты:

// Массив:
scale | push, us | shift, us
    0 |       41 |        33
    1 |       22 |        15
    2 |       15 |        10
    3 |       11 |         6
    4 |        9 |         6
    5 |        8 |         9
    6 |        7 |        18
    7 |        7 |        29
    8 |        8 |        30
    9 |        9 |        30
   10 |        9 |        30
   11 |       10 |        31
   12 |        8 |        30
   13 |        8 |        30
   14 |       11 |       975
   15 |       12 |      2425
   16 |       18 |      5109
// Pow2Buffer:
scale | push, us | shift, us
    0 |       38 |        42
    1 |       22 |        16
    2 |       15 |        11
    3 |       13 |         6
    4 |       10 |         3
    5 |        9 |         2
    6 |        8 |         2
    7 |        8 |         2
    8 |        8 |         1
    9 |        9 |         1
   10 |        9 |         1
   11 |        9 |         1
   12 |        8 |         1
   13 |        9 |         1
   14 |        9 |         1
   15 |       10 |         1
   16 |        9 |         1
// Queue:
scale | push, us | shift, us
    0 |       57 |        31
    1 |       34 |        26
    2 |       22 |         9
    3 |       21 |         6
    4 |       15 |         5
    5 |       14 |         4
    6 |       14 |         4
    7 |       13 |         1
    8 |       13 |         1
    9 |       12 |         1
   10 |       12 |         1
   11 |       12 |         1
   12 |       12 |         1
   13 |       12 |         1
   14 |       13 |         2
   15 |       13 |         1
   16 |       16 |         1

Как-то так.

[Kilor]

На самом деле, даже странно, что push в список оказался почти на треть медленнее. Видимо, сказывается пара if'ов - вряд ли создание объекта-обертки.

[rock]

Ну пару if'ов можно сократить и до одного, вот только это сокращает время всего на пол наносекунды.

    if (this.length) {
      this.#head.next = element;
    } else {
      this.#tail = element;
    }

У вас в тесте используется Math.random() - очень тяжелая операция, так что большая часть времени у вас в тесте .push - время исполнения Math.random(). Если его заменить на счетчик, разница будет ещё значительней - примерно, двукратная. Почему - разбираться и копаться в сгенерированном коде лень. Может, особенности доступа к полям / модификации объектов.