8

我需要将一块内存与 C 中的一个固定值进行比较。我可以用 memcmp 做到这一点吗？就像是：

memcmp (starting_address , fixed_value , num_byte)

我需要 fixed_value 是一个固定值而不是一个块的起始地址。

  1. 将固定值写入整个临时内存块不是一种选择，因为我的空间有限。
  2. 使用循环逐个写入和检查内存不是一种选择，因为它非常慢。

如果不可能，谁能告诉我一个与 memcmp 一样快（或更快）的解决方案？

谢谢，

编辑：假设我有 5GB 的内存可以容纳 0。我正在努力确保它们都是 0。检查块的第一个字节是否安全，然后执行以下操作：

memcmp (starting_address , starting_address + ONE_BYTE , FIVE_GB); ?

编辑：这就是为什么我需要使用 memcmp 而不是用户定义的循环：

这段代码运行了 546 个时钟周期：

memset(0x80000000 , 0x1 , 0x10000000);
memset(0x90000000 , 0x1 , 0x10000000);
memcmp(0x80000000 , 0x90000000 , 0x10000000);

与这个花费了 7669 个时钟滴答声的对比：

unsigned int i;
int flag = 0;
int *p = 0x80000000;
int *q = 0x90000000;
while(p < 0x90000000)
{
    if(*p++ != *q++)
    {
        flag = 1;
    }
}
4

6 回答 6

2

一种解决方案：

创建一个包含所有相同值的缓冲区并迭代地比较它。这样，您memcmp无需编写太多代码即可获得高效实现的优势：

static char val[4096]; // tune the size of the buffer if desired
/* at initialization: memset(val, 0x01, sizeof(val)) */

