Совершенно причудливая производительность циклов и циклов CPS в JavaScript - PullRequest
0 голосов
/ 28 мая 2018

Чтобы увидеть, будет ли стиль реализации цикла с передачей продолжений слишком медленным для использования в javascript, я создал JS-Perf, чтобы проверить это с помощью следующего кода:

 const ITERATIONS = 10000;

  function NormalLoop() {
      for (var i = 0; i < ITERATIONS; i++) {
          console.log("loop iteration");
          if (i % 5) {
              console.log("continuing");
              i += 2;
              continue;
          }
          console.log("normally going out");
      }
      console.log("ended loop");
  }

  function WhileTrueLoop() {
      var i = 0;
      while (true) {
          if (i >= ITERATIONS) {
              break;
          }
          console.log("loop iteration");
          if (i % 5) {
              console.log("continuing");
              i += 2;
              i++;
              continue;
          }
          console.log("normally going out");
          i++;
      }
      console.log("ended loop");
  }

  function NonTrampLoop() {
      var i = 0;
      n1(i);
  }

  function n1(i) {
      if (i >= ITERATIONS) {
          n4(i);
          return;
      }
      console.log("loop iteration");
      if (i % 5) {
          console.log("continuing");
          i += 2;
          n3(i)
          return;
      }

      n2(i)
  }

  function n2(i) {
      console.log("normally going out");
      n3(i);
  }

  function n3(i) {
      i = i + 1;
      n1(i);
  }

  function n4() {
      console.log("ended loop");
  }

  function TrampolineSimplistic() {
      var f = function () { return ts1(0) };
      while (f !== null) { f = f(); }
      console.log("ended loop");
  }

  function ts1(i) {
      if (i >= ITERATIONS) {
          return null;
      }
      console.log("loop iteration");
      if (i % 5) {
          console.log("continuing");
          i += 2;
          return function () { return ts3(i); };
      }

      return function () { return ts2(i); };
  }

  function ts2(i) {
      console.log("normally going out");
      return function () { return ts3(i); }
  }

  function ts3(i) {
      i = i + 1;
      return function () { return ts1(i); }
  }

  function TrampolineStreamlined() {

      var f = { cont: t1, i: 0 };
      while (f.cont !== null) { f.cont(f); }
      console.log("ended loop");
  }

  function t1(th) {
      var i = th.i;
      if (i >= ITERATIONS) {
          th.cont = null;
          return;
      }
      console.log("loop iteration");
      if (i % 5) {
          i = i + 2;
          th.i = i;
          th.cont = t3;
          return;
      }

      th.i = i;
      th.cont = t2;
      return;
  }

  function t2(th) {
      var i = th.i;
      console.log("normally going out");
      th.i = i;
      th.cont = t3;
      return;
  }

  function t3(th) {
      var i = th.i;
      i = i + 1;
      th.i = i;
      th.cont = t1;
      return;
  }

Есть пять способов: стандартный цикл for, цикл while-true, использование наивных вызовов функций, использование trampolining и CPS, а также использование trampolining и CPS для предварительного выделения локальных переменных в куче.

Я ожидал, что цикл for будетсамый быстрый, за которым очень тесно следует цикл while-true, затем петли для прыжков на батуте занимают в 2-10 раз больше времени цикла for, а цикл наивной функции - в 10-100 раз длиннее цикла for.

Теперь шокирующепетля для прыжков на батуте, кажется, работает быстрее всего в firefox.Самая медленная петля, кажется, петля while-true!Даже простой цикл вызова функции был относительно быстрым.Как это может быть, когда простой цикл функции увеличивает стек пропорционально количеству итераций, в то время как другие методы используют постоянное пространство стека.

Также простой цикл батута выделяет функцию в куче несколько раз в течение каждоговыполнение.Являются ли движки javascript исключительно агрессивными при оптимизации вызовов функций?Я сделал что-то исключительно глупое в своем коде?

1 Ответ

0 голосов
/ 29 мая 2018

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

Firefox
Iterations      : 30000
NormalLoop      : 0
WhileTrueLoop   : 1
NonTrampLoop    : 22
TrampSimplistic : 2
TrampStreamlined: 1

Chrome
Iterations      : 14000
NormalLoop      : 3
WhileTrueLoop   : 2
NonTrampLoop    : 1
TrampSimplistic : 7
TrampStreamlined: 3

Edge
Iterations      : 5000
NormalLoop      : 0
WhileTrueLoop   : 1
NonTrampLoop    : 3
TrampSimplistic : 11
TrampStreamlined: 3

Chrome
Iterations      : 200000
NormalLoop      : 4
WhileTrueLoop   : 4
TrampSimplistic : 68
TrampStreamlined: 14
* 1003Времена в Firefox довольно последовательны, для других браузеров результаты отличаются, я использовал вывод, который мне показался наиболее последовательным.
...