C++, Добавляющий 2 массива вместе быстро
Учитывая массивы:
int canvas[10][10];
int addon[10][10];
Где все значения колеблются от 0 - 100, каков самый быстрый путь в C++ для добавления тех двух массивов, таким образом, каждая ячейка в холсте равняется себе плюс соответствующее значение ячейки в дополнении?
IE, я хочу достигнуть чего-то как:
canvas += another;
Таким образом, если холст [0] [0] =3 и дополнение [0] [0] = 2 затем холст [0] [0] = 5
Скорость важна здесь, поскольку я пишу очень простую программу в грубую силу проблема типа ранца и будут десятки миллионов комбинаций.
И как небольшой дополнительный вопрос (благодарит, если можно помочь!), каков был бы самый быстрый способ проверить, превышает ли какое-либо из значений в холсте 100? Циклы являются медленными!
6 ответов
Вот реализация SSE4, которая должна работать довольно хорошо на Nehalem (Core i7):
#include <limits.h>
#include <emmintrin.h>
#include <smmintrin.h>
static inline int canvas_add(int canvas[10][10], int addon[10][10])
{
__m128i * cp = (__m128i *)&canvas[0][0];
const __m128i * ap = (__m128i *)&addon[0][0];
const __m128i vlimit = _mm_set1_epi32(100);
__m128i vmax = _mm_set1_epi32(INT_MIN);
__m128i vcmp;
int cmp;
int i;
for (i = 0; i < 10 * 10; i += 4)
{
__m128i vc = _mm_loadu_si128(cp);
__m128i va = _mm_loadu_si128(ap);
vc = _mm_add_epi32(vc, va);
vmax = _mm_max_epi32(vmax, vc); // SSE4 *
_mm_storeu_si128(cp, vc);
cp++;
ap++;
}
vcmp = _mm_cmpgt_epi32(vmax, vlimit); // SSE4 *
cmp = _mm_testz_si128(vcmp, vcmp); // SSE4 *
return cmp == 0;
}
Компиляция с помощью gcc -msse4.1 ... или эквивалент для вашей конкретной среды разработки.
Для более старых CPU без SSE4 (и с гораздо более дорогими смещенными загрузками/сохранениями) вам нужно (a) использовать подходящую комбинацию SSE2/SSE3 intrinsics для замены операций SSE4 (отмеченных * выше) и в идеале (b) убедиться, что ваши данные выровнены по 16 байтам и использовать выровненные операции. байт и использовать выровненные загрузки/сохранения (_mm_load_si128/_mm_store_si128) вместо _mm_loadu_si128/_mm_storeu_si128.
Вы не можете сделать ничего быстрее циклов на C++. Вам нужно будет использовать некоторые специфические для платформы векторные инструкции. То есть, вам придется спуститься на уровень языка ассемблера. Однако есть некоторые библиотеки C++, которые пытаются сделать это за вас, так что вы можете писать на высоком уровне, а библиотека позаботится о выполнении низкоуровневой SIMD работы, которая подходит для любой архитектуры, на которую вы ориентируетесь с помощью вашего компилятора.
MacSTL - это библиотека, на которую вы, возможно, захотите взглянуть. Изначально это была библиотека для Macintosh, но теперь она кроссплатформенная. Смотрите их домашнюю страницу для получения дополнительной информации.
Две части: во-первых, рассмотрите ваш двумерный массив [10] [10] как единый массив [100]. Правила компоновки C ++ должны позволять это. Во-вторых, проверьте свой компилятор на наличие встроенных функций, реализующих некоторую форму инструкций SIMD , таких как Intel SSE. Например Microsoft предоставляет набор . Я считаю, что в SSE есть некоторые инструкции по проверке максимального значения и даже по максимальному, если хотите.
Лучшее, что вы собираетесь сделать в стандартном C или C ++, - это преобразовать его в одномерный массив из 100 чисел и сложить их в цикле. (Одиночные индексы будут использовать немного меньше обработки, чем двойные, если компилятор не сможет их оптимизировать. Единственный способ узнать, какой эффект есть, если он есть, - это проверить.)
Конечно, можно создать класс, в который добавлением будет одна простая инструкция C ++ ( canvas + = addon; ), но это ничего не ускорит. Все, что могло бы произойти, - это то, что простая инструкция C ++ расширилась бы до цикла выше.
Чтобы ускорить это, вам нужно будет перейти на обработку более низкого уровня. На многих современных процессорах есть дополнительные инструкции для выполнения такой обработки, которые вы могли бы использовать. Вы могли бы запустить что-то подобное на графическом процессоре, используя что-то вроде Cuda . Вы можете попробовать сделать операцию параллельной и работать на нескольких ядрах, но в таком небольшом случае вам нужно знать, как кеширование работает на вашем процессоре.
Альтернативой является улучшение вашего алгоритма (для задачи типа рюкзака вы можете каким-то образом использовать динамическое программирование - без дополнительной информации от вас мы не можем вам сказать), или принять спектакль.Десятки миллионов операций с массивом 10 на 10 превращаются в сотни миллиардов операций с числами, и это уже не так страшно, как раньше. Конечно, я не знаю вашего сценария использования или требований к производительности.
Вот альтернатива.
Если вы на 100% уверены, что все ваши значения находятся между 0 и 100, вы можете изменить тип с int на uint8_t. Тогда вы могли бы сложить сразу 4 элемента вместе, используя uint32_t, не беспокоясь о переполнении.
То есть ...
uint8_t array1[10][10];
uint8_t array2[10][10];
uint8_t dest[10][10];
uint32_t *pArr1 = (uint32_t *) &array1[0][0];
uint32_t *pArr2 = (uint32_t *) &array2[0][0];
uint32_t *pDest = (uint32_t *) &dest[0][0];
int i;
for (i = 0; i < sizeof (dest) / sizeof (uint32_t); i++) {
pDest[i] = pArr1[i] + pArr2[i];
}
Возможно, это не самый элегантный вариант, но он может помочь вам избежать перехода к коду, специфичному для конкретной архитектуры. Кроме того, если вы сделаете это, я бы настоятельно рекомендовал вам прокомментировать, что вы делаете и почему.
Вам следует попробовать CUDA. Такая проблема прямо на улице CUDA. Порекомендуйте книгу Программирование массивно-параллельных процессоров .
Однако для этого требуется оборудование с поддержкой CUDA, а CUDA требует некоторых усилий для настройки в вашей среде разработки, поэтому все будет зависеть от того, насколько это важно на самом деле!
Удачи!