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

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

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

Массив, который мне нужен, имеет длину около 10000 элементов, поэтому он обеспечит значительно более плотную упаковку данных, использование 2 фактических битов позволит разместить весь массив в кеше L1, а при использовании массива байтов это будет невозможно.

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


c++ caching performance bit-fields memory-efficient
person dtech    schedule 20.01.2013    source источник
comment
Какую информацию вы ищете? Кажется, вы уже знаете, чего хотите, и профилирование поможет вам это получить.   -  person Joseph Mansfield    schedule 20.01.2013
comment
@sftrabbit - известные проблемы, потенциальные ловушки, основные идеи о том, как иметь в 4 раза большую плотность данных в кеше L1 будет играть против дополнительных затрат на такую ​​структуру данных.   -  person dtech    schedule 20.01.2013
comment
Да, вполне вероятно, что ваш код будет работать быстрее с упакованными битами. Поскольку они в любом случае побитовые, вероятно, будет чище использовать побитовые операторы (&, |) вместо деления и остатка для упаковки и распаковки.   -  person Jerry Coffin    schedule 20.01.2013
comment
Избегайте функции div. Компиляторы могут видеть это, когда вы вычисляете как /, так и %. Я бы просто использовал битовые поля struct A4 { unsigned char x1:2; etc } и позволил компилятору заниматься оптимизацией.   -  person Marc Glisse    schedule 20.01.2013
comment
Избегайте однобайтовых обращений. Попробуйте использовать целые числа с 32 или даже 64 битами в качестве базового хранилища. Причина в том, что это снижает нагрузку на шину памяти, которая требует специальной обработки для доступа к отдельным байтам в большинстве современных систем. Кроме того, большинство процессоров имеют регистр с 32 или 64 битами, так что в любом случае это естественная единица вычислений.   -  person Ulrich Eckhardt    schedule 20.01.2013
comment
@MarcGlisse Я не знаю, так ли это до сих пор, но в последний раз, когда я смотрел (признаюсь, очень давно), компиляторы не особенно эффективно реализовывали битовые поля. И, конечно же, вы не можете создать массив битовых полей.   -  person James Kanze    schedule 20.01.2013
comment
@JerryCoffin Я сам думал об этом. Я бы почти наверняка написал это, используя битовые манипуляторы, но тогда я имею опыт работы с аппаратным обеспечением. Я не знаю, что другие люди подумают о читабельности. (Компилятор почти наверняка сгенерирует точно такой же код в любом случае.)   -  person James Kanze    schedule 20.01.2013
comment
Конечно, вы создаете массив из n/4 структур, каждая из которых содержит 4 битовых поля (возможно, замените 4 другими). Пока вы остаетесь в общем случае (независимо читаете битовые поля), я бы доверял компилятору генерировать правильный код (я также доверял бы ему распознавать шаблоны & | ›› как извлечения битового поля).   -  person Marc Glisse    schedule 20.01.2013
comment
Я согласен, что трудно ответить, не имея хотя бы представления о том, как будет использоваться массив.   -  person Marc Glisse    schedule 20.01.2013
comment
@JamesKanze: У меня может быть немного та же проблема, но мне определенно кажется, что x & 0x03 — это более ясный способ сказать два младших значащих бита x, чем использование деления и остатка, но я < я>предполагаю, что другие могут не согласиться (я полагаю, особенно те, у кого больше опыта в математике и меньше в аппаратном обеспечении).   -  person Jerry Coffin    schedule 20.01.2013

Ответы (2)


arrow_upward
5
arrow_downward

С 10000 элементов на современном процессоре он должен хорошо помещаться в памяти в виде байтов (10 КБ), поэтому я бы не стал слишком беспокоиться об этом, если только вы не хотите, чтобы это работало на каком-то очень маленьком микропроцессоре с кешем, который намного меньше чем типичные кэши L1 размером 16-32 КБ, которые есть у современных процессоров.

Конечно, вы вполне можете ПРОВЕРИТЬ производительность с помощью различных решений, если считаете, что это важная часть вашего кода с точки зрения производительности [судя по вашему профилированию, которое вы уже сделали, прежде чем начать оптимизацию, верно?] .

person Mats Petersson    schedule 20.01.2013
comment
Но какой кеш? Кэш L3 составляет часто (но не всегда) 10 КБ; L1 меньше, но быстрее. И, конечно же, с другой стороны, сколько стоит доступ к небайтовым границам. Для произвольного доступа это может стоить больше, чем потеря из-за выхода на один или два уровня в кэше. - person James Kanze; 20.01.2013
comment
На каком процессоре? На современных процессорах Intel/AMD кэш L2 составляет 512 КБ или 1 МБ, кэши L3 больше. Кэш L1 на процессорах AMD обычно составляет 64 + 64 КБ, на процессорах Intel он обычно составляет 32 + 32 КБ (например, Sandy/Ivy Bridge). Процессоры ARM15 имеют 32+32 КБ. - person Mats Petersson; 20.01.2013
comment
Большинство современных процессоров действительно имеют 32 КБ кеша данных, но он по-прежнему используется совместно с каждым запущенным процессом, поэтому я намерен максимально минимизировать занимаемую площадь. Массив используется в качестве таблицы поиска в анализаторе текста. - person dtech; 21.01.2013
comment
Ну конечно; естественно. Дело скорее в том, что наиболее эффективно: чтение одного байта или перетасовка битов. Перетасовка битов определенно более затратна с точки зрения процессора, так как вы в конечном итоге получаете по крайней мере команду и и сдвиг, чтобы выкопать правильные биты. Поэтому я подозреваю, что в достаточно хорошем случае это медленнее. Я уверен, что можно придумать сценарий, когда другой процесс работает и загрязняет только записи кеша, которые не являются вашей таблицей, но это вряд ли будет распространенным случаем - если другой процесс запустится, кеш исчезнет. - person Mats Petersson; 21.01.2013

