Сброс массива C int до нуля: самый быстрый способ?

Question

Предполагая, что у нас есть T myarray[100] с T = int, unsigned int, long long int или unsigned long long int, что является самым быстрым способом сброса всего его содержимого в ноль (не только для инициализации, но и для сброса содержимогонесколько раз в моей программе)?Может быть, с memset?

Тот же вопрос для динамического массива, как T *myarray = new T[100].

Answer 1

memset (из <string.h>), вероятно, является самым быстрым стандартным способом, поскольку обычно это процедура, написанная непосредственно в сборке и оптимизированная вручную.

memset(myarray, 0, sizeof(myarray)); // for automatically-allocated arrays
memset(myarray, 0, N*sizeof(*myarray)); // for heap-allocated arrays, where N is the number of elements

---

Кстати, вC ++ идиоматическим способом было бы использовать std::fill (из <algorithm>):

std::fill(myarray, myarray+N, 0);

, который может автоматически оптимизироваться в memset;Я вполне уверен, что он будет работать так же быстро, как memset для int с, хотя он может работать немного хуже для небольших типов, если оптимизатор не достаточно умен.Тем не менее, если есть сомнения, профиль.

Answer 2

Этот вопрос, хотя и довольно старый, требует некоторых критериев, поскольку он требует не самого идиоматического способа или способа, который может быть записан в наименьшем количестве строк, но способа самый быстрый . И глупо отвечать на этот вопрос без какого-либо реального тестирования. Поэтому я сравнил четыре решения: memset против std :: fill и ZERO ответа AnT против решения, которое я сделал с использованием встроенных функций AVX.

Обратите внимание, что это решение не является универсальным, оно работает только с данными из 32 или 64 бит. Пожалуйста, прокомментируйте, если этот код делает что-то неправильное.

#include<immintrin.h>
#define intrin_ZERO(a,n){\
size_t x = 0;\
const size_t inc = 32 / sizeof(*(a));/*size of 256 bit register over size of variable*/\
for (;x < n-inc;x+=inc)\
    _mm256_storeu_ps((float *)((a)+x),_mm256_setzero_ps());\
if(4 == sizeof(*(a))){\
    switch(n-x){\
    case 3:\
        (a)[x] = 0;x++;\
    case 2:\
        _mm_storeu_ps((float *)((a)+x),_mm_setzero_ps());break;\
    case 1:\
        (a)[x] = 0;\
        break;\
    case 0:\
        break;\
    };\
}\
else if(8 == sizeof(*(a))){\
switch(n-x){\
    case 7:\
        (a)[x] = 0;x++;\
    case 6:\
        (a)[x] = 0;x++;\
    case 5:\
        (a)[x] = 0;x++;\
    case 4:\
        _mm_storeu_ps((float *)((a)+x),_mm_setzero_ps());break;\
    case 3:\
        (a)[x] = 0;x++;\
    case 2:\
        ((long long *)(a))[x] = 0;break;\
    case 1:\
        (a)[x] = 0;\
        break;\
    case 0:\
        break;\
};\
}\
}

Я не буду утверждать, что это самый быстрый метод, так как я не эксперт по оптимизации низкого уровня. Скорее, это пример правильной, зависящей от архитектуры реализации, которая работает быстрее, чем memset.

Теперь перейдем к результатам. Я рассчитал производительность для int размером 100 и для длинных длинных массивов, как статически, так и динамически распределенных, но за исключением msvc, который исключил мертвый код для статических массивов, результаты были чрезвычайно сопоставимы, поэтому я покажу только производительность динамического массива. Временные метки равны мс на 1 миллион итераций с использованием функции часов time.h с низкой точностью.

clang 3.8 (при использовании внешнего интерфейса clang-cl флаги оптимизации = / OX / arch: AVX / Oi / Ot)

int:
memset:      99
fill:        97
ZERO:        98
intrin_ZERO: 90

long long:
memset:      285
fill:        286
ZERO:        285
intrin_ZERO: 188

gcc 5.1.0 (флаги оптимизации: -O3 -march = native -mtune = native -mavx):

int:
memset:      268
fill:        268
ZERO:        268
intrin_ZERO: 91
long long:
memset:      402
fill:        399
ZERO:        400
intrin_ZERO: 185

msvc 2015 (флаги оптимизации: / OX / arch: AVX / Oi / Ot):

