错过了 string_view::find_first_of 的优化

Question

更新：相关 GCC 错误报告：https://gcc.gnu.org/bugzilla/show_bug.cgi ?id=103798

我测试了以下代码：

#include <string_view>

size_t findFirstE_slow(std::string_view sv) {
  return sv.find_first_of("eE");
}

size_t findFirstE_fast(std::string_view sv) {
  auto it{sv.begin()};
  for (; it != sv.end() && *it != 'e' && *it != 'E'; ++it)
    ;
  return it == sv.end() ? std::string_view::npos : size_t(it - sv.begin());
}

快速台测试：https://quick-bench.com/q/dSU3EBzI8MtGOFn_WLpK3ErT3ok

编译器资源管理器输出：https://godbolt.org/z/eW3sx61vz

和函数findFirstE_slow()都firstFirstE_fast()旨在执行相同的操作，但findFirstE_slow()运行速度明显较慢（在快速平台测试中至少慢 5 倍）。

这是 的汇编输出x86-64 gcc (trunk) -std=c++20 -O3。

findFirstE_slow()：

.LC0:
        .string "eE"
findFirstE_slow(std::basic_string_view<char, std::char_traits<char> >):
        push    r12
        push    rbp
        push    rbx
        test    rdi, rdi
        je      .L4
        mov     rbx, rdi
        mov     rbp, rsi
        xor     r12d, r12d
        jmp     .L3
.L8:
        add     r12, 1
        cmp     rbx, r12
        je      .L4
.L3:
        movsx   esi, BYTE PTR [rbp+0+r12]
        mov     edx, 2
        mov     edi, OFFSET FLAT:.LC0
        call    memchr
        test    rax, rax
        je      .L8
        mov     rax, r12
        pop     rbx
        pop     rbp
        pop     r12
        ret
.L4:
        mov     r12, -1
        pop     rbx
        pop     rbp
        mov     rax, r12
        pop     r12
        ret

findFirstE_fast()：

findFirstE_fast(std::basic_string_view<char, std::char_traits<char> >):
        add     rdi, rsi
        cmp     rdi, rsi
        je      .L13
        mov     rax, rsi
        jmp     .L12
.L15:
        add     rax, 1
        cmp     rdi, rax
        je      .L13
.L12:
        movzx   edx, BYTE PTR [rax]
        and     edx, -33
        cmp     dl, 69
        jne     .L15
        sub     rax, rsi
        ret
.L13:
        mov     rax, -1
        ret

有趣的是，findFirstE_slow()需要memchr("eE", *current_char, 2)中的每个角色sv。另一方面，findFirstE_fast()通过将每个字符与sv“e”和“E”进行比较来完成我们合理预期的操作。

Clang 生成类似的输出。

问题：对于像我的测试中那样的短字符串，这里是否存在错过的优化？我是否缺少一些让 GCC 生成更快代码的东西？

Answer 1

libstdc++std::string_view::find_first_of看起来像：

size_type find_first_of(std::string_view v, std::size_t pos = 0) {
    if (v.empty()) return npos;
    for (; pos < size(); ++pos) {
        const char_type* p = traits_type::find(v.data(), v.size(), this->data()[pos]);
        if (p) return pos;
    }
    return npos;
}

您可以看到如何traits_type::find转变为memchr.

问题的关键是 的memchr("eE", this->data()[pos], 2) != nullptr编译方式与 不同 this->data()[pos] == 'e' || this->data()[pos] == 'E'，尽管后者效率更高。

您可以通过尝试编译来检查这一点：

constexpr unsigned char characters[] = "eE";

bool a(unsigned char* p) {
    return __builtin_memchr(characters, *p, 2);
}

bool b(unsigned char* p) {
    return *p == characters[0] || *p == characters[1];
}

这是一个错过的优化，但您可以提示编译器不要将 memchr 与自定义特征类型一起使用：

struct char_traits : std::char_traits<char> {
    static constexpr const char_type* find(const char_type* p, std::size_t count, const char_type& ch) {
        if (__builtin_constant_p(count) && count < 5) {
            switch (count) {
                case 0: return nullptr;
                case 1: return ch == *p ? p : nullptr;
                case 2: return ch == *p ? p : ch == *++p ? p : nullptr;
                case 3: return ch == *p ? p : ch == *++p ? p : ch == *++p ? p : nullptr;
                case 4: return ch == *p ? p : ch == *++p ? p : ch == *++p ? p : ch == *++p ? p : nullptr;
            }
        }
        return std::char_traits<char>::find(p, count, ch);
    }
};

using string_view = std::basic_string_view<char, char_traits>;

size_t findFirstE_slow(string_view sv) {
  return sv.find_first_of(characters);
}

// Also your "fast" version needs to return
//    return it == sv.end() ? string_view::npos : size_t(it - sv.begin());
// to be equivalent

（https://godbolt.org/z/bhPPxjboE）

https://quick-bench.com/q/QVxVTxGEagUUCPuhFi9T8wjI1qQ表示慢速版本现在仅慢 1.3 倍。使用较大的字符串（https://quick-bench.com/q/el0ukDywBNMoGsEb33PM_g4WUaY;之前有 8000 个字符'e'），差异几乎不明显。

现在的主要区别在于，一个迭代索引，另一个迭代指针（最后返回差异）。汇编中的两个不同的指令是movzx edx, BYTE PTR [rsi+rax]和movzx edx, BYTE PTR [rax] sub rax, rsi，您应该发现第二个版本稍微快一点（特别是渐近地，因为减法发生在循环之外）