Каков наиболее эффективный способ выполнения (целочисленных) операций в Javascript?

Я реализую машину Тьюринга (думайте о ней как о виртуальной машине) в Javascript. I ' m работает над процедурой, которая должна выполнять вычисления с максимальной эффективностью (это не было целью проекта с самого начала).

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

Решение очевидно, если я, например, программировал на C ++. Уделите время. гпроф . -O3 и т. Д. Я бы изучал архитектуры, на которых я ожидаю, что код будет запущен, и, вероятно, также заглянул бы в создаваемую сборку.

А вот с javascript этого сделать нельзя. Моим первым побуждением было свести операции во внутреннем цикле к поиску в массиве. Мне кажется, что это хорошая ставка на то, что я смогу воспользоваться производительностью кеш-памяти ЦП, если интерпретатор сможет преобразовать ее в (надеюсь, короткую) серию целочисленных операций.

Машина Тьюринга очень проста. Фактически, это самая простая формулировка вычислений, которая существует (!): Она имеет конечное число состояний, двунаправленную бесконечную ленту, головку ленты, которая может перемещать одну единицу в любом направлении и может читать и записывать один символ в кассета.

Программа кодируется функцией перехода, которая принимает состояние и считываемый символ, и с помощью этой информации предоставляет символ для записи, направление перемещения головки и новое состояние.

Это логика каждого шага:

// states is an array of arrays of triplets and is the transition func
var trans = states[state][alph_index[tape[pos]]]; 
tape[cur_tape_pos] = trans[0]; // write
cur_tape_pos += trans[1]; // move
state = trans[2]; // state update

Процесс происходит в цикле. Мне кажется очевидным, что лента будет массивом. Я предполагаю, что сохранение (добавление) значений в конец массива - это, по крайней мере, амортизированная операция с постоянным временем с массивами Javascript. Гораздо менее ясно, что добавление в начало массива также будет иметь отличную производительность, поэтому я, вероятно, захочу использовать два массива, один расширяющийся влево, а другой - вправо.

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

Существует также еще одна потенциальная оптимизация, которая может исключить индексацию в alph_index путем сохранения на ленте индекса в алфавите, а не самого значения алфавита.

Но главная проблема вот в чем. Что еще я мог бы сделать, чтобы сделать это быстрее? Можно ли вообще сделать это быстрее? Я не знаю, какой компонент выполнения будет узким местом (ЦП, ввод-вывод или что-то еще?), И я не знаю, как я могу это выяснить. С Javascript у меня тоже есть хеш-таблицы, но похоже, что массивы всегда будут быстрее.

Возможно, я преждевременно обращаюсь за советом. Я вернусь и буду редактировать цифры производительности по мере продвижения.

В награду за прочтение моего вопроса я предоставлю ссылку на текущую версию моего проекта, находящуюся в разработке: http://stevenlu.net/tm.html

Его работа пока что было управлять div , заполненным промежутками , который представляет собой ленту. Он также выполняет множество операций со строками, а также выполняет много копий элементов, что совершенно не нужно, когда речь идет о фактических вычислениях машины Тьюринга. Но даже в этом случае он обеспечивает достойную производительность. На моем компьютере потребовалось около минуты, чтобы вычислить 600 000 или около того шагов (5 ^ 4 = 625), что составляет 10 000 шагов в секунду.Это не так уж и плохо, но я знаю, что, вероятно, смогу достичь более миллиона в секунду с помощью более низкого уровня программирования.

Глядя на эталонную производительность здесь для ЦП предыдущего поколения, я вижу около 10 000 MIPS на ядро.Поэтому я предполагаю, что если я смогу запустить свой внутренний цикл один раз за время, необходимое для выполнения 50 итераций Dhrystone (что кажется очень возможным с простой реализацией C, хотя я понятия не имею, что на самом деле делают эти синтетические тесты), за исключением пропускной способности памяти ограничения, у меня 200 миллионов итераций в секунду в одном потоке. Мой расчет шага 600 000 будет завершен за 3 мс !!

Что ж, если я смогу запустить вычисление 5 ^ 4 без того, чтобы браузер сообщал мне, что он завис, я буду очень счастлив ...

ОБНОВЛЕНИЕ

С более эффективной реализацией javascript для алгоритм завершился, вычисление 9 ^ 4 = 6561 , принявшее 58202209 шагов, заняло 6173 мсек. Это 9,4 миллиона шагов в секунду. Почти в 1000 раз больше по сравнению с моим исходным DOM-зависимым методом.

Исходное вычисление 5 ^ 4 (которое заняло около 30 секунд даже без прокрутки ленты) теперь завершается за 84 мс.