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

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++ и сборку/внутреннюю структуру, загрузите два 16-байтовых массива в регистры xmm и выполните команду cmp.При этом генерируется битовая маска, представляющая истинное/ложное условие сравнения.Затем вы используете инструкцию movmsk для загрузки битового представления битовой маски в регистр x86;Затем это становится битовым полем, в котором вы можете посчитать все единицы, чтобы определить, сколько истинных значений у вас было.Аппаратная инструкция popcnt может быть быстрым способом подсчитать все единицы в регистре.

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

Например.

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

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

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

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

Answer 4

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

Answer 5

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

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

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

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

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

Answer 11

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

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

Answer 12

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

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

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

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

Answer 13

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

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

Answer 14

Всегда есть старая добрая инструкция REPNE CMPS для x86.

Answer 15

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