Самый быстрый способ узнать, сколько байтов равняется между массивами с фиксированной длиной

Ответ 1

UPDATE: этот ответ был изменен, чтобы мои комментарии соответствовали исходному коду, представленному ниже.

Доступна оптимизация, если у вас есть возможность использовать инструкции SSE2 и popcnt.

16 байтов удачно сочетаются в регистре SSE. Используя С++ и сборку/встроенные функции, загрузите два массива по 16 байт в регистры xmm и cmp. Это создает битовую маску, представляющую истинное/ложное условие сравнения. Затем вы используете инструкцию movmsk для загрузки битового представления битмаски в регистр x86; это становится бит полем, где вы можете подсчитать все 1, чтобы определить, сколько истинно значений у вас было. Аппаратная команда popcnt может быть быстрым способом подсчета всех 1 в регистре.

Это требует знания сборки/встроенных функций и SSE в частности. Вы должны иметь возможность находить веб-ресурсы для обоих.

Если вы запустите этот код на машине, которая не поддерживает SSE2 или popcnt, вы должны выполнить итерацию по массивам и подсчитать различия с помощью подхода с развернутым циклом.

Удачи.

Изменить: Поскольку вы указали, что не знаете сборки, вот пример кода, чтобы проиллюстрировать мой ответ:

#include "stdafx.h"
#include <iostream>
#include "intrin.h"

inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
    __m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
    __m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );

    return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}

int _tmain( int argc, _TCHAR* argv[] )
{
    unsigned count = 0;
    char    arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
    char    arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };

    count = __popcnt( cmpArray16( arr1, arr2 ) );

    std::cout << "The number of equivalent bytes = " << count << std::endl;

    return 0;
}

Некоторые примечания. Эта функция использует инструкции SSE2 и инструкцию popcnt, представленную в процессоре Phenom (тот, который я использую). Я считаю, что у последних процессоров Intel с SSE4 также есть popcnt. Эта функция не проверяет поддержку команд с CPUID; функция undefined, если используется на процессоре, который не имеет SSE2 или popcnt (вы, вероятно, получите недопустимую инструкцию по коду). Этот код обнаружения представляет собой отдельный поток.

Я не приурочил этот код; причина, по которой я думаю, что это быстрее, потому что она сравнивает 16 байтов за раз, без ветвления. Вы должны изменить это, чтобы оно соответствовало вашей среде, и настало время убедиться, что оно работает для вас. Я написал и протестировал это на VS2008 SP1.

SSE предпочитает данные, которые выровнены по естественной 16-байтовой границе; если вы можете гарантировать, что тогда вам нужно получить дополнительные улучшения скорости, и вы можете изменить команды _mm_loadu_si128 на _mm_load_si128, что требует выравнивания.

Ответ 2

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

В приведенном ниже коде демонстрируется использование 4-байтных целых чисел, но если вы работаете в архитектуре SIMD (любой современный чип Intel или AMD), вы можете сравнить оба массива в одной инструкции, прежде чем возвращаться к циклу с целым числом. Большинство компиляторов в наши дни имеют встроенную поддержку 128-битных типов, поэтому НЕ требуется ASM.

(Обратите внимание, что для сравнения SIMD ваши массивы должны быть выровнены по 16 байт, а некоторые процессоры (например, MIPS) потребуют, чтобы массивы были выровнены по 4 байта для сравнения на основе.

например.

int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];

int same = 0;

for (int i = 0; i < 4; i++)
{
  // test as an int
  if (array1[i] == array2[i])
  {
    same += 4;
  }
  else
  {
    // test individual bytes
    char* bytes1 = (char*)(array1+i);
    char* bytes2 = (char*)(array2+i);

    for (int j = 0; j < 4; j++)
    {
      same += (bytes1[j] == bytes2[j];
    }
  }
}

Я не помню, что именно поддерживает MSVC-компилятор для SIMD, но вы можете сделать что-то вроде:

// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];

// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
    same = 16;
}
else
{
    // do int/byte testing
}

