C++ 性能 : checking a block of memory for having specific values in specific cells

Question

我正在研究 2D Bin Packing 算法。我问过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 占用的整个字节。但我更关心速度，你认为它会让事情变得更快吗？

谢谢!

更新:我将 int* pos 替换为 rect pos(与 best 相同)，正如 MSalters 所建议的。起初我看到了改进，但我用更大的数据集进行了更多测试，它似乎回到了正常的运行时间。我会尝试建议的其他技术，并会及时通知您。

更新:使用memset 和memchr 将速度提高了大约两倍。用 '\1' 和 '\0' 替换 'x' 和 'o' 没有显示任何改进。 __restrict 也没有帮助。总的来说，我对程序的性能感到满意，因为我还对算法本身进行了一些改进。我还没有尝试使用位图并使用 -02 (-03) 进行编译...再次感谢大家。

Answer 1

最好的可能性是使用复杂度更高的算法。

但即使是您当前的算法也可以加速。尝试使用 SSE 指令一次测试 ~16 个字节，你也可以做一个大的分配并自己拆分，这将比使用库分配器更快(库分配器的优点是让你单独释放 block ，但我不要认为你需要那个功能)。