在实现大多数算法(排序,搜索,图遍历等)时,经常需要权衡以减少存储器访问为代价的额外普通操作. Knuth有一种有用的方法,可以通过从特定处理器中抽象出来来比较各种算法实现的复杂性
Knuth有一种有用的方法,可以通过从特定处理器中抽象出来来比较各种算法实现的复杂性,并且只区分普通操作(oops)和内存操作(mems).
在编译的程序中,通常允许编译器组织低级操作,并希望操作系统将处理数据是保存在高速缓存(更快)还是保存在虚拟存储器(更慢)中的问题.此外,指令的确切数量/成本由编译器封装.
使用Forth,不再有这样的封装,而且更接近机器,尽管可能是在寄存器处理器上运行的堆栈机器.
忽略操作系统的影响(因此没有内存停滞等),并且暂时假设一个简单的处理器,
(1)任何人都可以建议如何将Forth中的普通堆栈操作(例如dup,rot,over,swap等)与Forth的内存访问获取(@)或store(！)的成本进行比较？
(2)是否有一个经验法则我可以用来决定在保存内存访问权限的情况下需要权衡多少普通操作？
我正在寻找的是“内存访问成本高达50普通操作,或500普通操作,或5普通操作’Ballpark绝对没问题.
我试图了解获取和存储与腐败,交换,复制,丢弃,过度,正确到一个数量级的相对费用.
这篇文章 How much time does it take to fetch one word from memory?讨论了主内存停滞时间,带有一些经验法则类型的数字,但基本上你可以在停止主内存时做很多指令.正如其他人所说,系统之间的数字差异很大.主存储器停顿是一个很大的兴趣领域,特别是当CPU具有更多内核时,但通常没有更快的内存带宽.关于压缩主存储器中的数据也有一些研究,因此CPU可以利用“备用”周期和紧密压缩的缓存行http://oai.cwi.nl/oai/asset/15564/15564B.pdf
对于那些真正对细节感兴趣的人,大多数CPU制造商都会发布关于内存优化的深度指南等,主要针对高端和编译器编写者,但所有2gl和3gl程序员都可以读取.
PS.去吧.