C++性能:检查内存块在特定单元中是否有特定值
我正在做一个关于2D装箱算法的研究。我问过similar question关于PHP性能的问题--打包起来太慢了--现在代码被转换成了C++。
它仍然很慢。因此，我的程序所做的就是分配动态内存块，并用字符'o‘填充它们
char* bin;
bin = new (nothrow) char[area];
if (bin == 0) {
cout << "Error: " << area << " bytes could not be allocated";
return false;
}
for (int i=0; i<area; i++) {
bin[i]='o';
}(对于我的数据集，它们的大小在1kb到30kb之间)
然后，程序检查当前内存块中“x”字符的不同组合。
void place(char* bin, int* best, int width)
{
for (int i=best[0]; i<best[0]+best[1]; i++)
for (int j=best[2]; j<best[2]+best[3]; j++)
bin[i*width+j] = 'x';
}其中一个检查非重叠的函数在运行时会被调用数百万次。
bool fits(char* bin, int* pos, int width)
{
for (int i=pos[0]; i<pos[0]+pos[1]; i++)
for (int j=pos[2]; j<pos[2]+pos[3]; j++)
if (bin[i*width+j] == 'x')
return false;
return true;
}所有其他的东西只需要运行时间的百分之一，所以我需要让这两个人(适合和放置)更快。谁是罪魁祸首？
因为我只有两个选项'x‘和'o'，所以我可以尝试只使用一个位，而不是char接受的整个字节。但我更关心的是速度，你认为它会让事情变得更快吗？
谢谢!
更新:我按照MSalters的建议，将int* pos替换为rect pos (best也是如此)。起初我看到了改进，但我用更大的数据集测试了更多，它似乎回到了正常的运行时。我将尝试其他建议的技术，并将与您保持联系。
更新:使用memset和memchr的速度提高了两倍。将'x‘和'o’替换为'\1‘和'\0’没有任何改进。__restrict也帮不上忙。总体而言，我现在对程序的性能感到满意，因为我还对算法本身进行了一些改进。我还没有尝试使用位图并使用-02 (-03)进行编译...再次感谢大家。
回答 8
Stack Overflow用户
发布于 2011-02-11 13:15:50
最好的可能性是使用复杂度更高的算法。
但即使是你当前的算法也可以加快速度。尝试使用SSE指令一次测试~16字节，你也可以自己做一个大的分配并拆分它，这将比使用库分配器更快(库分配器的优点是让你单独释放块，但我不认为你需要这个功能)。
Stack Overflow用户
发布于 2011-02-11 13:22:50
当然:剖析它！
在第一种情况下，使用位而不是字节并不会更快。
但是，考虑到对于字符，您可以将4或8字节的块转换为无符号的32位或64位整数(确保处理对齐)，并将其与块中的'oooooooo‘或’oooooooo‘的值进行比较。这允许进行非常快速的比较。
现在已经向下介绍了整数方法，您可以看到您可以使用位方法做同样的事情，并在一次比较中处理64位。这肯定会给你带来真正的加速。
Stack Overflow用户
发布于 2011-02-11 13:14:13
位图也将提高速度，因为它们涉及的内存较少，因此将导致更多的内存引用来自缓存。此外，在place中，您可能希望将best的元素复制到局部变量中，以便编译器知道您对bin的写入不会更改best。如果您的编译器支持restrict的某些拼写，您可能也希望使用该拼写。您还可以将place中的内循环替换为memset库函数，并将fits中的内循环替换为memchr；不过，这些可能不会带来很大的性能改进。
https://stackoverflow.com/questions/4965817
复制相似问题
腾讯云开发者
