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

Question

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

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

Решение очевидно, если бы я программировал, например, на C ++.Сделайте немного времени.gprof.-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 заполнено spans, которое представляет ленту.Он также выполняет множество операций со строками, а также выполняет множество копий вокруг элементов, что совершенно не нужно, когда речь идет о реальных вычислениях машины Тьюринга.Но даже при этом он достигает достойной производительности.На моей машине потребовалось около минуты, чтобы вычислить около 600 000 шагов (5 ^ 4 = 625), что составляет 10000 шагов в секунду.Что не так уж и плохо, но я знаю, что, возможно, я смогу достичь более миллиона в секунду при программировании на более низком уровне.

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

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

UPDATE

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

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

Answer 1

С Javascript у меня тоже есть хеш-таблицы, но кажется, что массивы всегда будут быстрее.

Вы, наверное, думаете, что поиск "Array" в JavaScript работает следующим образом:

[ 1, 2, 3, 4, 5 ]
|------>x

С учетом индекса 2 вы просто вычислите:

int operator[] (int index) {
  return start_of_data + (sizeof(data_item) * index);
}

Так что ваш поиск просто получит O(1) время.

Нетак, по крайней мере, традиционно, в JavaScript.Как правило, «Array» - это хеш-карты с цифровыми клавишами.Таким образом, каждый раз, когда вы выполняете поиск, вы фактически запускаете свой индекс (который рассматривается как ключ) через хеш-функцию.Итак, это:

a[1]

Более воспринимается как:

a["1"]

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

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

Что еще я мог бы сделать, чтобы сделать это быстрее?Можно ли вообще сделать это быстрее?

Одна идея, которая у меня возникла, состояла в том, чтобы использовать типизированные массивы , чтобы иметь больше шансов получить постоянную скорость поиска по времени.Это помогло Фабрису Беллару перенести все ядро ​​Linux в JavaScript / браузер ( jslinux.org ).

Решение очевидно, если я программирую, например, на C ++.Сделайте некоторое время.

Я рекомендую использовать jsperf.com , если вы планируете запускать вещи в браузере (что, похоже, у вас), поскольку у них довольно хороший таймер Java(более детально, чем то, что связано со временем в JavaScript, IIRC) или просто используйте node.js или Rhino и другие инструменты профилирования командной строки (вы можете эмулировать DOM в этомсреда, если вам действительно нужно ...).

Answer 2

Если вы хотите иметь целые индексы + ve и -ve, почему бы не использовать простой объект?Вы используете какие-либо специальные методы массива?Методы массива в основном являются общими, поэтому их можно вызывать с использованием других собственных объектов (может не работать с хост-объектами, но я думаю, что это не проблема).

В javascript массивы - это просто объекты, поэтому я не вижупочему доступ к массиву [i] должен быть быстрее или медленнее, чем для объекта [i] (хотя, конечно, он может быть в разных реализациях).Вам просто нужно сохранить собственное свойство длины (возможно, положительное и отрицательное).

Если вы предоставите пример кода, независимо от производительности, вы можете получить более конкретный совет.