Ответ 3

Если у вас есть возможность управлять расположением массивов, например, поместив один сразу после другого в память, это может привести к их загрузке в кэш CPU при первом доступе.

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

Вы можете прочитать о иерархии и кеше памяти в Компьютерная архитектура Henessy и Patterson: количественный подход

Ответ 4

Если вам нужен абсолютный минимальный след, я бы пошел с кодом сборки. Я не делал этого некоторое время, но я готов поспорить, что MMX (или, скорее всего, SSE2/3) имеет инструкции, которые могут позволить вам сделать именно это в очень немногих инструкциях.

Ответ 5

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

Если два 32-битных значения не то же самое, тогда вам придется тестировать их отдельно (И из верхних и нижних 16-битных значений).

Код будет более сложным, но должен быть быстрее.

Если вы ориентируетесь на 64-битную систему, вы можете сделать тот же трюк с 64-битным ints, и если вы действительно хотите нажать предел, посмотрите на то, чтобы перейти на ассемблер и использовать различные векторные инструкции, которые позволят вам работать с 128 бит сразу.

Ответ 6

Магические параметры компилятора сильно изменят время. В частности, создание его генерации SSE-векторизации, вероятно, приведет к огромному ускорению.

Ответ 7

Должно ли это быть независимым от платформы, или этот код всегда будет работать на одном и том же процессоре? Если вы ограничиваете себя современными процессорами x86, вы можете использовать MMX инструкции, которые должны позволить вам работать с массивом 8 байтов за один такт. AFAIK, gcc позволяет встраивать сборку в ваш код C, а компилятор Intel (icc) поддерживает встроенные функции, которые являются оболочками, которые позволяют вам напрямую называть конкретные инструкции по сборке. Для этого также могут быть полезны другие наборы команд SIMD, такие как SSE.

Ответ 8

Есть ли связь между значениями в массивах? Являются ли некоторые байты более вероятными, чем другие? Может ли быть некоторый внутренний порядок в значениях? Тогда вы можете оптимизировать для наиболее вероятного случая.

Ответ 9

Если вы объясните, что представляют фактические данные, тогда может быть совершенно другой способ представления данных в памяти, которые бы не сравнивали этот тип грубой силы. Позаботьтесь о том, какие данные фактически представляют?

Ответ 10

Это быстрее, чем одно утверждение?

matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;

Ответ 11

Если запись в 16 раз быстрее, чем простой цикл, то ваш компилятор либо засасывает, либо у вас нет оптимизации.

Короткий ответ: нет более быстрого способа, если вы не выполняете векторные операции с параллельным оборудованием.

Ответ 12

Попробуйте использовать указатели вместо массивов:

p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.

Конечно, вы должны измерить это против других подходов, чтобы увидеть, что быстрее.

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

Ответ 13

Можно ли каким-либо образом изменить способ хранения массивов? Сравнение 1 байта за один раз чрезвычайно медленное, учитывая, что вы, вероятно, используете 32-битный компилятор. Вместо этого, если вы сохранили 16 байтов в 4 целых (32-разрядных) или 2 длинных (64-разрядных), вам нужно было бы выполнить соответственно 4 или 2 сравнения.

Вопрос о том, сколько стоит хранить данные как 4-целые или 2-длинные массивы, задается вопросом. Как часто вам нужно получить доступ к данным и т.д.

Ответ 14

Всегда хорошая старая инструкция x86 REPNE CMPS.

Ответ 15

Одна дополнительная возможная оптимизация: если вы ожидаете, что в большинстве случаев массивы идентичны, то может быть немного быстрее сделать memcmp() в качестве первого шага, установив "16" в качестве ответа, если тест возвращает true, Если курс, если вы не ожидаете, что массивы будут одинаковыми очень часто, это только замедлит работу.