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

Ответ 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 или аналогичные, поэтому правильно выровнены для любого типа.

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

Ответ 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.

Ответ 3

Я однажды написал следующую функцию для моего собственного использования. Он предполагает, что данные для проверки являются кратными размеру постоянного блока и правильно выравниваются для буфера машинных слов. Если это не указано в вашем случае, нетрудно выполнить цикл для первого и последнего нескольких байтов в отдельности и только проверить объем с оптимизированной функцией. (Строго говоря, это поведение undefined, даже если массив правильно выровнен, но данные были написаны любым типом, который несовместим с 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). Конечно, самое главное - включить оптимизацию компилятора.