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

Ответ 1

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

struct Foo {
    unsigned char a:2;
    unsigned char b:2;
    unsigned char c:2;
    unsigned char d:2;
}

Это размер 1 байт, и к ним можно получить доступ просто, т.е. foo.a, foo.b и т.д.

Сделав вашу структуру более плотно упакованной, это должно помочь в эффективности кеша.

Edit:

Подводя итог комментариям:

По-прежнему происходит битбирование с битовым полем, однако оно выполняется компилятором и, скорее всего, будет более эффективным, чем то, что вы пишете вручную (не говоря уже о том, что ваш исходный код более краткий и менее подвержен внедрению ошибок), И учитывая большое количество структур, с которыми вы будете иметь дело, сокращение промахов в кеше, полученных с помощью упакованной структуры, например, это, вероятно, восполнит накладные расходы на манипуляции с битами, которые налагает структура.

Ответ 2

Упакуйте их только в том случае, если пространство является соображением - например, массив из 1000 000 структур. В противном случае код, необходимый для переключения и маскировки, больше, чем экономия места для данных. Следовательно, у вас больше шансов пропустить кеш в I-кеше, чем в D-кеше.

Ответ 3

Нет окончательного ответа, и вы не дали достаточной информации, чтобы разрешить "правильный" выбор. Есть компромиссы.

Ваше утверждение о том, что ваша "основная цель - эффективность времени" недостаточна, поскольку вы не указали, является ли время ввода-вывода (например, для чтения данных из файла) более опасным, чем вычислительная эффективность (например, как долго какой-то набор вычислений берутся после того, как пользователь нажимает кнопку "Перейти" ).

Таким образом, было бы удобно записывать данные в виде одного char (чтобы сократить время на чтение или запись), но распакуйте его в массив из четырех int (поэтому последующие вычисления идут быстрее).

Кроме того, нет гарантии, что int - 32 бита (которые вы предположили в своем заявлении, что первая упаковка использует 128 бит). int может быть 16 бит.

Ответ 4

Foo имеет 4 значения, a, b, c, d, которые варьируются от 0 до 3. Обычно я не но иногда эти структуры...

Существует еще одна опция: поскольку значения 0... 3, вероятно, указывают на какое-то состояние, вы могли бы рассмотреть использование "flags"

enum{
  A_1 = 1<<0,
  A_2 = 1<<1,
  A_3 = A_1|A_2,
  B_1 = 1<<2,
  B_2 = 1<<3,
  B_3 = B_1|B_2, 
  C_1 = 1<<4,
  C_2 = 1<<5,
  C_3 = C_1|C_2,
  D_1 = 1<<6,
  D_2 = 1<<7,
  D_3 = D_1|D_2,
  //you could continue to  ... D7_3 for 32/64 bits if it makes sense
}

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

if ( a < 2 && b < 2 && c < 2 && d < 2) // .... (4 comparisons)
//vs.
if ( abcd & (A_2|B_2|C_2|D_2) !=0 ) //(bitop with constant and a 0-compare)

В зависимости от того, какие операции вы будете делать с данными, может иметь смысл использовать либо 4 или 8 наборов abcd, либо выровнять конец с 0s по мере необходимости. Это позволило до 32 сравнения заменить на бит и 0-сравнить. Например, если вы хотите установить "1 бит" для всех 8 наборов из 4 в 64-битной переменной, вы можете сделать uint64_t abcd8 = 0x5555555555555555ULL;, а затем установить все 2 бита, которые вы могли бы сделать abcd8 |= 0xAAAAAAAAAAAAAAAAULL;, чтобы теперь все значения 3

Приложение: При дальнейшем рассмотрении вы можете использовать объединение в качестве своего типа и либо объединить с полями char и @dbush (эти операции с флагом будут работать на unsigned char), либо использовать типы char для каждого a, b, c, d и объединить их с unsigned int. Это позволило бы как компактное представление, так и эффективные операции в зависимости от того, какой член профсоюза вы используете.

union Foo {
  char abcd; //Note: you can use flags and bitops on this too
  struct {
    unsigned char a:2;
    unsigned char b:2;
    unsigned char c:2;
    unsigned char d:2;
  };
};

