Как эффективно сравнить блок памяти с одним байтом?

Наиболее очевидным решением здесь, по-видимому, является просто перебрать размер структуры и сравнить ее побайтно.

Подход с выделением блока 0xFF, за которым следует memcmp, должен достичь того же, но с более высокой сложностью пространства.

Я не знаю стандартной функции для этого.

Я не думаю, что memcmp всегда правильный выбор (требуется вдвое большая пропускная способность памяти).

Я бы написал итерацию (даже очень наивную). Большинство компиляторов оптимизируют это очень хорошо (когда их просят). Таким образом, они, вероятно, разворачивают ваши циклы и могут сравнивать слова (даже если вы закодировали наивную итерацию байтов).

Вы можете написать специализированные варианты openmp (по крайней мере, для GCC). См. http://openmp.org/.

Если структура большая (например, десятки килобайт из-за стоимости копирования данных GPGPU ‹-> RAM) и если у вас есть много времени на разработку, рассмотрите, возможно, OpenCL (в частности, если у вас есть специализированное оборудование, поддерживающее его, например GPGPU). Это может никогда не стоить затрат (если вы не сделаете что-то, что не требует большой пропускной способности памяти, на ЦП, пока работает GPGPU)

Я бы закодировал наивный цикл и не стал бы заниматься оптимизацией вручную (если только бенчмаркинг кода, оптимизированного компилятором, не предполагает иного), потому что узким местом, вероятно, является пропускная способность памяти.

Логическое имя для такой функции будет memcchr - это для memchr, как strcspn для strspn.

И посмотрите здесь: результаты Google для memcchr показывают, что он был реализован под этим именем как часть ядра FreeBSD, и они предприняли некоторые попытки оптимизировать его, выйдя за рамки очевидного цикла 1 байт за раз.

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

Существует memchr(), который делает противоположное тому, о чем вы просите, - ищет первое вхождение байта в блоке памяти. afaik, нет стандартной функции для поиска байта, который не соответствует определенному. Цикл for звучит как путь. Может быть, перейти на 32/64 бита за раз, чтобы ускорить его.

-- Дополнительный бит не-ответа: memcmp будет медленнее, чем цикл for. Во-первых, вам нужно заполнить блок памяти того же размера, что и ваш исходный блок (эта часть, вероятно, займет столько же времени, сколько наивный цикл for). Затем вам нужно прочитать каждый блок памяти в регистры, чтобы сравнить их. Цикл for будет иметь значение в регистре и просто читать в одном блоке памяти для сравнения с неизменяемым регистром.

Я не знаю, сильно ли это улучшит производительность, но вы можете следовать этому алгоритму:

1. Сравните 1-й байт структуры с 1 байтом выделенной памяти 0xFF
2. Сравните 2-й байт структуры с 1-м байтом структуры
3. Сравните байты 3-4 структуры с байтами 1-2 структуры
4. Сравните байты 5-8 структуры с байтами 1-4 структуры

И продолжайте в том же духе до конца структуры. Если в какой-то момент утверждение ложно, вы знаете, что структура не вся 0xFF. Вам также нужно будет обрабатывать это по-другому, когда оставшаяся часть структуры меньше, чем первая проверенная часть, но это должно быть относительно просто.

В конце концов вы выделили 1 дополнительный байт памяти, и алгоритм равен O (log n) (небольшое улучшение по сравнению с тем, что я видел в ответах до сих пор).

edit: Как упоминал Эскраффорд ниже, если вы замените «байт» на «слово» в приведенной выше части, он может работать немного быстрее. Я не могу комментировать, какую скорость вы могли бы увеличить, но это увеличило бы дополнительную хранимую память (хотя и на крошечную величину на современных компьютерах).

Грязная переработка кода в Почему эта реализация strlen() работает ?. Сделал несколько быстрых тестов; никаких гарантий.

Это должно вернуть число 0xFF байтов; если он равен числу, с которого вы его начали, вы в сейфе. (Конечно, вы можете просто позволить ему возвращать 0 или 1.) Удалите printf, когда будете удовлетворены.

#define LONGPTR_MASK (sizeof(long) - 1)

int find_no_ff (const char *memory, size_t length)
{
    const char *p;
    const unsigned long *lp;
    size_t remain = length, to_do;

    printf ("non-aligned, start:\n");
    /* Test the first few bytes until we have an aligned p */
    for (p = memory; (uintptr_t)p & LONGPTR_MASK; p++)
    {
        printf ("testing %02X\n", *p & 0xff);
        if (*p != '\xFF')
            return (p - memory);
        remain--;
    }

    printf ("passed.\n");

    printf ("aligned:\n");
    to_do = remain/sizeof(long);
    remain -= (to_do*sizeof(long));

    /* Scan the rest of the string using word sized operation */
    for (lp = (const unsigned long *)p; to_do--; lp++)
    {
        printf ("testing %08lX\n", *lp);
        if (*lp +1)
            return p - memory;
    }
    printf ("passed.\n");

    p = (const char *)lp;

    printf ("non-aligned, end:\n");
    /* Test the last bytes until we have an aligned p */
    while (remain--)
    {
        printf ("testing %02X\n", *p & 0xff);
        if (*p != '\xFF')
            return (p - memory);
        p++;
    }
    printf ("passed.\n");
    return p - memory;
}

int main (void)
{
    char data[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,  0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };

    printf ("input size: %ld\n", sizeof(data));
    printf ("test result: %d\n", find_no_ff (data, sizeof(data)));

    return 0;
}

Мне нравится предложение Эрика, но его можно интересно упростить следующим образом (не проверено):

if((*pBytes == 0xFF) && (memcmp(pBytes, pBytes + 1, byteCount - 1) == 0)) // Байты byteCount в pBytes равны 0xFF.

Условие будет истинным, только если А) первый байт равен 0xFF и Б) каждый второй байт равен байту перед ним. Комбинация означает, что каждый байт равен 0xFF.