string_view::find_first_of的优化被忽略了

Question

string_view::find_first_of的优化被忽略了

c++assemblygccclangcompiler-optimization

6

更新：相关的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

编译器Explorer输出：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() 在 sv 中的每个字符都调用了 memchr("eE", *current_char, 2)。另一方面，findFirstE_fast() 通过将 sv 中的每个字符与 'e' 和 'E' 进行比较来实现我们合理期望的功能。

Clang 生成类似的输出。

问题：对于像我测试中的短字符串，这里是否有被忽视的优化？我是否遗漏了一些东西可以让 GCC 生成更快的代码？

- zwliew

更新：此补丁已针对小常量字符串进行了处理： https://gcc.gnu.org/git/gitweb.cgi?p=gcc.git;h=c6cf555a88f8ffb8ec85c2b94fe656ab217260ea - zwliew

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Artyer · Accepted Answer

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];
}

这是一个被忽视的优化，但是你可以通过提示编译器不要使用带有自定义 traits 类型的 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，你应该会发现第二个版本稍微快一些（特别是渐进地，因为减法发生在循环外）。