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

Question

У меня есть 2 массива из 16 элементов (символов), которые мне нужно «сравнить» и посмотреть, сколько элементов равно между этими двумя.

Эта подпрограмма будет использоваться миллионы раз (обычный запуск - около 60 или 70 миллионов раз), поэтому мне нужно, чтобы она была максимально быстрой. Я работаю на C ++ (C ++ Builder 2007, для записи)

Прямо сейчас у меня есть простое:

matches += array1[0] == array2[0];

повторяется 16 раз (так как профилирование кажется на 30% быстрее, чем при выполнении цикла for)

Есть ли другой способ, который мог бы работать быстрее?

Некоторые данные об окружающей среде и сами данные:

• Я использую C ++ Builder, который не учитывает оптимизацию скорости. В конце концов я попробую с другим компилятором, но сейчас я застрял с этим.
• Данные будут отличаться в большинстве случаев. 100% равных данных обычно очень и очень редко (возможно, менее 1%)

Answer 1

ОБНОВЛЕНИЕ: Этот ответ был изменен, чтобы мои комментарии соответствовали приведенному ниже исходному коду.

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

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

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

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

Удачи

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

#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; функция не определена, если используется на процессоре, который не имеет SSE2 или popcnt (вы, вероятно, получите недопустимую инструкцию для кода операции). Этот код обнаружения является отдельным потоком.

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

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

Answer 2

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

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

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

1007 * Е.Г. *

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
}

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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