有没有比逐字节遍历更快的解析方法?

x86有一些字符串指令,但它们在现代处理器上不受欢迎,因为它们比执行相同操作的更原始的指令慢。

处理器世界正越来越向RISC(即简单指令集)迈进。

引用 Wikipedia (重点是我的):

第一个高度(或紧密)流水线的x86实现是Intel、AMD、Cyrix和IBM的486设计,它们支持它们的前任所做的每一条指令,但是 仅在一个相当简单的x86子集上实现了最大的效率,该子集与典型的RISC指令集相比仅略为相似。 (即没有典型的RISC负载存储限制)。

在今天的x86处理器上仍然是这样。

你可以得到 轻微地 一次处理四个字节的性能更好, 假设 文本中的每个“标记”都是四字节对齐的。显然,大多数文本都不是这样的…所以最好坚持逐字节扫描。

是的,有一些特殊的CPU指令;以及运行时库,它实现了如下功能 strchr ,可以在程序集中写入。

一种比遍历字节更快的技术是遍历双字,即一次处理32位数据。

在字符串上下文中,遍历大于最小可寻址内存单元块的问题是对齐

在函数的开头和结尾添加代码(循环前后),以处理不均匀/未对齐的字节[s]。(耸肩)它使您的代码更快:不简单。 例如,下面的一些源代码声称是strchr的改进版本。它使用特殊的CPU指令,但并不简单(对于未对齐的字节有额外的代码):

PATCH: Optimize strchr/strrchr with SSE4.2 --“此补丁添加了SSE4.2优化strchr/strrchr。在Intel Core i7上,它可以将strchr/strrchr的速度提高2倍。

虽然(有些)处理器确实有字符串指令,但它们在生成更快的代码方面用处不大。首先,正如@zildjohn01所指出的,它们通常比当前处理器的其他指令慢。更重要的是,不管怎样,它很少有什么不同——如果你扫描了大量的文本,瓶颈通常是从内存到CPU的带宽,所以本质上,你对改变指令的任何操作在任何情况下都可能造成显著的不同。

这就是说,特别是如果你要找的令牌很长,一个更好的算法可能会有用。Boyer-Moore搜索(或变体)可以避免查看某些文本,这可以带来实质性的改进。

嗯,在某种程度上,你必须了解所有关于文本的知识。可以说,您可能有某种结构化的文本,它为您提供了关于在N元空间分区中的每个点上行走的进一步信息。但是,在创建文件时,“解析”已经部分完成了。从0信息开始,您需要触摸每个字节以了解所有信息。

对。由于您的编辑特别要求算法,我想为它添加一个示例。

您将知道要解析的语言,并且可以在构建解析器时使用这些知识。例如,一种语言,其中每个标记必须至少有两个字符,但标记之间可以出现任何长度的空白。现在,当您在空白处扫描下一个令牌时,可以跳过每一个字符。只有当你点击第一个非空白时,你才需要备份一个字符。

例子:

01234567890123456789
FOO        BAR    

扫描下一个令牌时,您将探测4、6、8、10和12。只有当你看到A的时候,你才会回头看11找到B。你从来没有看过3,5,7和9。

这是一个特殊的案例 Boyer–Moore string search algorithm

尽管这个问题早就不存在了,但我还有另一个答案。

最快的分析方法是根本不分析。嗯?!

我的意思是,从统计上讲,大多数源代码文本,以及从该源代码生成的大多数代码和数据,不会在编译过程中发生变化。

因此,您可以使用一种称为增量编译的技术。第一次编译源代码时,您将它分成粗粒度的块,例如,在全局声明和函数体的边界处。您必须保存块的源代码,或其签名或校验和,以及有关边界的信息、它们编译到的内容等。

下一次您必须在相同的环境下重新编译同一个源代码时,您可以快速浏览源代码以查找更改。一种简单的方法是将当前代码与上次保存的代码的持久快照进行比较(每次比较longword)。只要longwords匹配,就跳过源代码;而不是解析和编译,而是重新使用上次为该部分创建的快照编译结果。

如“C”88、QuickC 2.0和VC++4.0增量重新编译中所示。

快乐黑客!

有没有比遍历文本的每个字节更快的方法来解析文本?

是的,有时您可以跳过数据。这个 Boyer-Moore string search algorithm 基于这个想法。

当然,如果解析操作的结果以某种方式需要包含文本中的所有信息,那么就无法绕过必须读取所有内容的事实。如果您想避免CPU负载,可以构建 hardware which processes data 具有 direct memory access 我猜。