Влияние 2-битного массива битовых полей на производительность и эффективность кэша?
Я нуждаюсь в 2-битном массиве, меня совсем не волнует экономия памяти, но я озабочен тем, чтобы свести к минимуму потери кеша и максимизировать его эффективность. Использование массива bools будет использовать в 4 раза больше памяти, что означает, что для каждого используемого кеша данных в кеше будет 3, которые не используются. Технически, я могу получить в 3 раза лучшую согласованность кэша, если буду использовать битовые поля.
План состоит в том, чтобы реализовать его в виде массива байтов, разделенного на 4 равных битовых поля, и использовать функцию div, чтобы иметь возможность получить целое отношение и остаток, возможно, за один такт, и использовать их для доступа к нужному индексу и правильному битовый.
Массив, в котором я нуждаюсь, имеет длину около 10000 элементов, поэтому он будет содержать значительно более плотные упакованные данные, использование 2-х фактических битов позволит разместить весь массив в кэше L1, а при использовании байтового массива это будет невозможно.
Поэтому мой вопрос заключается в том, может ли кто-нибудь сказать мне, является ли это хорошей идеей в задаче, ориентированной на производительность, поэтому я знаю, стоит ли идти вперед и реализовывать 2-битный массив? И, конечно же, лучший способ узнать это профилирование, но любая информация заранее может быть полезна и будет оценена по достоинству.
Решение
С 10000 элементов на современном процессоре он должен хорошо вписываться в память в виде байтов (10 КБ), поэтому я бы не стал сильно беспокоиться об этом, если вы не хотите, чтобы он работал на каком-то очень маленьком микропроцессоре с кешем, который намного меньше чем типичные 16-32KB кэши L1, которые есть у современных процессоров.
Конечно, вы, возможно, захотите протестировать производительность с помощью различных решений, если считаете, что это важная часть вашего кода с точки зрения производительности [если судить по профилированию, которое вы уже выполнили до начала оптимизации, верно?] ,
Другие решения
Мне не ясно, что это приведет к производительности
усиление. Доступ к каждому полю потребует нескольких инструкций
((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 столько обращений к памяти. Упаковка сбез знака int`
вероятно, будет еще быстрее.