Сравнение памяти (с разницей в положении)

Question

Есть ли способ сравнить два блока памяти и узнать, в какой момент они различаются (memcmp () не соответствует этому требованию)?Я не хотел бы выполнять дорогостоящие петли.Заранее спасибо.

С уважением, Neo_b

Answer 1

std :: mismatch сделает это за вас вместе std :: distance .

Answer 2

memcmp просто делает «дорогостоящий цикл», байт за байт. Например, вот реализация 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;
}

Большинство других реализаций делают то же самое. Для своих нужд вы можете сделать что-то вроде этого:

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 3

Нельзя избежать зацикливания при сравнении памяти более чем на несколько байтов. Напишите алгоритм, как вы можете себе это представить. Это достаточно просто, и вы можете быть удивлены, насколько хорошо компилятор оптимизирует код, подобный этому.

Answer 4

По сравнению с тем, что вы делаете, цикл обходится дешево: большая стоимость будет в первую очередь получать данные из оперативной памяти (или диска!).

Answer 5

Если бы был лучший способ сравнения двух блоков памяти, memcmp был бы переопределён для этого.

Сказав, что часто memcmp имеет переносимую реализацию по умолчанию в стандартной библиотеке C, но он часто реализуется самим компилятором как встроенная функция. Эта встроенная функция должна быть в высокой степени оптимизирована для целевой архитектуры. Взять реализацию библиотеки с небольшим количеством соли.

Answer 6

Вам всегда понадобится петля.Но вы могли бы сделать бенчмарк, если цикл на 4 байта (приведение к int *) или на 8 байтов (uint64_t или long long int) выполняется быстрее, чем простое на байтовое решение.

Еще лучше, в зависимости отдлина (скажем,> 1 КБ) вы можете развернуть цикл, то есть вы проверяете, например, на 8 int / uint64_t и при несоответствии точно определяете первый отличающийся байт.

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.

Развертывание цикла также может иметь неприятные последствиятам есть все эти + N вещей, а также i + = 8.Эталонный тест, чтобы быть уверенным.

ps также проверьте выравнивание памяти: это будет самым быстрым, когда m1&0xff == m2&0xff == 0