Или даже расширен дальше

union Foo {
  uint64_t abcd8;  //Note: you can use flags and bitops on these too
  uint32_t abcd4[2];
  uint16_t abcd2[4];
  uint8_t  abcd[8];
  struct {
    unsigned char a:2;
    unsigned char b:2;
    unsigned char c:2;
    unsigned char d:2;
  } _[8];
};
union Foo myfoo = {0xFFFFFFFFFFFFFFFFULL};
//assert(myfoo._[0].a == 3 && myfoo.abcd[0] == 0xFF);

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

union Foo {
  uint32_t abcd;
  uint32_t dcba; //only here for endian purposes
  struct { //anonymous struct
    char a;
    char b;
    char c;
    char d;
  };
};

Вы можете экспериментировать и измерять с помощью разных типов соединений и алгоритмов, чтобы увидеть, какие части профсоюзов заслуживают сохранения, а затем отбросить те, которые не являются полезными. Вы можете обнаружить, что работа над несколькими типами char/short/int одновременно автоматически оптимизируется для некоторой комбинации инструкций AVX/simd, тогда как использование бит-полей не делает, если вы вручную их не разворачиваете... нет способа узнать, пока вы проверить и измерить их.

Ответ 5

Подбор вашего набора данных в кеше является критическим. Меньше всегда лучше, потому что hyperthreading конкурентно делится кэшами между ядрами между аппаратными потоками (на процессорах Intel). Комментарии к этому ответу включают некоторые номера для расходов на пропуски в кэше.

На x86 загрузка 8-битных значений со знаком или нулевым расширением в 32 или 64-битные регистры (movzxили movsx) буквально так же быстро, как обычный mov байта или 32bit dword. Хранение младшего байта 32-битного регистра также не имеет накладных расходов. (См. Таблицы Agner Fog таблицы инструкций и руководства по оптимизации C/asm).

