Охота на самую быструю реализацию Хэмминга С C

Question

Я хочу найти, сколько разных символов имеет две строки одинаковой длины. Я обнаружил, что алгоритмы xoring считаются самыми быстрыми, но они возвращают расстояние, выраженное в битах. Я хочу, чтобы результаты были выражены в символах. Предположим, что «животное» и «яма» есть расстояние 1 выражается в символах, а «е» и «я» может иметь два различных бита, так XORing возвращается 2.

Функция я написал является:

// na = length of both strings 
unsigned int HammingDistance(const char* a, unsigned int na, const char* b) { 

    unsigned int num_mismatches = 0; 
    while (na) { 
     if (*a != *b) 
      ++num_mismatches; 

     --na; 
     ++a; 
     ++b; 
    } 

    return num_mismatches; 
} 

Может ли он стать быстрее? Возможно использование некоторых команд нижнего уровня или реализация другого алгоритма?

система: Gcc 4.7.2 на Intel Xeon X5650

Спасибо

Answer 1

Вы можете сделать сравнение сравнить несколько байт в то время, выполнив оператор побитового на родной размер целого.

В вашем коде вы сравниваете равенство байта за раз, но ваш процессор может сравнивать хотя бы одно слово за один цикл и 8 байтов, если это x86-64. Конечно, характеристики производительности зависят от архитектуры процессора.

Но если вы продвигаетесь через два указателя с шагом 8, то в некоторых сценариях он может быть быстрее. Когда он должен читать строки из основной памяти, время загрузки памяти фактически будет доминировать над производительностью. Но если строки находятся в кэше ЦП, вы можете сделать XOR и интерпретировать результаты, проверив, где в 64-битном значении биты будут изменены.

Подсчет ведер, которые не являются 0, может быть выполнен с использованием варианта алгоритма SWAR, начиная с 0x33333333 вместо 0x55555555.

С алгоритмом будет сложнее работать, поскольку для этого потребуется использовать указатели uint64_t, которые имеют правильное выравнивание памяти. Вам понадобится преамбула и постскриптум, которые охватывают оставшиеся байты. Возможно, вы должны прочитать сборку, которую выводит компилятор, и посмотреть, не делает ли она что-то более умное, прежде чем вы попробуете что-то более сложное в коде.

Answer 2

Вместо

if (*a != *b) 
    ++num_mismatches; 

это будет быстрее на некоторых архитектурах (с 8 битными байтами), поскольку он позволяет избежать ветвей:

int bits = *a^*b; 
bits |= bits >> 4; 
bits |= bits >> 2; 
bits |= bits >> 1; 
num_mismatches += bits & 1; 

Answer 3

Как о петле разворачивании:

while (na >= 8){ 
    num_mismatches += (a[0] != b[0]); 
    num_mismatches += (a[1] != b[1]); 
    num_mismatches += (a[2] != b[2]); 
    num_mismatches += (a[3] != b[3]); 
    num_mismatches += (a[4] != b[4]); 
    num_mismatches += (a[5] != b[5]); 
    num_mismatches += (a[6] != b[6]); 
    num_mismatches += (a[7] != b[7]); 
    a += 8; b += 8; na -= 8; 
} 
if (na >= 4){ 
    num_mismatches += (a[0] != b[0]); 
    num_mismatches += (a[1] != b[1]); 
    num_mismatches += (a[2] != b[2]); 
    num_mismatches += (a[3] != b[3]); 
    a += 4; b += 4; na -= 4; 
} 
if (na >= 2){ 
    num_mismatches += (a[0] != b[0]); 
    num_mismatches += (a[1] != b[1]); 
    a += 2; b += 2; na -= 2; 
} 
if (na >= 1){ 
    num_mismatches += (a[0] != b[0]); 
    a += 1; b += 1; na -= 1; 
} 

Кроме того, если вы знаете, что есть длинные отрезки одинаковых символов, вы можете наложить указатели на long* и сравнить их по 4 за раз, и только если не равный взгляд на отдельные символы. Этот код основан на memset и memcpy Быстро. Он копирует строки в массивы long, чтобы 1) устранить проблемы с выравниванием и 2) заполнить строки нулями до целого числа long. Поскольку он сравнивает каждую пару long s, если они не равны, то они направляют указатели на char* и подсчитывают неравные символы. Основная петля также может быть развернута, как описано выше.

long la[BIG_ENOUGH]; 
long lb[BIG_ENOUGH]; 
memset(la, 0, sizeof(la)); 
memset(lb, 0, sizeof(lb)); 
memcpy(la, a, na); 
memcpy(lb, b, nb); 
int nla = (na + 3) & ~3; // assuming sizeof(long) = 4 
long *pa = la, *pb = lb; 
while(nla >= 1){ 
    if (pa[0] != pb[0]){ 
    num_mismatches += (((char*)pa[0])[0] != ((char*)pb[0])[0]) 
        + (((char*)pa[0])[1] != ((char*)pb[0])[1]) 
        + (((char*)pa[0])[2] != ((char*)pb[0])[2]) 
        + (((char*)pa[0])[3] != ((char*)pb[0])[3]) 
        ; 
    } 
    pa += 1;pb += 1; nla -= 1; 
} 

Answer 4

Если строки заполняются нулями, чтобы всегда быть 32 байта и их адреса 16 выровнены, вы могли бы сделать что-то вроде этого: (код не тестировался профилированный)

movdqa xmm0, [a] 
movdqa xmm1, [a + 16] 
pcmpeqb xmm0, [b] 
pcmpeqb xmm1, [b + 16] 
pxor xmm2, xmm2 
psadbw xmm0, xmm2 
psadbw xmm1, xmm2 
pextrw ax, xmm0, 0 
pextrw dx, xmm1, 0 
add ax, dx 
movsx eax, ax 
neg eax 

Но если строки обычно крошечные, он делает много ненужной работы, и это может быть не быстрее. Это должно быть быстрее, если строки обычно (почти) 32 байта.

---

редактировать: Я написал этот ответ, прежде чем я увидел обновленный комментарий - если строки, как правило, это крошечное, это, вероятно, не очень хорошо. 16-байтная версия может (возможно) быть полезной, хотя (условно выполняйте вторую итерацию, ветвь для нее должна быть хорошо предсказана, потому что она будет редко приниматься). Но с такими короткими строками нормальный код трудно превзойти.

movdqa xmm0, [a] 
pxor xmm1, xmm1 
pcmpeqb xmm0, [b] 
psadbw xmm0, xmm1 
pextrw ax, xmm0, 0 
movsx eax, ax 
neg eax