算法复杂度计算估计的基本运算性能特征

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

我意识到这既依赖于体系结构又依赖于实现,最多只能产生模糊结果,并且是一个双重问题.但有没有人碰巧知道有什么高质量的资源可以让我入手？看一下高级操作的开源实现会给我足够的信息来提供他们复杂性的公平估计吗？

在大多数现代CPU中,“特定指令的循环时间”概念并不是特别有用.管道将同时处理多个指令,并且它们将竞争CPU内部的各种资源 – 因此只能在周围指令的上下文中理解给定指令的性能.即使是处理器系列中的不同型号,细节也会有很大差异.

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

对于x86：看看Agner Fog’s “Software optimization resources”.