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

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

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

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

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

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

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

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

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

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

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

Это быстрее как один оператор?

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

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

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

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

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

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

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

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

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

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

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

Можно читать об иерархии памяти и кэше в Henessy & Patterson's Computer Architecture: Количественный Подход

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

Ниже кода демонстрирует с использованием 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
}

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