char *start, *ptr, *end;
// initialize start and end
for(ptr = start; ptr < end-sizeof(val); ptr += sizeof(val)) {
    if(memcmp(ptr, val, sizeof(val))
        goto not_all_val;
}
if(memcmp(ptr, val, end - ptr))
    goto not_all_val;

/* all val */
puts("all val");
return;

not_all_val:
puts("not all val");
return;

性能对比：

10000次迭代memcmp(buf, buf2, 4000000)（两个长度相同的缓冲区，与问题中的第一种方法相同）：

real    0m7.480s
user    0m7.375s
sys 0m0.103s

在 4000000 字节上逐字符比较 10000 次迭代（与第二种方法相同）：

real    0m27.004s
user    0m26.908s
sys 0m0.094s

建议方法的 10000 次迭代超过 4000000 字节：

real    0m3.194s
user    0m3.151s
sys 0m0.042s

YMMV（我用的是三年前的 Macbook Pro），但这种方法比比较完整缓冲区快两倍（可能是由于卓越的缓存性能），几乎是逐字符比较的十倍.

于 2013-06-10T23:24:57.407 回答
2

我刚刚在我的 Mac 上测试了这个循环，它击败了memcmp：

uint64_t *p = (uint64_t *)buffer1;
uint64_t compare;
memset(&compare, 1, sizeof compare);
for (i = 0; i < length/sizeof compare; i++)
{
    if (p[i] != compare)
        break;
}

完整的示例代码：

#include <stdio.h>
#include <string.h>
#include <sys/resource.h>
#include <time.h>
#include <stdlib.h>
#include <stdint.h>

// from: http://www.gnu.org/software/libc/manual/html_node/Elapsed-Time.html
void timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{
    /* Perform the carry for the later subtraction by updating y. */
    if (x->tv_usec < y->tv_usec)
    {
        int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
        y->tv_usec -= 1000000 * nsec;
        y->tv_sec += nsec;
    }

    if (x->tv_usec - y->tv_usec > 1000000)
    {
        int nsec = (x->tv_usec - y->tv_usec) / 1000000;
        y->tv_usec += 1000000 * nsec;
        y->tv_sec -= nsec;
    }

    /* Compute the time remaining to wait. tv_usec is certainly positive. */
    result->tv_sec = x->tv_sec - y->tv_sec;
    result->tv_usec = x->tv_usec - y->tv_usec;
}

int main(int argc, char **argv)
{
    struct rusage before;
    struct rusage after;
    struct timeval diff;
    size_t i;

    size_t length = strtoull(argv[1], NULL, 0);

    char *buffer1 = malloc(length);
    char *buffer2 = malloc(length);

    printf("filling...");
    fflush(stdout);
    memset(buffer1, 1, length);
    memset(buffer2, 1, length);
    printf(" done\n");

    getrusage(RUSAGE_SELF, &before);
    uint64_t *p = (uint64_t *)buffer1;
    uint64_t compare;
    memset(&compare, 1, sizeof compare);
    for (i = 0; i < length/sizeof compare; i++)
    {
        if (p[i] != compare)
            break;
    }
    if (i == length/sizeof compare)
        i = 0;
    getrusage(RUSAGE_SELF, &after);

    printf("\nloop (returned %zu):\n", i);
    timeval_subtract(&diff, &after.ru_utime, &before.ru_utime);
    printf("User:   %ld.%06d s\n", diff.tv_sec, diff.tv_usec);

    timeval_subtract(&diff, &after.ru_stime, &before.ru_stime);
    printf("System: %ld.%06d s\n", diff.tv_sec, diff.tv_usec);

    getrusage(RUSAGE_SELF, &before);
    i = memcmp(buffer1, buffer2, length);
    getrusage(RUSAGE_SELF, &after);

    printf("\nmemcmp (returned %zu):\n", i);
    timeval_subtract(&diff, &after.ru_utime, &before.ru_utime);
    printf("User:   %ld.%06d s\n", diff.tv_sec, diff.tv_usec);

    timeval_subtract(&diff, &after.ru_stime, &before.ru_stime);
    printf("System: %ld.%06d s\n", diff.tv_sec, diff.tv_usec);

    return 0;
}

并运行结果：

$ make
clang -Wall -Wextra -Werror -O3 -g -o example example.c
./example 0x10000000
filling... done

loop (returned 0):
User:   0.024078 s
System: 0.000011 s

memcmp (returned 0):
User:   0.036752 s
System: 0.000017 s

也许你可以做类似的事情？

注意：对于那些担心缓存变暖的人，我也在循环之前尝试了 memcmp 并得到了相同的结果。

于 2013-06-11T00:08:13.827 回答
1

memcmp带地址是比较内存块的最佳选择。无论您使用块内联还是使用块的内存地址，您仍然必须将块存储在某个地方。

您可以在编译时创建这样的块，例如：

int block[] = {3, 1, 4, 1, 5, 9};

然后block在你的memcmp.

如果您只是想确保将内存块设置为特定值，请使用for循环解决方案。您提出的任何其他解决方案都必须做同样的事情，检查整个块。

如果它是一个非常大的内存块并且花费的时间太长，另一种方法是完全删除该要求。我的意思是重新设计您的算法，使其变得不必要。假设您有一个 1G 块。

一个例子：不要将它们全部设置为零。相反，只需在您积极使用的前面设置位，并维护一个单独的length变量来指示您正在使用多少。

高度优化的memcmp 可能会优于用户循环，但您也可能会发现它没有，这仅仅是因为它必须满足一般情况 - 您针对零进行检查的特定情况可能允许编译器引入失败的优化memcmp。

与所有优化一样，衡量，不要猜测！

于 2013-06-10T22:40:18.563 回答
0

如果在运行 memcmp() 之后，为什么会期望内存发生变化？如果内存只属于您的进程，则不会修改它。如果这是共享内存，问题就会变得非常不同。

作为替代建议，我正在考虑使用 memset() 将所有内存设置为已知值-您已经在不到 546 个滴答声中完成了。

原因是：memset() 将在一次传递中将内存设置为已知值 - 通过相同的内存进行第二次传递以验证大约需要两倍的时间。

于 2013-06-10T23:42:56.793 回答
0

如果您无法控制谁写入该内存块，则不可能存在允许与单个值进行有效比较的智能算法。您将需要遍历整个块，甚至不能跳过一个单词。您唯一能做的就是一次比较更多数据，可能使用可以一次处理多个单词的机器指令。

如果您确实可以控制该内存并且只有您可以对其进行写入，那么您可以更聪明地确定其中的内容。例如，通过“浪费”一些空间来保存确定哪些字为零的位模式。例如，如果您的字是 32 位的，那么您将有一个单独的内存块，您可以在其中保存与实际内存块中的字数相同的字数。在这种情况下，这将花费您每 32 字节的可用内存 1 字节，这并不可怕。如果您确实需要字节粒度，那么成本要高得多：每 8 个 1 个。但您通常不需要那个；一旦找到未归零的单词，您就可以缩小搜索范围，并仅在该单词中搜索第一个非零字节。

于 2013-06-10T23:18:40.010 回答
0

一种选择是从 memcmp 的源代码开始，并对其进行修改以迭代地与固定缓冲区进行比较。这样，您将保留 memcmp 中内置的优化，避免外部循环的开销，并且仍然实现您的目标。您可以具有如下功能：

int memcmp2(const void *s1, size_t n1, const void *s2, size_t n2);

其中 n1 是缓冲区 s1 的大小，n2 是 s2 的大小。

于 2013-06-10T23:04:28.530 回答