arrow_upward
2
arrow_downward

Мне не ясно, что это приведет к приросту производительности. Для доступа к каждому полю потребуется несколько инструкций ((data[i / 4] >> 2 * (i % 4)) & 0x03), и многие современные процессоры имеют кэш-память L3, в которой хранится весь массив с одним байтом на запись. Трудно сказать, будут ли дополнительные затраты времени выполнения больше или меньше разницы в кэшировании; вам придется профиль, чтобы знать точно.

Если вы можете организовать свои алгоритмы для обработки байтов (или даже слов) за раз, стоимость доступа может быть намного меньше. Перебор всего массива, например:

for ( int i = 0; i < 10000; i += 4 ) {
    unsigned char w1 = data[ i / 4 ];
    for ( int j = 0; j < 4; ++ j ) {
        unsigned char w2 = w1 & 0x03;
        //  w2 is entry i + j...
        w1 >>= 2;
    }
}

может иметь существенное значение. Большинство компиляторов смогут хранить w1 и w2 в регистрах, что означает, что у вас будет только 1/4 доступа к памяти. Упаковка с unsigned int`, вероятно, была бы еще быстрее.

person James Kanze    schedule 20.01.2013
comment
Исправлена ​​небольшая опечатка: w1 >>= 4 должно быть w1 >>= 2. - person Mats Petersson; 20.01.2013
comment
Я бы также избегал i/4 и использовал i ›› 2 - таким образом, компилятор ОПРЕДЕЛЕННО будет использовать сдвиги, а не потенциально использовать другие механизмы для деления. - person Mats Petersson; 20.01.2013
comment
@Mats Petersson Но использование / позволяет компилятору выполнять деление наиболее эффективным способом, в то время как >> ограничивает его одним конкретным механизмом, который не всегда может быть быстрее. - person Mark B; 21.01.2013
comment
Как обсуждалось в другой ветке, если вы используете / компилятор ДОЛЖЕН следовать правилам деления отрицательных чисел [в этом случае он может понять, что i никогда не бывает отрицательным, но не всегда], и это означает, что одна инструкция с >>, делается около пяти инструкций на x86_64. Я пробовал. Сделай это сам, если не доверяешь мне. - person Mats Petersson; 21.01.2013
comment
Это все о манипуляциях с битами, поэтому я смею надеяться, что никто даже не подумает использовать здесь подписанный тип. В качестве примечания: для подписанных типов *4 быстрее, чем ‹‹2 (более неопределенное поведение при переполнении). - person Marc Glisse; 21.01.2013
comment
@MatsPetersson На самом деле производительность спорила бы, используя деление. Деление чаще используется в целом, и поэтому компиляторы оптимизируют его больше всего. Но на практике я не могу представить, чтобы компилятор когда-либо генерировал другой код. - person James Kanze; 21.01.2013
comment
@MarcGlisse В индексе нет манипуляций с битами, и нет уважительной причины использовать для него что-либо, кроме int. - person James Kanze; 21.01.2013
comment
Я позволю вам попробовать это на себе. Убедитесь, что компилятор не может просто заменить константу, и посмотрите на ассемблерный код. Конечно, и gcc, и clang (и их родственники C++) генерируют более сложный код для x / 2^y, чем для x >> y. - person Mats Petersson; 21.01.2013
comment
@MatsPetersson Не для беззнаковых значений в моем Linux-боксе. - person James Kanze; 21.01.2013
comment
Правильный. Но в приведенном выше коде используется int, тип со знаком. - person Mats Petersson; 21.01.2013
comment
@MatsPetersson Да, но вы никогда не захотите использовать сдвиг и маскировку для int из-за путаницы, которую это вызовет. - person James Kanze; 21.01.2013
comment
Является ли это одной из тех вещей типа юриста по языку, поскольку у меня есть МНОГИЕ примеры того, где я работаю как исходный код Linux... Кажется, там он работает довольно хорошо... Конечно, он не предназначен для работы на ЛЮБОМ оборудовании - он работает только на нескольких десятках различных моделей процессоров, и иногда в коде обнаруживаются ошибки для редкого и малоизвестного оборудования. - person Mats Petersson; 21.01.2013
comment
@MatsPetersson Ошибка возникает, когда кто-то другой должен поддерживать код. (И я, конечно, не стал бы брать исходный код Linux в качестве эталона надежного и поддерживаемого кода, по крайней мере, тех частей, которые я видел.) - person James Kanze; 21.01.2013