algorithm - 算法复杂度计算估计的基本操作的性能特征

Question

我为通用编程语言制作了一个编译器。作为工具链的一部分，我想包括一个分析器，它能够估计给定表达式的时间复杂度。计算算法复杂性似乎相当简单——也就是说，假设所有恒定时间操作花费相同的时间——但我希望能够近似真实 复杂性也是如此。为此，我需要有关单个处理器操作的相对性能的信息，例如 inc、add、mul 等，以及某些更高级别的操作，例如 I/O。

我意识到这既依赖于体系结构又依赖于实现，最多只能产生模糊的结果，和是一个双重问题。但是有没有人碰巧知道任何可以帮助我入门的高质量资源？查看更高级别操作的开源实现是否会为我提供足够的信息来合理估计它们的复杂性？

Answer 1

在大多数现代 CPU 上，“特定指令的周期时间”的概念并不是特别有用。流水线将同时处理多条指令，它们将竞争 CPU 内部的各种资源——因此只能在周围指令的上下文中理解给定指令的性能。即使在处理器系列的不同型号中，细节也会有很大差异。

此外，如果您正在做任何涉及数据的事情，那么缓存行为可能与指令执行时间一样重要。

对于 x86:查看 Agner Fog's "Software optimization resources" .