4

我正在尝试查看结构是否与结构0xFF的大小一样返回。

memcmp似乎是显而易见的起点，但我必须分配第二个内存块，用0xFF's. 这似乎只是一种浪费。

是否存在为此的标准功能？还是我应该通过 for 循环进行平底船和迭代？

4

7 回答 7

4

我不知道这个的标准功能。

我认为这memcmp 并不总是正确的选择（它需要两倍的内存带宽）。

我会写一个迭代（即使是一个非常幼稚的迭代）。大多数编译器都很好地优化了这一点（当被问到时）。所以他们可能会展开你的循环并且可能会进行单词比较（即使你编写了一个简单的字节迭代）。

您可以编写专门的openmp变体（至少在GCC上）。见http://openmp.org/

如果结构很大（例如几十千字节，因为 GPGPU <-> RAM 数据复制的成本）并且如果您有很多开发时间可以浪费，可以考虑使用OpenCL（特别是如果您有专门的硬件支持它，例如GPGPU）。它可能永远不值得付出代价（除非您在 GPGPU 工作时在 CPU 上做一些不需要大量内存带宽的事情）

我会编写简单的循环，并且不会手动优化（除非编译器优化代码的基准测试另有建议），因为瓶颈可能是内存带宽。

于 2014-08-06T17:09:42.483 回答
4

这里最明显的解决方案似乎是简单地循环结构的大小并逐字节进行比较。

分配块的方法0xFF应该memcmp实现相同但更高的空间复杂度。

于 2014-08-06T17:17:53.787 回答
3

这种函数的逻辑名称是memcchr- 它是 to memchras strcspnis to strspn。

看看这里：谷歌搜索 memcchr 的结果表明，它已经作为 FreeBSD 内核的一部分以该名称实现，并且他们已经尝试在明显的一次 1 字节循环之外对其进行优化。

可能需要做一些额外的工作才能使这个函数适用于除 FreeBSD 内核之外的任何程序。

于 2014-08-06T17:35:59.030 回答
2

有 memchr()，它与您要求的相反 - 搜索 mem 块中第一次出现的字节。afaik，没有标准功能来搜索与特定字节不匹配的字节。for 循环听起来像是要走的路。也许一次去 32/64 位以加快速度。

-- 一个额外的未回答：memcmp 将比 for 循环慢。首先，您需要填充与原始块大小相同的内存块（这部分可能需要与幼稚的 for 循环一样长的时间）。然后您需要将每个内存块读入寄存器以进行比较。for 循环将在寄存器中有一个值，并且只需读取一个内存块以与不变的寄存器进行比较。

于 2014-08-06T17:08:40.833 回答
2

我不知道这是否会对性能有很大帮助，但你可以遵循这个算法：

  1. 将结构的第一个字节与分配的内存 0xFF 的 1 个字节进行比较
  2. 将结构的第 2 个字节与结构的第 1 个字节进行比较
  3. 将结构的字节 3-4 与结构的字节 1-2 进行比较
  4. 将结构的 5-8 字节与结构的 1-4 字节进行比较

并以相同的方式继续，直到结构结束。如果在任何时候该语句为假，您就知道该结构并非全是 0xFF。当结构的剩余部分小于检查的第一部分时，您还需要以不同的方式处理它，但这应该相对简单。

最后，您分配了 1 个额外字节的内存，算法为 O(log n) （对我目前在答案中看到的略有改进）。

编辑：正如下面提到的escrafford，如果你在上面的部分中用“byte”代替“word”，它可能会运行得更快一点。我无法评论您可能会获得多少速度，但它会增加存储的额外内存（尽管在今天的计算机上只是少量）。

于 2014-08-06T17:34:02.213 回答
0

为什么 strlen() 的这种实现有效？. 做了一些快速测试；没有保证。

这应该返回0xFF字节数；如果它等于您开始使用它的数字，那么您就在保险箱中。（当然你可以让它返回0或者也可以。）满意时1删除s 。printf

#define LONGPTR_MASK (sizeof(long) - 1)

int find_no_ff (const char *memory, size_t length)
{
    const char *p;
    const unsigned long *lp;
    size_t remain = length, to_do;

    printf ("non-aligned, start:\n");
    /* Test the first few bytes until we have an aligned p */
    for (p = memory; (uintptr_t)p & LONGPTR_MASK; p++)
    {
        printf ("testing %02X\n", *p & 0xff);
        if (*p != '\xFF')
            return (p - memory);
        remain--;
    }

    printf ("passed.\n");

    printf ("aligned:\n");
    to_do = remain/sizeof(long);
    remain -= (to_do*sizeof(long));

    /* Scan the rest of the string using word sized operation */
    for (lp = (const unsigned long *)p; to_do--; lp++)
    {
        printf ("testing %08lX\n", *lp);
        if (*lp +1)
            return p - memory;
    }
    printf ("passed.\n");

    p = (const char *)lp;

    printf ("non-aligned, end:\n");
    /* Test the last bytes until we have an aligned p */
    while (remain--)
    {
        printf ("testing %02X\n", *p & 0xff);
        if (*p != '\xFF')
            return (p - memory);
        p++;
    }
    printf ("passed.\n");
    return p - memory;
}

int main (void)
{
    char data[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };

    printf ("input size: %ld\n", sizeof(data));
    printf ("test result: %d\n", find_no_ff (data, sizeof(data)));

    return 0;
}
于 2014-08-06T18:00:31.483 回答
0

我喜欢 Erik 的建议，但它可以以一种有趣的方式简化如下（未经测试）：

if((*pBytes == 0xFF) && (memcmp(pBytes, pBytes + 1, byteCount - 1) == 0)) // pBytes 处的 byteCount 字节为 0xFFs。

仅当 A) 第一个字节为 0xFF，并且 B) 每隔一个字节都等于它之前的字节时，该条件才会成立。该组合意味着每个字节都是 0xFF。

于 2018-05-05T22:55:46.687 回答