Ste*_* Lu 8 javascript arrays optimization performance
我正在使用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数组的摊销的常量时间操作.更不清楚的是,附加到阵列的前面也会有很好的性能,所以我可能想要使用两个阵列,一个向左延伸,一个向右延伸.
问题是,在naive实现中会在内部循环中插入条件语句.我不喜欢那样.无论如何必须已经有条件检查来检查状态是否处于暂停状态.所以也许它不会那么糟糕.
还有一个潜在的优化可以alph_index通过将索引存储在字母表而不是磁带上的字母值本身来消除索引.
但主要的问题是这个.我还可以采取哪些其他措施来加快速度？有可能让它更快吗？我不知道执行的哪个组件会成为瓶颈(CPU或I/O,还是别的什么？)而且我不知道如何找到它.使用Javascript我也可以使用哈希表,但似乎数组总是更快.
也许我过早地寻求建议.随着我的进步,我会回来编辑性能数字.
作为阅读我的问题的奖励,我将提供一个链接到我的项目的实时工作进展版本:http://stevenlu.net/tm.html
到目前为止,它的操作是操纵一个div填充spans代表磁带.它还对字符串执行大量操作,并且还对元素进行大量复制,这些元素在图灵机的实际计算中是完全不必要的.但即便如此,它也能取得不错的表现.我的机器花了大约一分钟来计算600,000左右的步数(5 ^ 4 = 625),即每秒10,000步.这并不是那么糟糕,但我知道我可以通过一些较低级别的编程实现每秒超过一百万.
在寻找标杆PERF这里对以往根CPU的我看到每个核心约10000 MIPS.因此,我估计如果我可以在运行50 Dhrystone迭代所花费的时间内运行一次我的内循环(即使我不知道这些综合基准实际上做了什么,这似乎很简单的C实现),禁止内存带宽限制,我在一个线程上每秒有2亿次迭代.我的600k步计算将在3ms内完成!!
好吧,如果我可以让我的5 ^ 4计算运行而没有浏览器向我报告它已挂起,我会很高兴...
UPDATE
通过更高效的javascript实现完成的算法,计算9^4 = 6561采取58202209步骤,计算时间为6173毫秒.那是每秒940万步.比我原来的DOM依赖方法增加了近1,000倍.
原始5^4计算(即使不滚动磁带也需要大约30秒)现在在84毫秒内完成.
使用 Javascript，我也可以使用哈希表，但数组似乎总是更快。
您可能认为 JavaScript 中的“数组”查找是这样工作的：
[ 1, 2, 3, 4, 5 ]
|------>x
给定索引 2，您只需计算：
int operator[] (int index) {
return start_of_data + (sizeof(data_item) * index);
}
这样你的查找就会得到O(1)时间。
至少在传统上，在 JavaScript 中并非如此。一般来说，“数组”是带有数字键的哈希映射。因此，每次进行查找时，您实际上都是通过哈希函数运行索引（仅将其视为键）。所以这：
a[1]
更被视为：
a["1"]
在此，您正在运行一些（可能相当不错的）哈希函数来尝试使存储桶分布规则并最大限度地减少冲突。这对我来说听起来很昂贵，但我不知道优化的实现是如何的（因为哈希图查找是摊销常数时间，但它可能仍然不那么高效，并且取决于您获得的碰撞次数以及遇到时您会做什么一）。
幸运的是，一些（如果不是大多数）现代 JavaScript 解释器在跟踪您的代码以查看您是否像稀疏数组或密集数组一样使用它之后，就了解如何使用密集和稀疏集合。仔细检查您期望使用的环境。
我还可以做哪些其他事情来加快速度？有可能让它变得更快吗？
我的一个想法是使用类型化数组来更好地获得恒定时间查找速度。这帮助 Fabrice Bellard 将整个 Linux 内核移植到 JavaScript/浏览器 ( jslinux.org ) 中。
例如，如果我使用 C++ 进行编程，那么解决方案就很清楚了。做一些计时。
如果你打算在浏览器中运行东西（看起来你确实这么做了） ，我建议使用jsperf.com，因为它们有一个非常好的 Java 计时器（比 JavaScript、IIRC 中处理时间的任何东西都更细粒度）或者简单地使用Node .js或Rhino以及其他命令行分析工具（如果您确实需要，可以在此环境中模拟 DOM...）。