c++ - 有限状态机的速度 - OO 与过程

Question

大家好，
我正在设计一个程序，它将从输入中接受一系列令牌并将它们提供给我设计的有限状态机。我设计了一个面向对象风格的测试有限状态机，具有机器本身的结构和转换等，但我正在编写的应用程序是速度非常重要的应用程序。

到目前为止，使用机器、添加新状态等已被证明很容易而且不是很复杂。理解起来很容易，离开一个月，回到代码中不会很迷失方向。但是，我不确定当前 OO 方法的速度折衷是什么。对象的分配、数据的存储等是否会大大降低使用一堆标签和goto语句的速度？

score 3 · Accepted Answer

与其从 OO 的角度考虑它，不如从功能或过程编程的角度考虑它，而不是从操作的角度考虑它。调用函数、分支、获取、存储等...都需要一些时间，并且要了解每个解决方案的性能，您需要计算出您需要执行的每个解决方案的多少。

最好的方法是使用您的 OO 测试解决方案，看看它是否足够快。如果没有，那么对其进行分析，找出哪些分店或商店花费你最多，看看你是否可以避免或简化它们。慢慢地重新构建您的解决方案，直到它满足您所追求的性能目标。在某些情况下，您可能不得不采用更具功能性或程序性的风格。

最后，如果你编写了一个包含数百个堆栈变量的函数并转到你做错了。代码必须始终是可读和可维护的。

额外的想法：您是否可以再花 5,000 美元购买更好的硬件来避免 50,000 美元的开发成本优化？

score 3 · Accepted Answer

我更喜欢结构良好、组织良好、可维护、易于理解（即使离开一个月，这也是相当好的质量）的代码，而不是“一堆标签和goto语句”。话虽如此，在进行速度分析时，我还会对代码运行分析器以检测瓶颈。

score 3 · Accepted Answer

简而言之，处理器在表查找时进行表查找比分支更快。只要表易于处理且足够小以适合缓存，您所描述的 OO 样式就会更快。（不过，我肯定不会说这两种范式都与这两种实现相关联。）

稍微更技术一点：处理器有 32-64 K 的 L1 缓存和几到几十兆字节的 L2-L3。分支缓存最多为几千字节。

score 1 · Accepted Answer

状态机多久更改一次？如果它在一段时间内保持不变，我所做的就是将它翻译成我喜欢的任何语言的硬编码例程。

状态机的转移图从何而来？它来自正则表达式吗？您知道您可以直接将其转换为结构化代码，而无需先构建弧集。事实上，从一开始就编写该代码可能更容易。

然后我要么只制作应用程序的那一部分，要么动态编译并将其链接到 dll 中并动态加载它。后者只需几秒钟。

有限状态机非常简单，它们基本上应该在加载 I/O 缓冲区所需时间的一小部分内运行。他们不应该做任何不必要的内存分配，数据结构构建，任何OO hoo-haw。

请记住，表示为一组状态和弧元组的有限状态机是一个理论模型。它的存在，就像图灵机一样，是为了证明关于它的定理。就像图灵机一样，它不一定是一种好的代码实现技术。

只是为了告诉你我的意思，考虑一个十进制整数的正则表达式：

dd*

其中“d”表示数字。作为有限状态机（元组），它将是：

A d -> B
B d -> B

作为代码，它将是：

char c = getc();
if (DIGIT(c)){
  c = getc();
  while(DIGIT(c)){
    c = getc();
  }
}

看到这段代码与正则表达式的相似性了吗？不要认为c = getc()是“获得下一个字符 c”。将其视为“接受当前字符 c”。我希望你能看到代码真的不能比这快得多。

如果你真的从弧集开始，你可以生成这个：

c = getc();

A:
if (DIGIT(c)){c = getc(); goto B;}
goto END;

B:
if (DIGIT(c)){c = getc(); goto B;}
goto END;

END:

这是意大利面条代码，但不超过弧集，它将与结构化代码一样快。（事实上，这或多或少是编译器将您的结构化代码转换成的内容。）

score 0 · Accepted Answer

我是一名应用程序性能工程师，以下是我对有限状态机性能的看法。请注意，这些是意见，而不是我衡量的事实，但我认为这对某些人有用：

FSM 对硬件来说通常是困难的。硬件总是在执行以前从未执行过的代码（因为从一种状态转移到另一种状态需要不同的功能）。
大开关原则上会比 OOP 方法更快，因为整个开关都在一个函数内，所以至少有一些空间局部性。如果您使用枚举来保存当前状态，请确保 FSM 中的相邻状态是枚举中的相邻编号，因为这会增加处理状态的函数在指令缓存中的可能性。
在 OOP 的情况下，将来自不同类的所有状态更改函数放入同一个链接器部分（例如 __attribute ((section (".state-machine"))) 状态更改函数的属性） - 如果程序很小，则不重要，重要如果程序很大

这些是一般性建议。现在，根据您的具体情况，您还有一些建议：

5 回答 5