在哪里可以找到用于编写每个 PHP "built-in" 函数的算法？

Question

我最近构建了一个基于 PHP 的应用程序，该应用程序通常需要数 (>10) 秒来解析目标字符串（>10 秒，因为通常对 100kB+ 的字符串进行数千次检查）。我正在寻找减少执行时间的方法。

我开始好奇PHP的每个"built-in"函数是怎么写的。例如，如果您转到手册中的 strpos() 参考资料 (this link)，其中有很多信息但没有算法。

谁知道，也许我可以为我的特定应用程序编写一个比内置函数更快的函数？但是我无法知道例如算法。 strpos()。算法是否使用了这样的方法：

function strposHypothetical($haystack, $needle) {

    $haystackLength = strlen($haystack);
    $needleLength   = strlen($needle);//for this question let's assume > 0

    $pos = false;

    for($i = 0; $i < $haystackLength; $i++) {
        for($j = 0; $j < $needleLength; $j++) {
            $thisSum = $i + $j;
            if (($thisSum > $haystackLength) || ($needle[$j] !== $haystack[$thisSum])) break;          
        }
        if ($j === $needleLength) {
            $pos = $i;
            break;
        }
    }
    return $pos;
}

或者它会使用更慢的方法，让我们说组合 substr_count() 来处理针的出现，如果出现 > 0，那么使用 for 循环，或其他一些方法？

我已经分析了我的应用程序中的函数和方法，并以这种方式取得了重大进展。另外，请注意 this post 并没有多大帮助。我在哪里可以找到 PHP 中每个内置函数所使用的算法，或者此信息是否专有？

Answer 1

内置的PHP函数可以在/ext/standard/ in the PHP source code中找到。

在strpos的情况下，您可以在/ext/standard/string.c. At its core, this function actually uses php_memnstr, which is actually an alias of zend_memnstr中找到PHP的实现：

found = (char*)php_memnstr(ZSTR_VAL(haystack) + offset,
                           Z_STRVAL_P(needle),
                           Z_STRLEN_P(needle),
                           ZSTR_VAL(haystack) + ZSTR_LEN(haystack));

如果我们阅读 zend_memnstr 的源代码，我们可以找到用于实现 strpos:

的算法本身

while (p <= end) {
    if ((p = (const char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
        if (!memcmp(needle, p, needle_len-1)) {
            return p;
        }
    }

    if (p == NULL) {
        return NULL;
    }
    p++;
}

这里的

ne表示needle的最后一个字符，p是一个指针，递增遍历haystack.

函数 memchr 是一个 C 函数，它应该对字节序列进行简单的线性搜索，以找到给定字节/字符在字节串中的第一次出现。 memcmp 是一个 C 函数，它通过逐字节比较可以在字符串中比较两个字节/字符范围。

该函数的伪代码版本如下：

while (p <= end) {
    find the next occurrence of the first character of needle;
    if (occurrence is found) {
        set `p` to point to this new location in the string;
        if ((character at `p` + `length of needle`) == last character of needle) {
            if ((next `length of needle` characters after `p`) == needle) {
                return p; // Found position `p` of needle in haystack!
            }
        }
    } else {
        return NULL; // Needle does not exist in haystack.
    }
    p++;
}

这是一个相当有效的算法，用于查找字符串中子字符串的索引。它与您的 strposHypothetical 几乎是相同的算法，并且在复杂性方面应该同样有效，除非 memcpy 在看到字符串相差一个时不会尽早 return字符，当然，在 C 中实现，它会更精简和更快。

在哪里可以找到用于编写每个 PHP "built-in" 函数的算法？

Where can I find the algorithm used to write each PHP "built-in" function?

php

built-in