为什么mb_strpos()比strpos()慢得多？

Question

我曾批评过一个答案，该答案建议在查找子字符串偏移量时使用preg_match而不是===，以避免类型不匹配。

然而，后来答案的作者发现preg_match实际上比多字节操作mb_strpos要快很多。正常的strpos比这两个函数都要快，但当然无法处理多字节字符串。

我明白mb_strpos需要比strpos做更多的事情。但是，如果正则表达式可以几乎与strpos一样快地完成它，那么是什么导致mb_strpos花费了这么多时间呢？

我强烈怀疑这是一种优化错误。例如，PHP扩展是否比其本机函数更慢？

mb_strpos($str, "颜色", 0 ,"GBK"): 15.988190889 (89%)
preg_match("/颜色/", $str): 1.022506952 (6%)
strpos($str, "dh"): 0.934401989 (5%)

函数被运行了10⁶次。绝对时间(s)是指一个函数运行10⁶次的总时间，而不是平均时间。

测试字符串为$str = "代码dhgd颜色代码";。可以在此处查看测试结果(向下滚动以跳过测试类)。

注意：根据其中一位评论者(和常识)，preg_match在比较时也不使用多字节，因此存在与strpos相同的错误风险。

- Tomáš Zato

---

您的正则表达式没有使用Unicode /u标志，因此很可能只进行了二进制比较。 - mario

我不太明白这个。如果愚蠢的 preg_match（没有 u 修饰符）可以工作，那么普通的 strpos 一定 也可以工作（而且显然会更快）。请澄清一下。 - Jon

@Jon - strops()可以找到多字节序列，但它也可能针对多字节序列返回误报，因为它无法识别多字节字符的字符边界，它仅适用于字节序列。 - Mark Baker

请注意，preg_match的性能将取决于底层pcre的版本。 - Mark Baker

mb_strpos 唯一能做到的一件事是告诉你子字符串的 字符 偏移量，而不管输入编码是什么。 - Jon

Answer 1

To understand why these functions have different runtimes, you need to understand what they actually do. Simply stating that "they search for needle in haystack" is not sufficient.

strpos

If you examine the implementation of strpos, you will see that it internally uses zend_memstr, which employs a fairly naive algorithm for searching for needle in haystack: Essentially, it uses memchr to locate the first byte of needle in haystack, and then uses memcmp to verify whether the entire needle begins at that position. If not, it repeats the search for the first byte of needle starting from the position of the previous match of the first byte.

了解这一点后，我们可以说strpos仅在字节序列中搜索字节序列，使用朴素的搜索算法。

mb_strpos

该函数是strpos的多字节版本。这使得搜索变得更加复杂，因为您不能只查看字节而不知道它们属于哪个字符。

mb_strpos使用mbfl_strpos，与zend_memstr的简单算法相比，mbfl_strpos执行更多操作，包含大约200行复杂代码，而zend_memstr只有30行精简代码。

We can skip the 部分，其中如果需要，可以将needle和haystack都转换为UTF-8编码, 直接进入主要的代码块。

首先有两个设置循环，然后是根据给定的offset进行指针操作的循环，在这里可以看到他们了解实际字符以及如何跳过整个编码的UTF-8字符：因为UTF-8是一种可变长度的字符编码，每个编码字符的第一个字节表示整个编码字符的长度。这些信息存储在u8_tbl数组中。

最后，循环实际搜索发生的地方。这里有一些有趣的东西，因为在 haystack 中的某个位置尝试 needle 的测试是反向进行的。如果一个字节不匹配，则使用跳转表jtbl找到 haystack 中 needle 下一个可能的位置。这实际上是Boyer-Moore字符串搜索算法的实现。

所以现在我们知道mb_strpos...

• 必要时将字符串转换为UTF-8
• 知道实际字符
• 使用Boyer-Moore搜索算法

preg_match

关于 preg_match，它使用 PCRE库。它的标准匹配算法使用非确定有限自动机 (NFA) 来查找匹配项，并对模式树进行深度优先搜索。这基本上是一种朴素的搜索方法。

- Gumbo

---

非常好的写作。我想知道的一件事（并没有在我的简单答案中提到）是，当进行Unicode搜索时，mb是否也进行Unicode规范化。但我想象那对于该库来说可能太多了，所以我跳过了它。关于搜索算法，这是否意味着在更大的“干草堆”下，相对时间会向mb_strpos转移？ - hakre

@hakre：我记得BM算法在使用较长的针时效果更好，相对于干草堆而言，针中包含的字符数量较少。如果干草堆中包含大量不出现在针中的字符，则效果更佳。然后BM可以跳跃式地运行，比朴素的字节比较快得多。 - LSerni

非常好的解释...我很高兴不是我在编写这些函数！:) +1 - zx81

Answer 2

为了使分析更加突出，我省略了preg_match。

根据你的观察，mb_strpos相对于strpos而言速度较慢，这导致你假设——由于耗费时间——mb_strpos执行的操作比strpos多。

我认为这种观察是正确的。

然后你问，是什么“更多”的东西导致了时间差异。

我试图给出一个简单的答案：那个“更多”是因为strpos操作的是二进制字符串（一个字符=8位=1八位组=1字节）。mb_strpos操作的是编码字符序列（几乎所有mb_*函数都如此），每个字符可以是X位，甚至长度每个字符不同。

由于这总是涉及特定的字符编码，因此无论是haystack还是needle字符串（可能）都需要首先验证该编码，然后在该特定字符编码下执行查找字符串位置的整个操作。

