Производительность ReasonML против императивного ванильного JavaScript

Отказ от ответственности: я новичок в ReasonML.

Недавно я начал играть с ReasonML и заметил большую разницу в производительности по сравнению с ванильным JavaScript. Вот мои примеры простой функции решения головоломки (головоломка взята с: https://adventofcode.com/2015/day/1)

ReasonML

let head = str =>
  switch (str) {
  | "" => ""
  | _ => String.sub(str, 0, 1)
  };

let tail = str =>
  switch (str) {
  | "" => ""
  | _ => String.sub(str, 1, String.length(str) - 1)
  };

let rec stringToList = str =>
  switch (str) {
  | "" => []
  | _ => [[head(str)], tail(str) |> stringToList] |> List.concat
  };

let rec findFloor = code =>
  switch (head(code)) {
  | "" => 0
  | "(" => 1 + findFloor(tail(code))
  | ")" => (-1) + findFloor(tail(code))
  | _ => 0
  };

let findFloorFold = code => {
  let calc = (a, b) =>
    switch (b) {
    | "" => a
    | "(" => a + 1
    | ")" => a - 1
    | _ => a
    };

  code |> stringToList |> List.fold_left(calc, 0);
};

JavaScript

const solve = code => {
  let level = 0;
  for (let i = 0, l = code.length; i < l; i++) {
    const el = code[i];
    if (el === "(") {
      ++level;
      continue;
    }
    if (el === ")") {
      --level;
      continue;
    }
  }
  return level;
};

Результаты

  • JavaScript: 5 мс
  • ReasonML (рекурсивный): 470 мс
  • ReasonML (нерекурсивный): 7185 мс

Ожидается ли это, или мои реализации функции ReasonML слишком медленные?

Заранее спасибо за разъяснения/предложения.

Следует признать, что второе решение (не rec) работает медленно из-за преобразования строки в массив, но это связано с тем, что в ReasonML строка не представлена ​​списком символов.


person skay-    schedule 15.09.2018    source источник
comment
В вашей нерекурсивной реализации вместо преобразования строки в список и последующего обхода списка вы могли бы использовать String.iter для применения вашей функции к каждому символу?   -  person pstrjds    schedule 15.09.2018
comment
String.iter возвращает тип unit, поэтому я хочу иметь возможность накапливать результат операций (возможно, я неправильно понял ваше предложение ..).   -  person skay-    schedule 15.09.2018
comment
Я думаю, что в целом ожидается, что JavaScript, созданный на другом языке, будет менее оптимизирован, чем JavaScript, настроенный вручную, но разница кажется слишком большой. Сгенерированный JavaScript также, похоже, имеет много накладных расходов из-за загрузки библиотек, List. методов и большого количества вызовов функций.   -  person Slai    schedule 15.09.2018
comment
Я просто выбрасывал это туда. Я никогда не писал ReasonML, и прошло почти 20 лет с тех пор, как я написал какой-либо стандартный ML, но я, кажется, припоминаю, что существовал способ переноса аккумулятора как части функции, которую вы передавали итератору.   -  person pstrjds    schedule 15.09.2018
comment
Ваша stringToList конверсия кажется ужасно неэффективной. Я не знаю ReasonML, я бы ожидал встроенной функции преобразования в стандартной библиотеке (или, по крайней мере, string в array(char)). Хотя я бы выбрал Str.split(regex "")   -  person Bergi    schedule 15.09.2018


Ответы (1)


Вы можете написать тот же императивный код в Reason, что и в JS, и на самом деле он будет быстрее (на 30% на моем компьютере):

let findFloorImperative = code => {
  let level = ref(0);
  for (i in 0 to String.length(code) - 1) {
    switch (code.[i]) {
    | '(' => level := level^ + 1
    | ')' => level := level^ - 1
    | _   => failwith("invalid code")
    }
  };
  level^
};

И это рекурсивное решение почти такое же быстрое:

let findFloorRecursiveNoList = code => {  
  let rec helper = (level, i) =>
    if (i < String.length(code)) {
      switch (code.[i]) {
      | '(' => helper(level + 1, i + 1)
      | ')' => helper(level - 1, i + 1)
      | _   => failwith("invalid code")
      }
    } else {
      level
    };

  helper(0, 0)
};

Результаты сравнительного анализа:

Reason, imperative:            19,246,043 ops/sec
Reason, recursive, no list:    18,113,602 ops/sec
JavaScript, imperative:        13,761,780 ops/sec
Reason, recursive, list:       481,426 ops/sec
Reason, folding, list:         239,761 ops/sec

Source: re:bench

person glennsl    schedule 15.09.2018
comment
Хм, если вы проведете стресс-тестирование функций, вы увидите, что JavaScript работает быстрее. (см. ответ Reddit: reddit.com/r/reasonml/comments/9g10m2 /) Это интересно, мы перешли от версии Js, которая была на 15 % медленнее, к версии Reason, которая была на 3 % быстрее. Кроме того, по мере масштабирования рекурсия Reason, хотя и была самой медленной, в обоих случаях увеличила производительность на 27%. - person skay-; 16.09.2018
comment
Каррирование по умолчанию @wegry? - person glennsl; 12.10.2018
comment
@glennsl Я имел в виду использование [@bs] для принудительного удаления. Похоже, что codegen в этом случае не пострадал. Думаю, я не уверен, когда uncurrying срабатывает из bsb. - person wegry; 16.10.2018
comment
Да, если компилятор знает как реализацию, так и ее использование, он может выполнять такие оптимизации. И на уровне модуля, а не только в функции. - person glennsl; 16.10.2018