Самый быстрый способ проверить массовые данные, если null в C?

Question

У меня есть масса данных, возможно 4 МБ. Теперь хочу, чтобы проверить, если все биты в нем равны 0.

Например: Вот данные:

void* data = malloc(4*1024*1024); 
memset(data, 0, 4*1024*1024); 

Проверьте, если все биты в нем 0. Вот мое решение, которое не достаточно быстро:

int dataisnull(char* data, int length) 
{ 
    int i = 0; 
    while(i<length){ 
     if (data[i]) return 0; 
     i++; 
    } 
    return 1; 
} 

Этот код может иметь некоторые особенности для улучшения производительности. Например, в 32/64 бит машине проверка 4/8 байт за раз может быть быстрее.

Так что я задаюсь вопросом, что является самым быстрым способом сделать это?

Answer 1

Вы можете обрабатывать несколько байт в то время, и раскатать цикл:

int dataisnull(const void *data, size_t length) { 
    /* assuming data was returned by malloc, thus is properly aligned */ 
    size_t i = 0, n = length/sizeof(size_t); 
    const size_t *pw = data; 
    const unsigned char *pb = data; 
    size_t val; 
#define UNROLL_FACTOR 8 
#if UNROLL_FACTOR == 8 
    size_t n1 = n - n % UNROLL_FACTOR; 
    for (; i < n1; i += UNROLL_FACTOR) { 
     val = pw[i + 0] | pw[i + 1] | pw[i + 2] | pw[i + 3] | 
       pw[i + 4] | pw[i + 5] | pw[i + 6] | pw[i + 7]; 
     if (val) 
      return 0; 
    } 
#endif 
    val = 0; 
    for (; i < n; i++) { 
     val |= pw[i]; 
    } 
    for (i = n * sizeof(size_t); i < length; i++) { 
     val |= pb[i]; 
    } 
    return val == 0; 
} 

В зависимости от вашей конкретной проблемы, это может быть более эффективным для обнаружения не нулевые значения рано или поздно:

• Если самый нулевой случай является наиболее распространенным, вы должны вычислить кумуляцию всех битов в аккумулятор val и протестировать только в конце.
• Если все нулевые случаи встречаются редко, вы должны чаще проверять ненулевые значения.

Развернутая версия выше представляет собой компромисс, который проверяет ненулевые значения каждые 64 или 128 байтов в зависимости от размера size_t.

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

Обратите внимание, что код не проверяет надлежащее выравнивание для data указателя:

• это не может быть сделано переносимо.
• предполагает, что данные были распределены через malloc или аналогичные, поэтому правильно выровнены для любого типа.

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

Answer 2

Следующие проверки, если первый байт является тем, что вы хотите, и все последующие пары байтов одинаковы.

int check_bytes(const char * const data, size_t length, const char val) 
{ 
    if(length == 0) return 1; 
    if(*data != val) return 0; 
    return memcmp(data, data+1, length-1) ? 0 : 1; 
} 

int check_bytes64(const char * const data, size_t length, const char val) 
{ 
    const char * const aligned64_start = (char *)((((uintptr_t)data) + 63)/64 * 64); 
    const char * const aligned64_end = (char *)((((uintptr_t)data) + length)/64 * 64); 
    const size_t start_length = aligned64_start - data; 
    const size_t aligned64_length = aligned64_end - aligned64_start; 
    const size_t end_length = length - start_length - aligned64_length; 

    if (!check_bytes(data, start_length, val)) return 0; 
    if (!check_bytes(aligned64_end, end_length, val)) return 0; 

    return memcmp(aligned64_start, aligned64_start + 64, aligned64_length-64) ? 0 : 1; 
} 

Более сложный вариант этой функции, вероятно, следует передать кэш-строки выровнены указатели на memcmp, и вручную проверьте остальные блоки (ы), а не только первый байт.

Конечно, вам нужно будет профилировать на своем конкретном оборудовании, чтобы узнать, есть ли какое-либо преимущество в скорости этого метода против других.

Если кто-то сомневается, работает ли это, ideone.

Answer 3

Я как-то написал следующую функцию для своего собственного использования. Он предполагает, что данные для проверки являются кратными размеру постоянного блока и правильно выравниваются для буфера машинных слов. Если это не указано в вашем случае, нетрудно выполнить цикл для первого и последнего нескольких байтов в отдельности и только проверить объем с оптимизированной функцией. (Строго говоря, это неопределенное поведение, даже если массив правильно выровнен, но данные были написаны любым типом, который несовместим с unsigned long.Однако, я считаю, что вы можете получить довольно далеко от этого тщательного нарушения правил здесь.)

#include <assert.h> 
#include <stdbool.h> 
#include <stddef.h> 
#include <stdint.h> 

bool 
is_all_zero_bulk(const void *const p, const size_t n) 
{ 
    typedef unsigned long word_type; 
    const size_t word_size = sizeof(word_type); 
    const size_t chunksize = 8; 
    assert(n % (chunksize * word_size) == 0); 
    assert((((uintptr_t) p) & 0x0f) == 0); 
    const word_type *const frst = (word_type *) p; 
    const word_type *const last = frst + n/word_size; 
    for (const word_type * iter = frst; iter != last; iter += chunksize) 
    { 
     word_type acc = 0; 
     // Trust the compiler to unroll this loop at its own discretion. 
     for (size_t j = 0; j < chunksize; ++j) 
     acc |= iter[j]; 
     if (acc != 0) 
     return false; 
    } 
    return true; 
} 

Функция сама по себе не очень умна. Основные идеи:

• Используйте большие машинные слова без знака для сравнения данных.
• Включить циклическое разворачивание путем разложения внутреннего цикла с постоянным количеством итераций.
• Уменьшите количество ветвей путем ORing слов в аккумуляторе и сравнивайте их только каждые несколько итераций против нуля.
• Это также должно облегчить компилятору генерировать векторизованный код с помощью команд SIMD, которые вы действительно хотите использовать для кода, подобного этому.

Дополнительные нестандартные настройки включают в себя аннотацию функции __attribute__ ((hot)) и использование __builtin_expect(acc != 0, false). Конечно, самое главное - включить оптимизацию вашего компилятора.