самое быстрое сравнение массива u_int64_t [8] в C / Stack Overflow
Какой самый быстрый метод, чтобы сравнить два u_int64[8] массивы в C / C ++?
Массив 1 находится внутри std::vector (~ 10k элементов) массив 2 находится внутри динамически распределенной структуры. (является memcmp() тут ложный позитив бесплатный?)
Моя (псевдо C) реализация:
typedef struct {
u_int64_t array[8];
}work_t;
/* alloc and fill array work_t* work = new (std::nothrow) work_t etc... */
for(u_int32_t i=0; i < some_std_vector.size(); i++) {
if((some_std_vector[i]->array[0] == work->array[0]) &&
(some_std_vector[i]->array[1] == work->array[1]) &&
(some_std_vector[i]->array[2] == work->array[2]) &&
(some_std_vector[i]->array[3] == work->array[3]) &&
(some_std_vector[i]->array[4] == work->array[4]) &&
(some_std_vector[i]->array[5] == work->array[5]) &&
(some_std_vector[i]->array[6] == work->array[6]) &&
(some_std_vector[i]->array[7] == work->array[7])) {
//...do some stuff...
}
}
Целевой платформой является Linux x86_64 gcc 4.9.2, цикл находится внутри pthread, tcmalloc используется, и код компилируется с -O2
Решение
Вот несколько предложений по улучшению скорости.
Используйте локальные переменные, если это возможно
Вместо использования указателей, например -> оператор, используйте локальные переменные или передавайте переменные в качестве ссылок. Компилятор может генерировать дополнительный код для загрузки указателя в регистр, а затем разыменовывать регистр для получения значения.
Используйте кэш данных процессора
Большинство современных процессоров имеют кеш данных. Если вы можете загрузить несколько переменных с данными, а затем сравнить, вы можете вызвать кэш данных процессора.
Кроме того, проектируйте свои данные, чтобы эффективно вписаться в строку кэша данных. Это означает, что элементы данных (включая массивы) должны быть рядом или очень близко друг к другу.
Блок сравнения
На самом низком уровне вы сравниваете много последовательных байтов. Как уже упоминалось, вы можете получить лучшую производительность, используя функцию сравнения памяти.
Еще одно предложение — помочь компилятору, загрузив значения в отдельные переменные, сравнивая значения:
for (/*...*/)
{
//...
uint64_t a1 = some_std_vector[i]->array[0];
uint64_t a2 = some_std_vector[i]->array[1];
uint64_t a3 = some_std_vector[i]->array[2];
uint64_t a4 = some_std_vector[i]->array[3];
uint64_t b1 = work->array[0];
uint64_t b2 = work->array[1];
uint64_t b3 = work->array[2];
uint64_t b4 = work->array[3];
if ((a1 == b1) && (a2 == b2) && (a3 == b3) && (a4 == b4))
{
//...
}
}
Концепция заключается в том, чтобы сначала загрузить переменные в несколько регистров, а затем сравнить регистры.
Язык ассемблера обзора & Профиль
При использовании всех техник, представленных в ответах, лучший способ — написать один код, просмотреть язык ассемблера и профиль. Не забудьте установить высокие уровни оптимизации для скорости.
Если в вашем процессе есть специальные инструкции, которые могут сделать это быстрее, вы хотите убедиться, что компилятор их использует или есть основания не использовать их.
Другие решения
Я полагаю, что единственный способ действительно ответить на этот вопрос — написать две подпрограммы, одну с помощью предоставленного вами цикла, а другую с помощью memcmp. Затем проанализируйте и посмотрите на дизассемблер, чтобы увидеть, какой из них выглядит наиболее эффективным. (Вы также можете быть одержимы и использовать профилировщик.)
Можно также написать пользовательскую подпрограмму в сборке, чтобы сравнить их напрямую (то есть пользовательскую версию memcmp, которая работает специально для сравнения именно того, на что вы смотрите) и сравнить ее вместе с двумя другими.
В любом случае, я согласен с другими, что, вероятно, все будет довольно близко (с современным компилятором); однако, если вы действительно хотите сохранить это, вам придется протестировать его с помощью профилировщика и / или иметь навыки, чтобы посмотреть на созданную сборку и узнать, какая из них будет быстрее на вид.
В зависимости от используемого вами устройства и используемого компилятора, вы можете попробовать некоторые «конкретные» проблемы. Например. в некоторых компиляторах существуют методики, позволяющие выполнять широкую загрузку из памяти и, как следствие, максимально быстро проводить множественные сравнения. Также есть способы вручную развернуть цикл, чтобы они выполнялись быстрее. Но это зависит от компилятора.
Вы всегда можете попробовать некоторые способы и проверить ассемблерный код, чтобы увидеть, какой путь самый быстрый.
Я провел несколько тестов и посмотрел на gcc memcmp, glibc memcmp и мой код выше. glibc-2.20 memcmp — это быстрый способ, потому что он использует оптимизацию для конкретной платформы (в моем случае).
gcc memcmp намного медленнее. (bug43052, скомпилировать с -fno-builtin-memcmp)