Заставить код на C работать быстрее

Question

Я написал фрагмент кода, который используется для подсчета частоты чисел от 0 до 255.

unsigned char arr[4096]; //aligned 64 bytes, filled with random characters

short counter[256]; //aligned 32 bytes

register int i;

for(i = 0; i < 4096; i++)
    ++counter[arr[i]];

Выполнение занимает много времени;произвольный доступ к массиву счетчиков очень дорогой.

У кого-нибудь есть идеи, которые я мог бы использовать, чтобы сделать последовательный доступ, или любой другой подход, который я мог бы использовать?

Answer 1

С чего вы взяли, что произвольный доступ к массиву счетчиков стоит дорого? Вы профилировали? Попробуйте Valgrind, у которого есть инструмент профилирования кеша, называемый «cachegrind». Профилирование также позволяет узнать, действительно ли код медленный или вы просто думаете, что он медленный, потому что он должен быть.

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

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

   Registers                      RAM
1.  <-- read data[i] ---------------
2.  <-- read histogram[data[i]] ----
3. increment
4.  --- write histogram[data[i]] -->
5.  <-- read data[i] ---------------
6.  <-- read histogram[data[i]] ----

Компилятору и процессору не разрешается переупорядочивать большинство приведенных здесь инструкций (кроме # 1 и # 5, что можно сделать заранее), поэтому вы будете ограничены в зависимости от того, что меньше: пропускная способность вашего Кэш L1 (где находится гистограмма) и пропускная способность вашей основной ОЗУ, каждая из которых умножена на некоторый неизвестный постоянный коэффициент (Примечание: компилятор может перемещать # 1/5 только в том случае, если он развернет цикл, но процессор все равно сможет его перемещать.)

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

Сноска:

Этот код:

register int i;
for(i = 0; i < 4096; i++)
    ++counter[arr[i]];

Создает ту же сборку, что и этот код:

int i;
for(i = 0; i < 4096; i++)
    counter[arr[i]]++;

Но этот код легче читать.

Answer 2

Ну, Ричард, конечно, прав.Это потому, что компилятор должен преобразовать массив в указатель, но это занимает некоторое время, что увеличивает время выполнения.Например, попробуйте это:

for(i = 0; i < 4096; i++)
     ++*(counter+*(arr+i));

Answer 3

код принимает данные размером 4k ... он добавляет каждые 3 последовательных байта и сохраняет результат во временном буфере размером 4k. Временный буфер используется для генерации гистограммы.

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

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

==11845== 
==11845== I   refs:      212,171
==11845== I1  misses:        842
==11845== LLi misses:        827
==11845== I1  miss rate:    0.39%
==11845== LLi miss rate:    0.38%
==11845== 
==11845== D   refs:       69,179  (56,158 rd   + 13,021 wr)
==11845== D1  misses:      2,905  ( 2,289 rd   +    616 wr)
==11845== LLd misses:      2,470  ( 1,895 rd   +    575 wr)
==11845== D1  miss rate:     4.1% (   4.0%     +    4.7%  )
==11845== LLd miss rate:     3.5% (   3.3%     +    4.4%  )
==11845== 
==11845== LL refs:         3,747  ( 3,131 rd   +    616 wr)
==11845== LL misses:       3,297  ( 2,722 rd   +    575 wr)
==11845== LL miss rate:      1.1% (   1.0%     +    4.4%  )

и полный вывод:

I1 cache:         65536 B, 64 B, 2-way associative
D1 cache:         65536 B, 64 B, 2-way associative
LL cache:         1048576 B, 64 B, 16-way associative
Command:          ./a.out
Data file:        cachegrind.out.11845
Events recorded:  Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Events shown:     Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Thresholds:       0.1 100 100 100 100 100 100 100 100
Include dirs:     
User annotated:   
Auto-annotation:  off

--------------------------------------------------------------------------------
     Ir I1mr ILmr     Dr  D1mr  DLmr     Dw D1mw DLmw 
--------------------------------------------------------------------------------
212,171  842  827 56,158 2,289 1,895 13,021  616  575  PROGRAM TOTALS

--------------------------------------------------------------------------------
    Ir I1mr ILmr     Dr  D1mr  DLmr     Dw D1mw DLmw  file:function
--------------------------------------------------------------------------------
97,335  651  642 26,648 1,295 1,030 10,883  517  479  ???:???
59,413   13   13 13,348   886   829     17    1    0  ???:_dl_addr
40,023    7    7 12,405    10     8    223   18   17  ???:core_get_signature
 5,123    2    2  1,277    64    19    256   64   64  ???:core_get_signature_parallel
 3,039   46   44    862     9     4    665    8    8  ???:vfprintf
 2,344   11   11    407     0     0    254    1    1  ???:_IO_file_xsputn
   887    7    7    234     0     0    134    1    0  ???:_IO_file_overflow
   720    9    7    250     5     2    150    0    0  ???:__printf_chk
   538    4    4    104     0     0    102    2    2  ???:__libc_memalign
   507    6    6    145     0     0    114    0    0  ???:_IO_do_write
   478    2    2     42     1     1      0    0    0  ???:strchrnul
   350    3    3     80     0     0     50    0    0  ???:_IO_file_write
   297    4    4     98     0     0     23    0    0  ???:_IO_default_xsputn

Answer 4

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

Единственное возможное улучшение, которое я вижу, - это ваше short.Я думаю, что размер таблицы здесь не будет проблемой, но рекламные акции и переполнение.Используйте тип, который обрабатывает это по умолчанию, а именно unsigned.

В любом случае, счетчики всегда должны быть unsigned (даже лучше size_t), это семантика кардинальности.В качестве дополнительного преимущества неподписанные типы не переполняются, а оборачивают окружность контролируемым образом.Для этого компилятору не нужно использовать дополнительную инструкцию.

Тогда арифметика в C выполняется с шириной, по крайней мере, равной int.Затем это должно быть приведено к короткому.

Answer 5

Более идиоматический:

// make sure you actually fill this with random chars
// if this is declared in a function, it _might_ have stack garbage
// if it's declared globally, it will be zeroed (which makes for a boring result)
unsigned char arr[4096]; 
// since you're counting bytes in an array, the array can't have more
// bytes than the current system memory width, so then size_t will never overflow
// for this usage
size_t counter[256];

for(size_t i = 0; i < sizeof(arr)/sizeof(*arr); ++i)
    ++counter[arr[i]];

Теперь ключ должен компилироваться с C99 и некоторыми серьезными флагами оптимизации:

cc mycode.c -O3 -std=c99

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

Answer 6

Попробуйте использовать указатель на arr вместо индексации.

unsigned char p = &arr;
for (i = 4096-1; 0 <= i; --i)
  ++counter[*p++];