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

102

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

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

Винсент
источник
16
@BoPersson: ну, new это C ++ ...
Matteo Italia
@ Маттео - ну да. Не сильно повлиял на ответы (до сих пор :-).
Bo Persson
3
@BoPersson: Мне было неприятно говорить только о том, memsetкогда каким-то образом задействован C ++ ... :)
Matteo Italia
2
В современном компиляторе невозможно обыграть простой forцикл. Но, что удивительно, вы можете сделать намного хуже, если будете умны.
Дэвид Шварц
Используйте структуру и вставьте в нее массив. Создайте экземпляр, состоящий только из нулей. Используйте это, чтобы обнулить других, которые вы создаете. Это работает хорошо. Нет включает, нет функций, довольно быстро.
Xofo 05

Ответы:

170

memset(from <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(from <algorithm>):

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

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

Маттео Италия
источник
10
Что касается стандарта ISO C 1999 г., не было никакой гарантии, memsetчто целое число будет установлено равным 0; не было никакого конкретного утверждения, которое представляло бы все биты-ноль 0. Техническое исправление добавило такую ​​гарантию, которая включена в стандарт ISO 2011 года. Я считаю, что all-bit-zero является допустимым представлением 0для всех целочисленных типов во всех существующих реализациях C и C ++, поэтому комитет смог добавить это требование. (Нет аналогичной гарантии для типов с плавающей запятой или указателей.)
Кейт Томпсон
3
Добавление к комментарию @ KeithThompson: эта гарантия была добавлена ​​в 6.2.6.2/5 в виде обычного текста в TC2 (2004); однако, если битов заполнения нет, то 6.2.6.2/1 и / 2 уже гарантировали, что все биты-ноль были 0. (С битами заполнения существует возможность, что все-биты-ноль могут быть представлением ловушки). Но в любом случае TC должен подтверждать и заменять дефектный текст, поэтому с 2004 года мы должны действовать так, как если бы C99 всегда содержал этот текст.
MM
В C, если вы правильно разместили динамический массив , тогда не будет никакой разницы между двумя наборами памяти. Правильное динамическое размещение было бы int (*myarray)[N] = malloc(sizeof(*myarray));.
Lundin
@Lundin: конечно - если вы знаете во время компиляции, насколько велик N, но в подавляющем большинстве случаев, если вы использовали, mallocвы знали только во время выполнения.
Маттео Италия
@MatteoItalia У нас есть VLA с 1999 года.
Лундин
20

Этот вопрос, хотя и довольно старый, требует некоторых тестов, поскольку он требует не самого идиоматического способа, или способа, который может быть записан с наименьшим количеством строк, но самым быстрым способом. И глупо отвечать на этот вопрос без реального тестирования. Поэтому я сравнил четыре решения: 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.

Теперь о результатах. Я рассчитал производительность для массивов размера 100 int и long long, как статически, так и динамически распределенных, но за исключением 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 убивает gcc, типичные точечные оптимизации MSVC (он производит впечатляющее устранение мертвого кода на статических массивах, а затем имеет ужасную производительность для заполнения). Хотя моя реализация значительно быстрее, это может быть только потому, что она признает, что очистка битов имеет гораздо меньше накладных расходов, чем любая другая операция настройки.

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

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

Бенджамин
источник
4
Тест без кода и без упоминания версии компилятора и используемых опций? Хм ...
Марк Глисс
У меня уже были версии компилятора (они были немного скрыты), и я просто добавил применимые используемые параметры.
Бенджамин
недопустимый аргумент типа унарного '*' (имеет 'size_t {aka unsigned int}') |
Петр Василевич
Будучи настолько щедрым, что написал свой собственный оптимизированный метод обнуления - не могли бы вы сказать несколько слов о том, КАК он работает и ПОЧЕМУ он быстрее? код почти не требует пояснений.
Мотти Шнеор
1
@MottiShneor Выглядит сложнее, чем есть на самом деле. Регистр AVX имеет размер 32 байта. Поэтому он вычисляет, сколько значений aпомещается в регистр. После этого он перебирает все 32-байтовые блоки, которые должны быть полностью перезаписаны с помощью арифметики указателей ( (float *)((a)+x)). Два встроенных функций (начиная с _mm256) просто создать нулевой инициализированную регистр 32byte и хранить его к текущему указателю. Это первые 3 строки. Остальное просто обрабатывает все особые случаи, когда последний 32-байтовый блок не должен быть полностью перезаписан. Это быстрее за счет векторизации. - Надеюсь, это поможет.
wychmaster
11

Из memset() :

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

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

Алекс Рейнольдс
источник
2
sizeof будет работать, даже если размер массива неизвестен во время компиляции. (конечно, только когда это массив)
asaelr 05
2
@asaelr: в C ++ sizeofвсегда оценивается во время компиляции (и не может использоваться с VLA). В C99 это может быть выражение времени выполнения в случае VLA.
Ben Voigt
@BenVoigt Ну, вопрос как в, так cи в c++. Я прокомментировал ответ Алекса, в котором говорится: «Вы можете использовать sizeof (myarray), если размер myarray известен во время компиляции».
asaelr
2
@asaelr: А в C ++ он совершенно прав. В вашем комментарии ничего не говорится о C99 или VLA, поэтому я хотел его прояснить.
Ben Voigt
5

Ты можешь использовать 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);
Муравей
источник
1
Я бы пропустил ;после while(0), чтобы можно было позвонить ZERO(a,n);, +1 отличный ответ
0x90
@ 0x90: Да, вы совершенно правы. Вся суть do{}while(0)идиомы не требует ;определения макроса. Исправлена.
AnT
3

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

T myarray[100] = {0};

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

Бруно Соарес
источник
2
Вопрос гласит: «Не только для инициализации».
Ben Voigt
2

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

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

template<typename T, size_t SIZE> inline void zero(T(&arr)[SIZE]){
    memset(arr, 0, SIZE*sizeof(T));
}
Навин
источник
1
Это неверно, будет очищено SIZE байтов. 'memset (arr, 0, SIZE * sizeof (T));' было бы правильно.
Kornel Kisielewicz
@KornelKisielewicz D'oh! Я надеюсь, что никто не копировал эту функцию за последние 1,5 года :(
Navin
1
надеюсь, что нет, я прокомментировал, потому что Google привел меня сюда :)
Kornel Kisielewicz
1
Обратите внимание, что эта функция zeroтакже верна, например, T=char[10]как это может быть в случае, когда arrаргумент является многомерным массивом, например char arr[5][10].
mandrake
1
Да, я тестировал несколько случаев с gcc 4.7.3. Я считаю, что это было бы хорошо отметить для этого ответа, поскольку в противном случае вам потребовались бы специализации шаблонов для каждого количества измерений массива. Другие ответы также не обобщают, например ARRAY_SIZEмакрос, который дает неправильный размер при использовании в многомерном массиве, возможно, лучшее имя ARRAY_DIM<n>_SIZE.
mandrake
1

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

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. Также вы получите ошибку времени компиляции, если используете динамический массив с указанием размера.

Шитал Шах
источник
исходный вопрос
касается