草庐IT

c++ - 查看固定长度数组之间有多少字节相等的最快方法

coder 2023-11-12 原文

我有 2 个包含 16 个元素(字符)的数组，我需要“比较”它们并查看两者之间有多少元素相等。

这个例程将被使用数百万次(通常运行大约 60 或 7000 万次)，所以我需要它尽可能快。我正在研究 C++(C++Builder 2007，备案)

现在，我有一个简单的:

matches += array1[0] == array2[0];

重复 16 次(因为性能分析似乎比使用 for 循环快 30%)

有没有其他方法可以更快地工作？

关于环境和数据本身的一些数据:

  • 我使用的是 C++Builder，它没有任何速度优化需要考虑。我最终会尝试使用另一个编译器，但现在我只能使用这个。
  • 大多数时候数据会有所不同。 100% 相等的数据通常非常非常少(可能少于 1%)

最佳答案

更新:这个答案已经过修改，使我的评论与下面提供的源代码相匹配。

如果您能够使用 SSE2 和 popcnt 指令，则可以进行优化。

16 个字节恰好适合 SSE 寄存器。使用 C++ 和程序集/内在函数，将两个 16 字节数组加载到 xmm 寄存器中，并对它们进行 cmp。这会生成一个位掩码，表示比较的真/假条件。然后使用 movmsk 指令将位掩码的位表示加载到 x86 寄存器中；这然后变成一个位字段，您可以在其中计算所有 1 以确定您有多少个真值。硬件 popcnt 指令可以是一种快速计算寄存器中所有 1 的方法。

这尤其需要汇编/内部函数和 SSE 的知识。您应该能够找到两者的网络资源。

如果您在不支持 SSE2 或 popcnt 的机器上运行此代码，则必须遍历数组并使用展开的循环方法计算差异。

祝你好运

编辑: 由于您表示您不知道汇编，下面是一些示例代码来说明我的回答:

#include "stdafx.h"
#include <iostream>
#include "intrin.h"

inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
    __m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
    __m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );

    return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}

int _tmain( int argc, _TCHAR* argv[] )
{
    unsigned count = 0;
    char    arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
    char    arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };

    count = __popcnt( cmpArray16( arr1, arr2 ) );

    std::cout << "The number of equivalent bytes = " << count << std::endl;

    return 0;
}

一些注意事项:此函数使用 SSE2 指令和 Phenom 处理器(这是我使用的机器)中引入的 popcnt 指令。我相信最新的带有 SSE4 的 Intel 处理器也有 popcnt。此函数不检查 CPUID 的指令支持；如果在没有 SSE2 或 popcnt 的处理器上使用该函数是未定义的(您可能会得到无效的操作码指令)。该检测代码是一个单独的线程。

我没有为这段代码计时；我认为它更快的原因是因为它一次比较 16 个字节，无分支。您应该修改它以适应您的环境，并自己计时以查看它是否适合您。我在 VS2008 SP1 上编写并测试了它。

SSE 更喜欢在自然 16 字节边界上对齐的数据；如果你能保证那么你应该得到额外的速度改进，你可以将 _mm_loadu_si128 指令更改为 _mm_load_si128，这需要对齐。

关于c++ - 查看固定长度数组之间有多少字节相等的最快方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/116485/

定长度数sectionpopcnt的c++arraysoptimization

有关c++ - 查看固定长度数组之间有多少字节相等的最快方法的更多相关文章

  1. ruby-on-rails - unicode 字符串的长度 - 2

    在我的Rails(2.3，Ruby1.8.7)应用程序中，我需要将字符串截断到一定长度。该字符串是unicode，在控制台中运行测试时，例如'א'.length，我意识到返回了双倍长度。我想要一个与编码无关的长度，以便对unicode字符串或latin1编码字符串进行相同的截断。我已经了解了Ruby的大部分unicode资料，但仍然有些一头雾水。应该如何解决这个问题？ 最佳答案 Rails有一个返回多字节字符的mb_chars方法。试试unicode_string.mb_chars.slice(0,50)

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  4. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  5. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  6. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  7. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  8. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  9. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  10. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

随机推荐