0

u_int64[8]在 C/C++中比较两个数组的最快方法是什么？

数组 1 在std::vector（约 10k 个元素）内，数组 2 在动态分配的结构内。（memcmp()这里有误报吗？）

我的（伪 C）实现：

typedef struct {            
    u_int64_t array[8];
}work_t;

/* alloc and fill array work_t* work = new (std::nothrow) work_t etc... */

for(u_int32_t i=0; i < some_std_vector.size(); i++) {       

                if((some_std_vector[i]->array[0] == work->array[0]) &&
                   (some_std_vector[i]->array[1] == work->array[1]) &&
                   (some_std_vector[i]->array[2] == work->array[2]) &&
                   (some_std_vector[i]->array[3] == work->array[3]) &&
                   (some_std_vector[i]->array[4] == work->array[4]) &&
                   (some_std_vector[i]->array[5] == work->array[5]) &&
                   (some_std_vector[i]->array[6] == work->array[6]) &&
                   (some_std_vector[i]->array[7] == work->array[7])) {
                    //...do some stuff...
                }
}

目标平台是Linux x86_64 gcc 4.9.2，循环在a里面pthread，tcmalloc使用，代码用-O2编译

4

4 回答 4

1

我想真正回答这个问题的唯一方法是编写两个例程，一个使用您提供的循环，另一个使用 memcmp。然后，分析并查看拆解，看看哪个看起来最有效。（您也可能会着迷并使用分析器。）

也可以在汇编中编写一个自定义例程以直接比较它们（即专门用于比较您正在查看的内容的自定义版本的 memcmp）并将其与其他两个进行比较。

无论哪种方式，我都同意其他人的观点，即一切都可能非常接近（使用现代编译器）；但是，如果您真的想保留它，则必须使用分析器对其进行测试和/或具有查看创建的程序集并知道哪个程序集会更快的技能。

于 2014-12-05T13:24:29.107 回答
1

这里有一些提高速度的建议。

尽可能使用局部变量

不要使用指针，例如 -> 运算符，而是使用局部变量或将变量作为引用传递。编译器可能会生成额外的代码，用于将指针加载到寄存器中，然后解除对寄存器的引用以获取值。

使用处理器的数据缓存 大多数现代处理器都有数据缓存。如果您可以使用数据加载多个变量，然后进行比较，则可以调用处理器的数据缓存。

此外，设计您的数据以有效地适应数据缓存行。这意味着数据成员（包括数组）应该彼此相邻或非常接近。

块比较

在最低级别，您正在比较许多连续的字节。正如其他人所提到的，您可以通过使用内存比较功能获得更好的性能。

另一个建议是通过将值加载到单独的变量中来帮助编译器，比较这些值：

for (/*...*/)
{
//...
    uint64_t a1 = some_std_vector[i]->array[0];
    uint64_t a2 = some_std_vector[i]->array[1];
    uint64_t a3 = some_std_vector[i]->array[2];
    uint64_t a4 = some_std_vector[i]->array[3];

    uint64_t b1 = work->array[0];
    uint64_t b2 = work->array[1];
    uint64_t b3 = work->array[2];
    uint64_t b4 = work->array[3];

    if ((a1 == b1) && (a2 == b2) && (a3 == b3) && (a4 == b4))
    {
       //...
    }
}

这里的概念是先将变量加载到多个寄存器中，然后比较寄存器。

查看汇编语言和配置文件

使用答案中提供的所有技术，最好的方法是编写一个代码，查看汇编语言和配置文件。请记住将优化级别设置为高以提高速度。

如果您的进程有可以加快速度的特殊指令，您需要验证编译器是否正在使用它们，或者有理由不使用它们。

于 2014-12-05T15:30:12.077 回答
0

根据您使用的设备和您使用的编译器，您可以尝试一些“特定”问题。例如，在某些编译器中，有一些技术允许从内存执行广泛的加载，因此可以实现最快的多重比较。还有一些方法可以手动展开循环，因此它们执行得更快。但这取决于编译器。您总是可以尝试一些方法并检查汇编代码以查看哪种方法最快。

于 2014-12-05T13:22:32.877 回答
0

我做了一些测试并查看了 gcc memcmp、glibc memcmp 和我上面的代码。glibc-2.20 memcmp 是最快的方式，因为它使用平台特定的优化（在我的例子中）。

gcc memcmp 要慢得多。( bug43052 , 使用 -fno-builtin-memcmp 编译)

于 2014-12-08T08:42:22.240 回答