Кэширование данных увеличивает скорость даже в неожиданных случаях

[Harkonnen]

Судя по докам и гуглам, JavaScript все числа хранит как double. Чистых int'ов он не умеет. Может быть с этим связано.

[tyomitch]

Я уверен, что дело именно в этом: wholeMod переводит аргумент, взятый из Uint8Array, в double, и производит все вычисления над double.

[MaZaNaX]

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

Объясните пожалуйста это утверждение. Откуда тогда чтение быстрее, чем из оперативной памяти?

[alexxxst]

Из регистров процессора.

[poxvuibr]

Плюс ещё между памятью и регистрами несколько уровней кеша, чтение из которого тоже сильно быстрее, чем из RAM

[propell-ant]

Регистры процессора и статья про javascript…
Как всё это совместилось в голове автора — вот загадка.

[Aquahawk]

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

[Aquahawk]

Очень часто, что-то мелкое проще заново посчитать чем в память ходить. Ну и кеши многоуровневы.

[MaZaNaX]

Понял, спасибо. Подумал, что в принципе сохранение результатов вычислений (даже сложных) в памяти считается моветоном.

[xadd]

for(let i = 0; i < matrixSize; i++)
for(let j = i + 1; j < matrixSize; j++)
let otherRowFirst = matrix[j][i];


Выглядит как, что на каждое чтение пары байт в цикле происходит постоянное считавание 64-байтовых строк из памяти в кэш процессора.

[tzlom]

Вы же понимаете что Uint8Array оптимизирует только память? При каждом доступе JS проверяет выход за границы.
Если хотите реальной производительности (а ещё не писать всю эту математику) — берите lapack и компилируйте его в WebAssembly, любой другой путь — ССЗБ.

[gchebanov]

O(n^3) раз брать по модулю не нужно, промежуточные вычисления вполне помещаются в разумные типы, если модуль маленький. Даже если он большой (порядка 10^9), можно брать Uint64 и делать каждые 16 итераций одно сравнение с вычитанием (завести константу 16*Mod*Mod).

[alexejisma]

Операция деления это далеко не 2 такта. На современных компьютерах деление порядка 50 тактов, а вот суммирование, умножение — один.
Кроме того, первоначальный вариант функции wholeMod можно ускорить. if дешевле, чем % (эта операция, как известно, основана на делении), то есть лучше сделать взятие остатка и потом return res if res >=0 else res + domain

[tyomitch]

Легко проверить, что предложенное вами изменение wholeMod на скорость не влияет.

[amarao]

Никакие CPU-friendly оптимизации не исправят асимпоты алгоритмической сложности. То, что тут написано — это одна из методик динамического программирования, которая меняет асимптоту.

Далее: js, насколько я знаю, работает с f64, а деление в f64 довольно дорогое (особенно, если не на 2).

Третье: ковейеризация очень важна. Если есть зависимость между данных, то конвейер сбрасывается, и тогда деление (f64) делается за 20+ тактов. Это много и дорого.