memcmp nhưng cần so sánh khối với giá trị cố định

Question

Tôi cần so sánh khối bộ nhớ với giá trị cố định trong C. Tôi có thể thực hiện việc này với memcmp không? Một cái gì đó như:

memcmp (starting_address, fixed_value, num_byte)

Tôi cần fixed_value trở thành một giá trị cố định không phải là địa chỉ bắt đầu của một khối.

1. Viết giá trị cố định cho toàn bộ khối bộ nhớ tạm thời không phải là tùy chọn vì tôi có không gian hạn chế.
2. Sử dụng vòng lặp để ghi và kiểm tra từng bộ nhớ một không phải là một tùy chọn vì nó rất chậm.

Nếu không ai có thể cho tôi biết giải pháp nhanh (hoặc nhanh hơn) so với memcmp?

Cảm ơn,

CHỈNH SỬA: Giả sử tôi có 5GB bộ nhớ chứa 0. Và tôi đang cố gắng đảm bảo tất cả đều là 0. Có an toàn để kiểm tra byte đầu tiên của khối sau đó thực hiện điều này:

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

EDIT: Đây là lý do tại sao tôi cần phải sử dụng memcmp và không phải là một người sử dụng được xác định vòng lặp:

Mã này mất 546 clock để chạy:

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

vs cái này mà mất 7669 clock:

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

Answer 1

tôi chỉ kiểm tra vòng lặp này trên máy Mac của tôi, và nó đập 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; 
} 

Toàn bộ mã ví dụ:

#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; 
} 

Và chạy kết quả:

$ 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 

Có lẽ bạn có thể làm một cái gì đó tương tự?

Lưu ý: Đối với những người quan ngại về việc làm ấm bộ nhớ cache, tôi cũng đã thử với memcmp trước vòng lặp và nhận được kết quả tương tự.

Answer 2

memcmp với một địa chỉ là lựa chọn tốt nhất để so sánh các khối bộ nhớ. Cho dù bạn đã sử dụng khối nội dòng hay sử dụng địa chỉ bộ nhớ của một khối, bạn vẫn phải lưu trữ khối ở đâu đó.

Bạn có thể tạo ra như một khối tại thời gian biên dịch với một cái gì đó như:

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

và sau đó chỉ cần sử dụng block trong memcmp của bạn.

Nếu bạn chỉ muốn đảm bảo một khối bộ nhớ được đặt thành giá trị cụ thể, hãy sử dụng giải pháp vòng lặp for. Bất kỳ giải pháp nào khác mà bạn đưa ra là sẽ phải làm điều tương tự, kiểm tra toàn bộ khối.

Một giải pháp thay thế, nếu đó là một khối bộ nhớ thực sự lớn và mất quá nhiều thời gian, là xóa hoàn toàn yêu cầu. Bằng cách đó, tôi có nghĩa là tái thiết kế các thuật toán của bạn để nó trở nên không cần thiết. Giả sử bạn có khối 1G.

Ví dụ: không đặt tất cả thành số không. Thay vào đó, chỉ đặt bit ở mặt trước bạn đang sử dụng và duy trì biến số length riêng biệt để cho biết bạn đang sử dụng bao nhiêu.

Một tối ưu hóa mạnh mẽ memcmp có thể hoạt động tốt hơn nhưng bạn cũng có thể thấy rằng nó không có, đơn giản vì nó phải phục vụ cho trường hợp chung - trường hợp cụ thể của bạn kiểm tra bằng 0 có thể cho phép trình biên dịch giới thiệu tối ưu hóa đánh bại memcmp.

Như với tất cả các tối ưu hóa, đo lường, đừng đoán!

Answer 3

Một tùy chọn sẽ là bắt đầu với mã nguồn cho memcmp và sửa đổi nó để so sánh với bộ đệm cố định, lặp lại. Bằng cách đó bạn sẽ giữ lại các tối ưu hóa được tích hợp vào memcmp, tránh chi phí của vòng lặp bên ngoài và vẫn đạt được mục tiêu của mình. Bạn có thể có một chức năng như sau:

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

Trong đó n1 là kích thước của bộ đệm s1 và n2 của s2.

Answer 4

Nếu bạn không kiểm soát được người ghi vào khối bộ nhớ đó, thì không thể tồn tại thuật toán thông minh cho phép so sánh hiệu quả với một giá trị đơn lẻ. Bạn sẽ cần phải lặp qua toàn bộ khối và bạn không thể bỏ qua ngay cả một từ duy nhất. Điều duy nhất bạn có thể làm là so sánh nhiều dữ liệu hơn cùng một lúc, có thể sử dụng các lệnh máy có thể xử lý nhiều từ cùng một lúc.

Nếu bạn có quyền kiểm soát bộ nhớ đó và chỉ bạn mới có thể ghi vào đó, bạn có thể thông minh hơn về việc xác định nội dung trong đó. Ví dụ bằng cách "lãng phí" một số không gian để giữ một mẫu bit xác định từ nào là số 0. Ví dụ, nếu từ của bạn là 32-bit, thì bạn sẽ có một khối bộ nhớ riêng biệt, nơi bạn giữ càng nhiều từ cộng lại với cùng một lượng bit như có các từ trong khối bộ nhớ thực của bạn. Trong trường hợp này, điều này sẽ khiến bạn tốn 1 byte cho mỗi 32 byte bộ nhớ có thể sử dụng, điều này không quá khủng khiếp. Nếu bạn thực sự cần byte-granularity, sau đó chi phí cao hơn nhiều: 1 trên 8. Nhưng bạn thường không cần điều đó; bạn có thể thu hẹp tìm kiếm khi bạn đã tìm thấy một từ không được đánh số 0 và chỉ tìm kiếm từ đó cho byte không phải 0 đầu tiên.

Answer 5

Một giải pháp:

Tạo bộ đệm chứa tất cả cùng giá trị và so sánh với giá trị đó theo cách lặp lại. Bằng cách đó bạn sẽ có được lợi thế của một memcmp thực hiện hiệu quả mà không cần phải viết quá nhiều mã:

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; 

Performance so sánh:

10000 lần lặp của memcmp(buf, buf2, 4000000) (hai bộ đệm của cùng độ dài, tương tự như phương pháp đầu tiên trong câu hỏi):

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

10000 lần lặp của nhân vật theo từng ký tự so sánh trên 4000000 byte (tương tự như phương pháp thứ hai):

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

10000 lần lặp của phương pháp đề xuất ở trên hơn 4000000 byte:

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

YMMV (Tôi đang trên một Macbook ba tuổi Pro), nhưng phương pháp này là hai lần nhanh như so sánh một bộ đệm hoàn chỉnh (có khả năng do hiệu suất bộ nhớ cache cao cấp) và gần như là gấp mười lần so với so sánh từng ký tự.

Answer 6

Nếu, sau khi chạy memcmp(), tại sao bạn mong đợi thay đổi bộ nhớ? Nếu bộ nhớ chỉ thuộc về tiến trình của bạn thì sẽ không có gì thay đổi. Nếu điều này được chia sẻ bộ nhớ vấn đề trở nên rất khác nhau.

Là một đề xuất thay thế, tôi đã nghĩ đến việc sử dụng memset() để đặt tất cả bộ nhớ một giá trị đã biết - mà bạn đã thực hiện trong ít hơn 546 bọ ve.

Lý do là: memset() sẽ đặt bộ nhớ thành giá trị đã biết trong một lần truyền