Как настроить повторяющиеся данные, чтобы большинство из них можно было оптимизировать?

Question

Мне нужно выполнить побитовое И на данных шириной 32 кбит.Одним из этих значений является фиксированная битовая маска.

Я выполняю это И 32 бита за раз.Упрощенно, мой алгоритм будет выглядеть примерно так:

_{(из этого примера я удаляю управление памятью, переменные области видимости и т. Д.)}

#include <stdint.h>

const uint32_t mask[1024] = {
            0b00110110100101100111001011000111,
            0b10001110100101111010010100100100,
            0b11101010010000110001101010010101,
            0b10001110100101111010010100100100,
            (...) // 1019 more lines!
            0b00110110100101100111001011000111};

uint32_t answer[1024] = {0};
uint32_t workingdata = 0;
uint16_t i = 0;

int main(void)
{
    for (i=0; i<1024; i++)
    {
        workingdata = getnextdatachunk();
        answer[i] = workingdata & mask[i];
    }

    do_something_with_answer();

    return 0;
}

Вотвещь: если вы посмотрите на пример битовой маски, то маска [1] == маска [3] и маска [0] == маска [1023].

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

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

Один метод, который я рассмотрел, похож на таблицу поиска, где мой массив содержит только один экземпляр каждого желаемого фрагмента битовой маски:

const uint32_t mask[20] = {
            0b00110110100101100111001011000111,
            0b10001110100101111010010100100100,
            (...) // only 17 more lines!
            0b11101010010000110001101010010101};

uint32_t answer[1024] = {0};
uint32_t workingdata = 0;
uint16_t i = 0;

int main(void)
{
    for (i=0; i<1024; i++)
    {
        workingdata = getnextdata();

        switch(i)
        {
            // the mask indexes are precalculated:

            case 0:
                answer[i] = workingdata & mask[5];
                break;
            case 1:
                answer[i] = workingdata & mask[2];
                break;
            case 2:
                answer[i] = workingdata & mask[2];
                break;
            case 3:
                answer[i] = workingdata & mask[0];
                break;
            case (...): // 1020 more cases!
                (...);
                break;
            default:
        }
    }

    do_something_with_answer();

    return 0;
}

Илис более компактным выражением switch:

switch(i)
{
    // the mask indexes are precalculated:

    case 0,3,4,5,18,35,67,(...),1019:
        answer[i] = workingdata & mask[0];
        break;
    case 1,15,16,55,89,91,(...),1004:
        answer[i] = workingdata & mask[1];
        break;
    case (...): // Only 18 more cases!
        (...);
        break;
    default:
}

Оба эти решения действительно неясно, что происходит, чего я действительно хотел бы избежать.

В идеале я хотел бы сохранитьисходная структура и оптимизатор gcc покончили со всеми ненужными данными. Как мне сохранить свой код хорошо написанным и при этом быть эффективным?

Answer 1

Давайте изобретем систему баллов и представим, что выборка данных из кэша L1 стоит 4 балла, выборка из кэша L2 - 8 баллов, а непредсказуемая ветвь - 12 баллов.Обратите внимание, что эти точки выбраны для грубого представления «циклов для среднего, но неизвестного процессора 80x86».

Исходный код с одной таблицей ввода 1024 будет иметь общую стоимость 4 балла за итерацию (при условии, что это часто делаетсядостаточно, чтобы производительность имела значение, и, следовательно, при условии, что данные используются достаточно часто, чтобы быть в кеше L1).

С оператором switch компилятор собирается (надеюсь - серия, если ветки - это кошмар производительности)преобразовать его в таблицу переходов и сделать что-то вроде goto table[i];, так что это, вероятно, считается как выборка из таблицы (4 балла), за которой следует одна непредсказуемая ветвь (12 баллов);или всего 16 точек за итерацию.

Обратите внимание, что для 64-битного кода таблица переходов, которую генерирует компилятор, будет 1024 записями, где каждая запись составляет 64 бита;и эта таблица будет в два раза больше таблицы для первого варианта (которая составляет 1024 записи, где каждая запись составляет 32 бита).Однако кэши данных L1 во многих ЦП имеют размер 64 КБ, поэтому таблица переходов 64 КБ означает все остальное, что входит в кэш данных L1 (исходные данные ANDed, результирующие данные «ответа», что-либо в стеке ЦП)заставляет (64 байта или 8 записей) части вашей таблицы переходов быть удаленными из кэша, чтобы освободить место.Это означает, что иногда вы будете платить за «L1 miss, L2 hit».Давайте предположим, что это происходит в 5% случаев, поэтому реальные затраты в конечном итоге составляют «(95 * (4 + 12) + 5 * (8 + 12)) / 100 = 16,2» балла за итерацию.

Учитывая, что вы ожидаете, что производительность будет выше для первого варианта («16,2 балла за итерацию» значительно больше, чем «4 балла за итерацию»), и что вы ожидаете, что размер исполняемого файла будет лучше для первого варианта (дажебез учета какого-либо кода для каждого case из switch таблица 32 КиБ - это половина размера таблицы 64 КиБ), и учитывая, что первый вариант имеет более простой (более обслуживаемый) код;Я не вижу ни одной причины, по которой вы захотите использовать второй вариант.

Чтобы оптимизировать этот код, я бы попробовал поработать над большими кусками.Для простого примера, можете ли вы сделать что-то вроде этого:

    uint64_t mask[512] = { ....

    uint64_t workingdata;
    uint64_t temp;

    for (i=0; i<512; i++)
    {
        workingdata = getnextdatachunk() << 32 | getnextdatachunk();
        temp = workingdata & mask[i];
        answer[i*2] = temp;
        answer[i*2+1] = temp >> 32;
    }

Если вы можете сделать что-то подобное, то это может (в лучшем случае) удвоить производительность;но если вы можете сделать «64 бита на итерацию для половины итераций», вы также сможете использовать встроенные функции SIMD для «128 бит на итерацию для четверти итераций» или «256 бит на итерацию для восьмой числаитераций ", и может быть в состоянии сделать это почти в 8 раз быстрее.

Конечно, шаг за этим заключается в том, чтобы буферизовать достаточное количество исходных данных, чтобы сделать использование нескольких потоков (нескольких процессоров) эффективным (например, чтобызатраты на синхронизацию могут быть эффективно амортизированы).При 4 параллельных процессорах, выполняющих по 256 бит на каждую итерацию, вы получите (теоретически лучший вариант) ускорение «в 32 раза быстрее, чем исходные 1024 итерации, 32 бит на итерацию с одной версией процессора».

Answer 2

Я лично считаю, что ваш подход действительно зависит от вашего варианта использования.У вас есть 2 различных режима:

• Если важна скорость работы, сохраняйте массив как целое в памяти (учитывая, что массив не станет слишком большим, чтобы портить кеш).
• Если кодРазмер важен, используйте методы, такие как то, что вы подумали или что предложили PSkocik .

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