class
来定义对象。在Windows Turbo Pascal中,我们使用object
,今天你仍然可以使用object
来创建对象。区别在于object
存在于堆栈上,而class
存在于堆上。当然,object
已经过时了。抛开这些不谈:使用
object
是否有速度上的优势?我知道在Delphi 2009中
object
已经失效了,但我有一个特殊的用例(1),在这个用例中速度很重要,我正在尝试找出是否使用object
会使我的代码更快,但不会出现错误。这个代码库是在Delphi 7中的,但我可能会将其移植到Delphi 2007,还没有决定。
1)康威生命游戏
长注释
感谢大家指引我正确的方向。
让我再解释一下。我正在尝试更快地实现hashlife,请参见此处或这里查看简单源代码
目前的记录保持者是golly,但golly使用了Bill Gospher原始Lisp代码的直接翻译(作为算法非常出色,但在微观层面上没有进行优化)。Hashlife可以在O(log(n))时间内计算一代。
它通过使用空间/时间权衡来实现。因此,hashlife需要大量的内存,数十亿字节并不罕见。作为回报,您可以使用o(1)时间计算第2^127(170141183460469231731687303715880000000)代,从而计算第2^128(340282366920938463463374607431770000000)代。
由于hashlife需要为出现在较大模式中的所有子模式计算哈希值,因此对象的分配需要快速进行。
这就是我选择的解决方案:
分配优化
我会分配一个大块的物理内存(用户可设置),比如说512MB。在这个块中,我会分配我所谓的cheese stacks。这是一个普通的栈,在其中进行push和pop操作,但是pop也可以从栈的中间进行。如果发生这种情况,我会将其标记为free
列表(这是一个普通的栈)。当进行push操作时,我首先检查free
列表是否有空闲,如果没有空闲,我就按照正常方式进行push操作。我会使用记录来实现,因为这看起来是开销最小的解决方案。
由于hashlife的工作方式,很少进行pop
操作,而进行了大量的push
操作。我为不同大小的结构保留了单独的栈,确保内存访问对齐在4/8/16字节边界上。
其他优化
- 递归消除
- 缓存优化
- 使用
inline
- 预计算哈希值(类似于彩虹表)
- 检测病态情况并使用备用算法
- 使用GPU