javascript - 在 Javascript 中执行(整数)操作的最有效方法是什么？

Question

我正在用 Javascript 实现一个图灵机(把它想象成一个虚拟机)。我正在研究一个尽可能高效地执行计算的例程(从一开始这不是项目的重点)。

是的，除非遇到性能问题，否则我不应该考虑优化。但是我正在做的事情的性质(大多数非平凡程序的渐近运行时效率非常低)意味着总是可以从优化中获得一些好处。我想尽我所能(合理地)每秒获得尽可能多的指令。

例如，如果我用 C++ 编程，解决方案就很清楚了。做一些计时。 gprof . -O3等等。我将研究我希望运行代码的体系结构，并且可能还会查看正在生成的程序集。

但是，不能用 javascript 做到这一点。我的第一直觉是将内部循环中的操作减少到数组查找。在我看来，如果解释器能够将它转换为一系列(希望是简短的)整数运算，我将能够利用 CPU 缓存性能，这是一个很好的选择。

图灵机非常简单。它实际上是存在的最简单的计算公式(!):它具有有限数量的状态，一个双向无限磁带，一个可以向任一方向移动一个单元的磁头，并且可以读取和写入单个字符到磁带。

一个程序被编码在一个转换函数中，该函数接受一个状态和一个读取的字符，并根据该信息提供要写入的字符、移动头部的方向和新状态。

这是每一步的逻辑:

// 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 的索引。通过将索引存储在字母表中而不是将字母表值本身存储在磁带上。

但主要的问题是这个。我还能做些什么来让它更快？有没有可能让它更快？我不知道执行的哪个组件将成为瓶颈(CPU 或 I/O，或其他什么？)，我不知道我将如何找到它。使用 Javascript，我也可以使用哈希表，但似乎数组总是更快。

也许我过早地寻求建议。随着我的进步，我会回来编辑性能数据。

作为阅读我的问题的奖励，我将提供一个链接到我的项目的实时工作中版本:http://stevenlu.net/tm.html

到目前为止，它的操作一直是操纵一个 div充满spans它代表磁带。它还对字符串执行大量操作，并且还进行了大量元素的复制，这在图灵机的实际计算中是完全没有必要的。但即便如此，它也取得了不错的性能。我的机器花了大约一分钟来计算 600,000 步左右(5^4 = 625)，即每秒 10,000 步。这还不错，但我知道我可以通过一些较低级别的编程达到每秒超​​过一百万的目标。

看着 benchmark perf here对于上一代 CPU，我看到每个内核大约 10,000 MIPS。因此，我估计，如果我能在运行 50 次 Dhrystone 迭代所需的时间内运行一次我的内部循环(即使我不知道那些合成基准测试实际上做了什么，这似乎很可能用一个简单的 C 实现)，除非内存带宽限制，我在一个线程上每秒进行 2 亿次迭代。我的 600k 步计算将在 3ms 内完成!!

好吧，如果我可以让我的 5^4 计算在没有浏览器向我报告它挂断的情况下运行，我会很高兴......

更新

随着算法更高效的javascript实现完成，9^4 = 6561的计算需要 58202209 步，计算耗时 6173 毫秒。那是每秒 940 万步。比我原来的 DOM 依赖方法增加了近 1,000 倍。

原5^4计算(即使不滚动磁带也需要大约 30 秒)现在在 84 毫秒内完成。

Answer 1

如果您想同时拥有 +ve 和 -ve 整数索引，为什么不使用普通对象呢？您是否使用任何特殊的数组方法？数组方法大多是通用的，因此可以使用其他 native 对象调用(可能不适用于宿主对象，但我认为这不是问题)。

在 javascript 中，数组只是对象，所以我不明白为什么访问 array[i] 应该比 object[i] 更快或更慢(当然它可能在不同的实现中)。您只需要保留自己的长度属性(可能是正长度和负长度)。

如果您提供一些示例代码，无论性能如何，您都可能会得到一些更具体的建议。