So sánh bộ nhớ (với vị trí khác biệt)

Question

Có cách nào so sánh hai khối bộ nhớ và biết tại thời điểm nào chúng khác nhau (memcmp() không đáp ứng yêu cầu này)? Tôi sẽ không muốn thực hiện các vòng tốn kém. Cảm ơn trước.

Kính trọng, Neo_b

Answer 1

So với bất cứ điều gì khác mà bạn đang làm, một vòng khá rẻ: với chi phí lớn sẽ được lấy dữ liệu từ ram ở nơi đầu tiên (hoặc đĩa!).

Answer 2

Bạn không thể tránh lặp với bộ nhớ so sánh hơn một vài byte. Viết các thuật toán như bạn có thể tưởng tượng nó. Nó đủ đơn giản và bạn có thể ngạc nhiên khi trình biên dịch tối ưu hóa mã như thế này.

Answer 3

std::mismatch sẽ làm điều đó cho bạn cùng với std::distance.

Answer 4

memcmp đơn giản thực hiện "vòng lặp tốn kém", byte cho byte. Ví dụ: đây là triển khai của Microsoft:

EXTERN_C int __cdecl memcmp(const void *Ptr1, const void *Ptr2, size_t Count) 
{ 
    INT v = 0; 
    BYTE *p1 = (BYTE *)Ptr1; 
    BYTE *p2 = (BYTE *)Ptr2; 

    while(Count-- > 0 && v == 0) { 
     v = *(p1++) - *(p2++); 
    } 

    return v; 
} 

Hầu hết các triển khai khác cũng thực hiện tương tự. Đối với nhu cầu của bạn, bạn có thể làm một cái gì đó như thế này:

long my_memcmp(const void *Ptr1, const void *Ptr2, size_t Count) 
{ 
    INT v = 0; 
    long pos = 0; 
    BYTE *p1 = (BYTE *)Ptr1; 
    BYTE *p2 = (BYTE *)Ptr2; 

    while(Count-- > 0 && v == 0) 
    { 
     v = *(p1++) - *(p2++); 
     if (v == 0) 
      pos++; 
     else 
      break; 
    } 

    return pos; 
} 

Answer 5

Bạn sẽ luôn cần một vòng lặp. Nhưng bạn có thể điểm chuẩn nếu looping bởi 4 byte (cast để int *) hoặc 8 byte (uint64_t hoặc long long int) là nhanh hơn so với các giải pháp ngây thơ mỗi byte.

Thậm chí tốt hơn, tùy thuộc vào độ dài (giả sử,> 1kb) bạn có thể hủy vòng lặp, nghĩa là bạn kiểm tra ví dụ: mỗi 8 int/uint64_t và trên một điểm không phù hợp, xác định byte khác nhau đầu tiên.

uint64_t *bigsteps1 = (uint64_t*)m1; 
uint64_t *bigsteps2 = (uint64_t*)m2; 
int steps = min(m1_len,m2_len)/sizeof(uint64_t); 
int i; 
for (i=0; i<steps; i+=8) 
{ 
    if (bigsteps1[i] != bigsteps2[i] 
     || bigsteps1[i+1] != bigsteps2[i+1] 
    /// .... 
     || bigsteps1[i+7] != bigsteps2[i+7]) break; 
} 

// i<steps tells if we found a difference 
// end game is trivial, left as an excercise to the reader. 

Các tháo vật cuộn tròn lại vòng lặp cũng có thể phản tác dụng, vì bạn có tất cả những điều + N trong đó và i + = 8 là tốt. Điểm chuẩn để chắc chắn.

ps cũng kiểm tra sự liên kết bộ nhớ: đây sẽ là nhanh nhất khi m1&0xff == m2&0xff == 0

Answer 6

Nếu có một cách tốt hơn để so sánh hai khối bộ nhớ, memcmp sẽ được thực hiện lại để làm điều đó.

Đã nói thường xuyên, memcmp có triển khai di động mặc định trong thư viện C chuẩn nhưng thường có trình biên dịch được thực hiện dưới dạng hàm dựng sẵn. Hàm dựng sẵn này nên được tối ưu hóa cao cho kiến ​​trúc đích. Do đó, hãy thực hiện thư viện với một nhúm muối.