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

Question

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

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

Answer 1

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

执行此操作的最佳方法是使用面向对象的测试解决方案并查看它是否足够快。如果没有，那就进行分析，找出哪些分支机构或商店花费最多，看看是否可以避免或简化它们。慢慢地重新构建您的解决方案，直到它满足您所追求的性能目标。在某些情况下，您可能必须采用更具功能性或程序性的风格。

最后，如果您编写了一个由数百个堆栈变量组成的函数并转到，那么您就错了。代码必须始终可读且可维护。

额外思考：您能否再花 5,000 美元购买更好的硬件，以避免 50,000 美元的开发成本优化？

Answer 2

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

Answer 3

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

技术性更强一些：处理器具有 32-64 K 的 L1 缓存和几到几十兆字节 L2-L3。分支缓存最多可达几千字节。

Answer 4

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

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

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

有限状态机非常简单，基本上它们的运行时间只是加载 I/O 缓冲区所需时间的一小部分。他们不应该做任何不必要的内存分配、数据结构构建、任何面向对象的胡言乱语。

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

---

只是为了向您展示我的意思，请考虑十进制整数的正则表达式：

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”。
我希望您能看到代码实际上没有比这更快的了。

如果您真的从 arc-set 开始，您可以生成以下代码：

c = getc();

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

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

END:

这是意大利面条代码，但不比 arc-set 多，而且它将与结构化代码一样快。
（事实上​​，这或多或少就是编译器将结构化代码转换成的内容。）

Answer 5

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

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

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

• 如果您有许多相同的有限机器，请考虑使用面向数据的设计方法来创建它们。这个想法是不是随机地处理机器，而是根据它们当前所处的状态链接