c++ - 为什么 struct{u64} 比 struct{u32,u32} 更快？

Question

嗯，ideone显示速度较慢。在我的虚拟机(ubuntu werewolf)中的 g++ 4.9.3 中，我得到 A: 830 B: 460。在任何一种情况下，为什么一个比另一个更快？我假设 A 是按引用推送，而 B 是按值推送，但我不明白为什么会这样做。我尝试使用 operator<(A a, ...但这并没有帮助。

struct A {
    u32 first, second;
    A(int f, int s):first(f),second(s) {}
    bool operator<(u32 b) const { return first < b; }
};
//bool operator<(const A&a, u32 b) { return a.first < b; }

struct B {
    u64 v;
    B(int f, int s) { v = ((long)f << 32) | s; }
    bool operator<(u32 b) const {
        return (v >> 32) < b;
    }
};
u32 get_value(deque<A>& d, u32 v) {
    auto p = lower_bound(d.begin(), d.end(), v);
    if (p != d.end())
        return p->second;
    else
        return UINT_MAX;
}
u32 get_value(deque<B>& d, u32 v) {
    auto p = lower_bound(d.begin(), d.end(), v);
    if (p != d.end())
        return p->v & 0xFFFFFFFF;
    else
        return UINT_MAX;
}

int main(int argc, char *argv[]) {

    {
        deque<A> d;
        struct timeval s, e;
        gettimeofday(&s, 0);
        for (int i = 0; i < 1024LL * 1024 * 1024 * 3 / 32; ++i)
            d.emplace_back(A(i, i ^ 92142));
        long v = 0;
        for (int i = 0; i < 10000; ++i)
            v += get_value(d, i * 3 + 1);

        gettimeofday(&e, 0);
        auto sec = e.tv_sec - s.tv_sec;
        auto usc = e.tv_usec - s.tv_usec;
        printf("A %ld\n", v);
        printf("Time: %lu\n", sec * 1000 + usc / 1000);
    }
    {
        deque<B> d;
        struct timeval s, e;
        gettimeofday(&s, 0);
        for (int i = 0; i < 1024LL * 1024 * 1024 * 3 / 32; ++i)
            d.emplace_back(B(i, i ^ 92142));
        long v = 0;
        for (int i = 0; i < 10000; ++i)
            v += get_value(d, i * 3 + 1);

        gettimeofday(&e, 0);
        auto sec = e.tv_sec - s.tv_sec;
        auto usc = e.tv_usec - s.tv_usec;
        printf("A %ld\n", v);
        printf("Time: %lu\n", sec * 1000 + usc / 1000);
    }
}

Answer 1

我认为 struct B { u64 v; } 可以加速您的工作因为你将它与编译时常量参数一起使用。编译器可以将这两个值组合到 64 位存储中。

我做了一个简单的非成员函数来获取为operater<的非内联情况生成的asm输出。对于 A 和 B。如 godbolt shows ， struct A::operator< 的汇编效率显着提高。 B::operator< 确实执行 64 位加载，然后进行移位。我对 asm 进行了评论，以方便那些不太了解 x86 的人。

bool comp_A(const struct A &lhs, u32 rhs) { return lhs < rhs; }
bool comp_B(const struct B &lhs, u32 rhs) { return lhs < rhs; }

comp_A(A const&, unsigned int):
    cmpl    %esi, (%rdi)  # compare with lhs->first as a memory operand
    setb    %al
    ret
comp_B(B const&, unsigned int):
    movq    (%rdi), %rax  # load lhs->v
    movl    %esi, %esi    # zero-extend the low 32b of rhs
    shrq    $32, %rax     # shift the high32 of v down to the low 32
    cmpq    %rsi, %rax
    setb    %al           # al=1 if rax "bigger than" rsi, else 0.
    ret

x86 具有快速硬件支持，可以将任意大小的整数从 RAM 加载到 32 或 64 位临时(在寄存器中)。 movzx和movsx零或符号扩展，并且与 mov 的常规负载一样便宜。 32 位操作始终将目标寄存器的高 32 位归零，因此对旧值的错误依赖不是问题。 (它们适用于 16 位和 8 位操作，这就是为什么 movzx 到 32 位临时是一个很好的计划。)

我还没有查看你的实际函数的汇编，因为它很大。不过，我建议一般使用版本 A。可能是 gcc 没有通过 64 位移动来复制它，也许是因为它可能没有对齐？ x86 不需要对齐(非 AVX(传统 SSE)16 字节内存操作数除外)。然而，IIRC 仅从 2008 年或 2009 年的 CPU(Intel 的 Nehalem)开始，只要不跨越缓存线，未对齐的加载/存储就不会受到惩罚。 gcc 可能仍然不愿意使用它们，因为潜在的 yield 小于未对齐访问速度慢的旧 CPU 的潜在负面影响。

---

通过 union ，您可能会得到 gcc 的两全其美。

union A { u64 v; u32 first_last[2]; };

这可能会导致编译器在复制时使用 64 位移动，但仍会执行 32 位加载 A.first_last[0]并且在访问各个字段时不需要移动。