int
memset:      196
fill:        613
ZERO:        221
intrin_ZERO: 95
long long:
memset:      273
fill:        559
ZERO:        376
intrin_ZERO: 188

Здесь происходит много интересного: llvm killing gcc, типичные точечные оптимизации MSVC (он производит внушительное устранение мертвого кода на статических массивах, а затем имеет ужасную производительность для заполнения). Хотя моя реализация значительно быстрее, это может быть только потому, что она распознает, что очистка битов имеет гораздо меньше накладных расходов, чем любая другая операция установки.

Реализация Clang заслуживает большего внимания, поскольку она значительно быстрее. Некоторое дополнительное тестирование показывает, что его memset на самом деле специализирован для нуля - ненулевые memset для массива 400 байтов намного медленнее (~ 220 мс) и сравнимы с gcc. Тем не менее, ненулевое значение memset с массивом в 800 байтов не имеет разницы в скорости, поэтому, вероятно, в этом случае их memset имеет более низкую производительность, чем моя реализация - специализация предназначена только для небольших массивов, а обрезание составляет около 800 байтов. Также обратите внимание, что gcc 'fill' и 'ZERO' не оптимизируются под memset (глядя на сгенерированный код), gcc просто генерирует код с идентичными характеристиками производительности.

Вывод: memset на самом деле не оптимизирован для этой задачи, так как люди будут притворяться, что это так (иначе у gcc и msvc и memset llvm будет одинаковая производительность) Если производительность имеет значение, то memset не должен быть окончательным решением, особенно для этих неуклюжих массивов среднего размера, потому что он не специализирован для очистки битов, и он не оптимизирован вручную лучше, чем компилятор может сделать сам по себе.

Answer 3

С memset():

memset(myarray, 0, sizeof(myarray));

Вы можете использовать sizeof(myarray), если размер myarray известен во время компиляции. В противном случае, если вы используете массив динамического размера, например, полученный с помощью malloc или new, вам необходимо отслеживать длину.

Answer 4

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

В общем случае в C имеет смысл реализовать макрос

#define ZERO_ANY(T, a, n) do{\
   T *a_ = (a);\
   size_t n_ = (n);\
   for (; n_ > 0; --n_, ++a_)\
     *a_ = (T) { 0 };\
} while (0)

Это даст вам C ++ -подобную функциональность, которая позволит вам «обнулять» массив объектов любого типа, не прибегая к взломам, подобным memset. По сути, это аналог C шаблона функции C ++, за исключением того, что вы должны явно указать аргумент типа.

Кроме того, вы можете создать «шаблон» для неразрушенных массивов

#define ARRAY_SIZE(a) (sizeof (a) / sizeof *(a))
#define ZERO_ANY_A(T, a) ZERO_ANY(T, (a), ARRAY_SIZE(a))

В вашем примере это будет применяться как

int a[100];

ZERO_ANY(int, a, 100);
// or
ZERO_ANY_A(int, a);

Стоит также отметить, что специально для объектов скалярных типов можно реализовать независимый от типа макрос

#define ZERO(a, n) do{\
   size_t i_ = 0, n_ = (n);\
   for (; i_ < n_; ++i_)\
     (a)[i_] = 0;\
} while (0)

и

#define ZERO_A(a) ZERO((a), ARRAY_SIZE(a))

превращение приведенного выше примера в

 int a[100];

 ZERO(a, 100);
 // or
 ZERO_A(a);

Answer 5

Для статического объявления я думаю, что вы можете использовать:

T myarray[100] = {0};

Для динамического объявления я предлагаю тот же способ: memset

Answer 6

zero(myarray); - это все, что вам нужно в C ++.

Просто добавьте это в заголовок:

template<typename T, size_t SIZE> inline void zero(T(&arr)[SIZE]){
    memset(arr, 0, SIZE*sizeof(T));
}

Answer 7

Вот функция, которую я использую:

template<typename T>
static void setValue(T arr[], size_t length, const T& val)
{
    std::fill(arr, arr + length, val);
}

template<typename T, size_t N>
static void setValue(T (&arr)[N], const T& val)
{
    std::fill(arr, arr + N, val);
}

Вы можете назвать это так:

//fixed arrays
int a[10];
setValue(a, 0);

//dynamic arrays
int *d = new int[length];
setValue(d, length, 0);

Выше описан способ C ++ 11, чем использование memset.Также вы получаете ошибку времени компиляции, если вы используете динамический массив с указанием размера.