Тем не менее x86-specific: временные файлы [u]int8_t тоже в порядке, но избегайте [u]int16_t временных рядов. (загрузка/сохранение от/до [u]int16_t в памяти прекрасна, но работа с 16-битными значениями в регистрах имеет большие штрафы от декодирования размера префикса операнда медленно на процессорах Intel.) 32-битные временные файлы будут быстрее, если вы хотите использовать их как индекс массива. (Использование 8-битных регистров не обнуляет высокие 24/56 бит, поэтому требуется дополнительная инструкция для нулевого или знакового расширения, для использования 8-битного регистра в качестве индекса массива или в выражении с более широким типом (например, добавлением его в int.)

Я не уверен, что ARM или другие архитектуры могут делать в отношении эффективного увеличения количества ноль/знаков из однобайтовых нагрузок или для однобайтовых магазинов.

Учитывая это, моя рекомендация для хранения, используйте int для временных. (Или long, но это немного увеличит размер кода на x86-64, поскольку для указания размера 64-разрядного операнда необходим префикс REX), например

int a_i = foo[i].a;
int b_i = foo[i].b;
...;
foo[i].a = a_i + b_i;

битовые

У упаковки в битовые поля будет больше накладных расходов, но они все равно могут стоить того. Тестирование постоянной позиции бита компиляции (или нескольких бит) в байтовом или 32/64-битном блоке памяти выполняется быстро. Если вам действительно нужно распаковать некоторые битовые поля в int и передать их вызову функции non-inline или что-то еще, это потребует нескольких дополнительных инструкций для смены и маскировки. Если это дает даже небольшое сокращение промахов в кеше, это может стоить того.

Тестирование, установка (до 1) или очистка (до 0) бит или группа битов могут быть эффективно выполнены с помощью OR или AND, но присваивание неизвестного логического значения битовому полю принимает дополнительные инструкции, чтобы объединить новые биты с битами для других полей. Это может значительно раздуть код, если вы очень часто назначаете переменную в поле бит. Поэтому использование int foo:6 и подобных вещей в ваших структурах, поскольку вы знаете, что foo не нуждается в двух верхних битах, вряд ли будет полезно. Если вы не сохраняете много бит по сравнению с помещением каждой вещи в свой собственный byte/short/int, то сокращение промахов в кэше не перевешивает дополнительные инструкции (которые могут скомбинировать пропуски I-cache/uop-cache, а также прямую дополнительную задержку и работу с инструкциями.)

Расширения инструкций x86 BMI1/BMI2 (Bit-Manipulation) сделают более эффективное копирование данных из реестра в некоторые биты назначения (без сбивания окружающих бит). BMI1: Haswell, Piledriver. BMI2: Haswell, экскаватор (неизданный). Обратите внимание, что, подобно SSE/AVX, это будет означать, что вам понадобятся версии ваших BMI, а также резервные версии без BMI для процессоров, которые не поддерживают эти инструкции. AFAIK, компиляторы не имеют возможности видеть шаблоны для этих инструкций и использовать их автоматически. Они могут использоваться только через intrinsics (или asm).

Dbush answer, упаковка в битполы, вероятно, является хорошим выбором, в зависимости от того, как вы используете свои поля. Ваш четвертый вариант (сложения четырех отдельных значений abcd в одну структуру), вероятно, является ошибкой, если вы не можете сделать что-то полезное с четырьмя последовательными значениями abcd (векторный стиль).

в общем случае, попробуйте оба способа

Для структуры данных, которую ваш код использует широко, имеет смысл задавать вопросы, чтобы вы могли переходить от одной реализации к другой и контрольной. Ответ Нир Фридман, с геттерами/сеттерами - это хороший способ. Однако, просто используя int temporaries и работая с полями, поскольку отдельные члены структуры должны работать нормально. Это до компилятора для генерации кода для проверки правильных битов байта для упакованных битовых полей.

подготовиться к SIMD, если это оправдано

Если у вас есть код, который проверяет только одно или пару полей каждой структуры, esp. зацикливание на последовательные значения структуры, тогда ответ на массив массивов, заданный cmaster, будет полезен. x86-векторные инструкции имеют один байт как наименьшую детализацию, поэтому структура массивов с каждым значением в отдельном байте позволит вам быстро сканировать первый элемент, где a == something, используя PCMPEQB / PTEST.

Ответ 6

Во-первых, точно определите, что вы подразумеваете под "наиболее эффективным". Лучшее использование памяти? Лучшая производительность?

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

Выберите тот, который лучше соответствует вашему первоначальному определению "наиболее эффективный".

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

Ответ 7

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

template <bool is_packed> class Foo;
using interface_int = char;

template <>
class Foo<true> {
    char m_a, m_b, m_c, m_d;
 public: 
    void setA(interface_int a) { m_a = a; }
    interface_int getA() { return m_a; }
    ...
}

template <>
class Foo<false> {
  char m_data;
 public:
    void setA(interface_int a) { // bit magic changes m_data; }
    interface_int getA() { // bit magic gets a from m_data; }
}

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

Ответ 8

Введите код int s

обрабатывать поля как int s.

blah.x во всем вашем коде, за исключением того, что объявление будет все, что вы будете делать. Интегральное продвижение позаботится о большинстве случаев.

Когда вы все закончите, у вас есть 3 эквивалентных файла include: include файл с использованием int s, один с помощью char и один с использованием бит-полей.

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

Ответ 9

Массивные массивы и ошибки памяти

2. вся программа состоит из большого массива миллиардов Foos;

Прежде всего, для # 2 вы можете оказаться сами или ваши пользователи (если другие запускают программное обеспечение), часто не могут выделить этот массив успешно, если он охватывает гигабайты. Общей ошибкой здесь является мысль о том, что ошибки из памяти означают "больше свободной памяти", когда они вместо этого часто означают, что ОС не может найти непрерывный набор неиспользуемых страниц, соответствующих требуемому размеру памяти. По этой причине люди часто путаются, когда они просят выделить один гигабайтный блок только для отказа, даже если у них нет 30 гигабайт свободной физической памяти, например. После того, как вы начнете распределять память в размерах, которые превышают, скажем, 1% от типичного объема доступной памяти, часто приходится думать об исключении одного гигантского массива для представления всего этого.

Итак, возможно, первое, что вам нужно сделать, это переосмыслить структуру данных. Вместо того, чтобы выделять один массив из миллиардов элементов, часто вы значительно уменьшаете вероятность столкновения с проблемами, выделяя меньшие куски (агрегированные меньшие массивы). Например, если ваш шаблон доступа носит исключительно последовательный характер, вы можете использовать развернутый список (связанные между собой массивы). Если необходим произвольный доступ, вы можете использовать нечто вроде массива указателей на массивы, каждый из которых составляет 4 килобайта. Для этого требуется немного больше работы, чтобы индексировать элемент, но с таким масштабом миллиардов элементов, это часто необходимо.

Шаблоны доступа

Одна из вещей, не указанных в вопросе, - это шаблоны доступа к памяти. Эта часть имеет решающее значение для руководства вашими решениями.

Например, структура данных проходит исключительно последовательно или требуется произвольный доступ? Все эти поля: a, b, c, d, нужны вместе все время или к ним можно получить доступ один или два или три за раз?

Попробуем охватить все возможности. В масштабе, о котором мы говорим, это:

struct Foo {
    int a1;
    int b1;
    int c1;
    int d1
};

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

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

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

struct Foo {
    char a1;
    char b1;
    char c1;
    char d1;
};

... и это еще больше:

// Each field packs 4 values with 2-bits each.
struct Foo {
    char a4; 
    char b4;
    char c4;
    char d4;
};

_{* Обратите внимание, что вы можете использовать бит-поля для вышеуказанного, но бит-поля, как правило, связаны с ними, в зависимости от используемого компилятора. Я часто старался избегать их из-за проблем с переносимостью, которые обычно описываются, хотя это может быть ненужным в вашем случае. Однако, поскольку мы приступаем к SoA и территориям с разбивкой по горячим/холодным полям ниже, мы достигнем точки, в которой битполы не могут быть использованы в любом случае.}

Этот код также фокусирует внимание на горизонтальной логике, которая может облегчить изучение некоторых дальнейших путей оптимизации (например: преобразование кода для использования SIMD), поскольку оно уже находится в миниатюрной форме SoA.

Данные "Потребление"

Особенно в таких масштабах, и тем более, когда доступ к памяти носит последовательный характер, он помогает мыслить в терминах "потребления" данных (как быстро машина может загружать данные, делать необходимую арифметику и хранить результаты). Простой ментальный образ, который я нахожу полезным, - представить компьютер как "большой рот". Это происходит быстрее, если мы кормим его достаточно большими ложками данных сразу, а не маленькими чайными ложками, а с более релевантными данными, плотно упакованными в смежную ложку.

Распределение горячих/холодных полей

В приведенном выше кодексе делается предположение, что все эти поля одинаково горячие (часто доступны) и доступны вместе. У вас могут быть холодные поля или поля, которые доступны только в критических кодовых путях попарно. Скажем, что вы редко получаете доступ к c и d, или что ваш код имеет один критический цикл, который обращается к a и b, а другой - к c и d. В этом случае может быть полезно разделить его на две структуры:

struct Foo1 {
    char a4; 
    char b4;
};
struct Foo2 {
    char c4;
    char d4;
};

Опять же, если мы "загружаем" данные компьютера, и наш код интересуется только полями a и b на данный момент, мы можем упаковать больше в ложки полей a и b, если у нас есть смежные блоки, содержащие только поля a и b, а не поля c и d. В таком случае поля c и d будут данными, которые компьютер не может переваривать в данный момент, но он будет смешаться в областях памяти между полями a и b. Если мы хотим, чтобы компьютер потреблял данные как можно быстрее, мы должны только кормить его соответствующими данными, представляющими интерес на данный момент, поэтому стоит расщеплять структуры в этих сценариях.

SIMD SoA для последовательного доступа

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

struct Foo1 {
    char* a4n;
    char* b4n;
};

... с уделением особого внимания выравниванию и заполнению (размер/выравнивание должно быть кратным 16 или 32 байтам для AVX или даже 64 для футуристического AVX-512), необходимых для использования более быстрых выровненных перемещений в регистры XMM/YMM ( и, возможно, с инструкциями AVX в будущем).

AoSoA для случайного/многопользовательского доступа

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

struct Foo1 {
    char a4x32[32];
    char b4x32[32];
};

... где мы теперь агрегируем эту структуру. Это делает так, чтобы поля a и b больше не расходились друг от друга, позволяя группам из 32 a и b полей вписываться в одну строку с байтом в 64 байта и быстро обращаться к ним. Мы также можем поместить 128 или 256 a или b элементов в регистр XMM/YMM.

Профилирование

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

Как анекдот, я часто делал лучшую работу (я не должен!) по оптимизации производственного кода, написанного людьми, обладающими гораздо более глубокими знаниями, чем я об компьютерной архитектуре (я работал с большим количеством людей, которые пришли из эпоху перфокарты и могут сразу понять код сборки), и их часто вызывали, чтобы оптимизировать свой код (что казалось очень странным). Это по одной простой причине: я "обманул" и использовал профилировщик (VTune). Мои сверстники часто этого не делали (у них была аллергия на это и они думали, что они понимают горячие точки так же хорошо, как и профилировщик, и видели, как профилирование было пустой тратой времени).

Конечно, идеальным является поиск тех, у кого есть опыт работы с компьютерной архитектурой и профилировщик в руке, но не имеющий того или другого, профилировщик может дать больший край. Оптимизация по-прежнему вознаграждает мышление производительности, которое зависит от наиболее эффективной приоритизации, и наиболее эффективной приоритизации является оптимизация тех частей, которые действительно имеют наибольшее значение. Профилировщик дает нам подробные разбивки о том, сколько времени тратится и где, наряду с полезными метриками, такими как промахи в кеше и неверные предсказания отрасли, которые даже самые продвинутые люди обычно не могут предсказать где-либо близко к столь же точно, как может выявить профайлер. Кроме того, профилирование часто является ключом к обнаружению того, как компьютерная архитектура работает более быстрыми темпами, преследуя горячие точки и исследуя, почему они существуют. Для меня профилирование было конечной точкой входа в лучшее понимание того, как компьютерная архитектура действительно работает, а не как я думал, что она работает. Только тогда писания кого-то, как опытные в этом отношении как Mysticial, стали все более и более ощущать.

Дизайн интерфейса

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

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

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

TL; DR

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

Ответ 10

Скажем, у вас есть шина памяти, которая немного старше и может доставлять 10 ГБ/с. Теперь возьмите процессор с частотой 2,5 ГГц, и вы увидите, что для насыщения шины памяти вам потребуется обработать не менее четырех байтов за цикл. Таким образом, когда вы используете определение

struct Foo {
    char a;
    char b;
    char c;
    char d;
}

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

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

struct Foo {
    size_t count;
    char* a;    //a[count]
    char* b;    //b[count]
    char* c;    //c[count]
    char* d;    //d[count]
}

Ответ 11

Вы указали общий и неоднозначный тег C/С++.

Предполагая С++, сделайте данные приватными и добавьте геттеры/сеттеры. Нет, это не приведет к поражению производительности - включение оптимизатора.

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

Для записи я ожидаю, что struct с битовыми полями в соответствии с @dbush, скорее всего, будет самым быстрым с учетом вашего описания.

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

Ответ 12

Возвращаясь к заданному вопросу:

используется в замкнутом цикле;

их значения читаются в миллиард раз/с, и это узкое место в программе;

вся программа состоит из большого массива миллиардов Foos;

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

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

Также возможно, поскольку это большой массив из миллиарда foos, что OP должен рассмотреть возможность использования OpenCL или OpenMP в качестве потенциальных решений, чтобы максимизировать использование доступных ресурсов на оборудовании во время выполнения. Это немного зависит от того, что вам нужно от данных, но это, вероятно, самый важный аспект этой проблемы - как использовать доступный parallelism.

Но нет единого правильного ответа на этот вопрос, ИМО.

Ответ 13

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

Некоторые процессоры имеют более одного эффективного размера. Многие процессоры ARM могут работать в режиме 8/32 бит. Это означает, что процессор оптимизирован для обработки 8-битных величин или 32-разрядных величин. Для такого процессора я рекомендую использовать 8-битные типы данных.

Ваш алгоритм имеет много общего с эффективностью. Если вы перемещаете данные или копируете данные, вы можете рассмотреть возможность перемещения данных по 32 битам за раз (4 8-битные величины). Идея здесь заключается в том, чтобы уменьшить количество выборок процессора.

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

Лучше всего, проверьте настройки оптимизации компилятора. Установите свой компилятор для самых высоких показателей производительности (скорости). Затем создайте списки ассемблера ваших функций. Просмотрите список, чтобы узнать, как сгенерированный код компилятора. Откорректируйте свой код, чтобы улучшить возможности оптимизации компилятора.

Ответ 14

Если вам нужна эффективность пространства, вам следует избегать struct вообще. Компилятор будет вставлять дополнения в ваше структурное представление, если необходимо, чтобы сделать его размер кратным его требованиям к выравниванию, который может составлять до 16 байт (но, скорее всего, это 4 или 8 байтов, и в конце концов это может быть как минимум 1 байт).

Если вы все равно используете struct, то использование зависит от вашей реализации. Если метод @dbush bitfield дает однобайтовые структуры, тогда это сложно превзойти. Если ваша реализация будет заполнять представление, по крайней мере, до четырех байтов, независимо от того, что это значит, то это, вероятно, тот, который нужно использовать:

struct Foo {
    char a;
    char b;
    char c;
    char d;
};

Или, наверное, я бы использовал этот вариант:

struct Foo {
    uint8_t a;
    uint8_t b;
    uint8_t c;
    uint8_t d;
};

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

Для обработки больших объемов данных эффективное использование кэша ЦП обеспечивает гораздо больший выигрыш, чем избежать нескольких целых операций. Если ваш шаблон использования данных по крайней мере несколько систематичен (например, если после доступа к одному элементу вашего прежнего структурного массива вы, скорее всего, получите доступ к ближайшему рядом), тогда вы, вероятно, получите повышение как эффективности, так и скорости пространства путем упаковки данных так сильно, как вы можете. В зависимости от реализации C (или если вы хотите избежать зависимостей от реализации) вам может потребоваться достичь этого по-другому - например, через массив целых чисел. Для вашего конкретного примера из четырех полей, для каждого из которых требуются два бита, я бы рассмотрел представление каждой "структуры" как uint8_t вместо всего, всего 1 байт.

Возможно, что-то вроде этого:

#include <stdint.h>

#define NUMBER_OF_FOOS 1000000000
#define A 0
#define B 2
#define C 4
#define D 6

#define SET_FOO_FIELD(foos, index, field, value) \
    ((foos)[index] = (((foos)[index] & ~(3 << (field))) | (((value) & 3) << (field))))
#define GET_FOO_FIELD(foos, index, field) (((foos)[index] >> (field)) & 3)

typedef uint8_t foo;

foo all_the_foos[NUMBER_OF_FOOS];

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

Ответ 15

Я сделал декомпрессию видео некоторое время. Самый быстрый способ сделать это примерно так:

short ABCD; //use a 16 bit data type for your example

и установите некоторые макросы. Может быть:

#define GETA ((ABCD >> 12) & 0x000F)
#define GETB ((ABCD >> 8) & 0x000F)
#define GETC ((ABCD >> 4) & 0x000F)
#define GETD (ABCD  & 0x000F)  // no need to shift D

На практике вам следует попытаться переместить 32-битные long или 64-битные длинные, потому что это собственный размер MOVE на большинстве современных процессоров.

Использование struct всегда будет создавать накладные расходы в вашем скомпилированном коде дополнительных инструкций из базового адреса вашей структуры в поле. Поэтому избегайте этого, если вы действительно хотите затянуть свою петлю.

Изменить: Вышеприведенный пример дает вам 4-битные значения. Если вам действительно нужны значения 0..3, вы можете сделать то же самое, что бы вытащить ваши 2-битные числа, поэтому, GETA может выглядеть так:

GETA ((ABCD >> 14) & 0x0003)

И если вы действительно перемещаете миллиарды вещей, и я не сомневаюсь в этом, просто заполните 32-битную переменную и сдвиньте и замаскируйте свой путь через нее.

Надеюсь, это поможет.