这是翻译工作，并且——根据编码——还需要特定的搜索算法。

除此之外，mb扩展还需要一些内存结构来组织不同的字符编码，无论是翻译表还是特定算法。例如，您注入的额外参数——编码名称。

这远比仅进行简单的逐字节比较要麻烦得多。

例如，当你需要编码或解码某个字符时，GBK字符编码非常有趣。在这种情况下，mb字符串函数需要考虑所有这些细节以确定字符是否存在以及其位置。由于PHP只在用户空间中拥有二进制字符串用于调用该函数，因此整个操作需要在每个单独的函数调用上完成。

为了更加明确，如果你查看支持的编码列表 (mb_list_encodings)，你还可以找到一些类似于BASE64，UUENCODE，HTML-ENTITIES和Quoted-Printable的编码。正如你所想象的那样，所有这些编码都是以不同的方式处理的。

例如，单个数值型HTML实体可能高达1024字节甚至更大。我知道并喜欢一个极端的例子是这个。然而，对于该编码，必须使用mb_strpos算法进行处理。

- hakre

---

好的，它确实“做得更多”，我们知道这一点。但为什么PCRE在表面上看起来完成相同任务时速度明显更快呢？ - deceze

@deceze：PHP中的PCRE仅支持两种编码：strpos的编码（速度较慢）和UTF-8。对于UTF-8，存在许多优化代码。这远远超出了mb扩展提供的编码范围，链接的手册页面列出了60种不同的编码。 - hakre

@deceze：即使它们都使用UTF-8编码，它们也不是在做同样的事情：mb_strpos返回数字字符位置，preg_match返回字节偏移量（如果启用了偏移量返回）。这也表明，在内部，mb_strpos必须以不同的方式处理事情，例如管理字符位置和字节偏移量。我觉得很难想象这些事情可能需要一些时间 - 而且库的质量可能不像广泛使用的pcre那样精确。 - hakre

@AmalMurali：感谢您的修改和评论 :) - hakre

Answer 3

缓慢的原因

查看 PHP 5.5.6 源文件后，我们发现延迟主要出现在 mbfilter.c 中，正如hakre所猜测的那样 - 每次调用mb_strpos（或者我猜大部分的mb_*函数），都需要验证和转换both haystack 和 needle：

除非haystack是默认格式，否则将其编码为默认格式：

if (haystack->no_encoding != mbfl_no_encoding_utf8) {
        mbfl_string_init(&_haystack_u8);
        haystack_u8 = mbfl_convert_encoding(haystack, &_haystack_u8, mbfl_no_encoding_utf8);
        if (haystack_u8 == NULL) {
                result = -4;
                goto out;
        }
} else {
        haystack_u8 = haystack;
}

除非针是默认格式，否则将其编码为默认格式:

if (needle->no_encoding != mbfl_no_encoding_utf8) {
        mbfl_string_init(&_needle_u8);
        needle_u8 = mbfl_convert_encoding(needle, &_needle_u8, mbfl_no_encoding_utf8);
        if (needle_u8 == NULL) {
                result = -4;
                goto out;
        }
} else {
        needle_u8 = needle;
}

根据使用 valgrind 的快速检查，编码转换占了 mb_strpos 运行时间的很大一部分，约为总运行时间的84%，或五分之六：

218,552,085  ext/mbstring/libmbfl/mbfl/mbfilter.c:mbfl_strpos [/usr/src/php-5.5.6/sapi/cli/php]
183,812,085  ext/mbstring/libmbfl/mbfl/mbfilter.c:mbfl_convert_encoding [/usr/src/php-5.5.6/sapi/cli/php]

这似乎与OP的mb_strpos与strpos的时间相一致。

没有考虑编码，mb_strpos字符串与strpos字符串是完全相同的，仅在字符串略长时会有所不同。如果您遇到非常麻烦的字符串，那么最多会长四倍，但即使如此，您也只会因为编码时间而延迟四倍，而不是二十倍。额外的5-6倍减速来源于编码时间。

加速 mb_strpos...

那么你该怎么办呢？您可以通过确保在mbfl*进行转换和比较的“基本”格式中内部已经有了字符串来跳过这两个步骤，该格式为mbfl_no_encoding_utf8（UTF-8）：

• 将数据保留在UTF-8格式中。
• 尽快将用户输入转换为UTF-8格式。
• 如有必要，则将其转换回客户端编码。

然后您的伪代码：

$haystack = "...";
$needle   = "...";

$res = mb_strpos($haystack, $needle, 0, $Encoding);

变成：

$haystack = "...";
$needle   = "...";

mb_internal_encoding('UTF-8') or die("Cannot set encoding");
$haystack   = mb_convert_encoding($haystack, 'UTF-8' [, $SourceEncoding]);
$needle     = mb_convert_encoding($needle, 'UTF-8', [, $SourceEncoding]);

$res = mb_strpos($haystack, $needle, 0);

...当它值得

当整个UTF-8基础的“设置时间”和维护明显小于在每个mb_*函数中隐式地进行转换的“运行时间”时，这当然是方便的。

- LSerni

Answer 4

mb_ 性能问题可能是由于混乱的 php-mbstring 包安装（在 Linux 上）引起的。为确切的 php 安装版本显式安装它可以帮助解决问题。

sudo apt-get install php7.1-mbstring

...

Before: Time: 16.17 seconds, Memory: 36.00MB OK (3093 tests, 40272 assertions)
After:  Time:  1.81 seconds, Memory: 36.00MB OK (3093 tests, 40272 assertions)

- Klesun