Оптимизация арифметического кодера

Ответ 1

В соответствии с VTune мы часто получаем промахи в кэше. Любые предложения по исправлению этого?

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

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

void aricoder::encode( symbol* s )

Теперь существует следующий код, в котором программа обращается к элементам данных этого объекта:

s->scale
s->high_count
s->low_count

Из обоих отчетов VTune мы можем проверить, что все три доступа к памяти имеют разные сроки. Это указывает на то, что эти данные находятся в разных смещениях этого конкретного объекта. И, обращаясь к одному из них (s- > high_count), он выходит из кеша L1 и, следовательно, занимает больше времени, так как он должен передавать данные в кеш. В связи с этим s- > low_count выигрывает, как сейчас, в кеше L1. Из этих данных я могу думать о следующем:

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

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

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

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

Что такое "кэш-совместимый" ? код?

Как написать дружественную к кешу программу в С++?

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

Ответ 2

Это не полный ответ. Этот код является демонстрацией использования арифметики с фиксированной точкой для выполнения быстрого целочисленного деления. Широко используется в DSP и обработке сигналов. Обратите внимание, что код имеет смысл для оптимизации, только если изменения "масштаб" нечасты. Кроме того, в случае небольших значений "шкалы" код можно переписать для использования uint32_t в качестве промежуточного результата.

#include <stdio.h>
#include <stdint.h>

int main(int argc, char **argv)
{
   uint32_t scale;
   uint32_t scale_inv;
   uint32_t delta_plus_one;
   uint32_t val0, val1;
   uint64_t tmp;

   scale = 5;
   delta_plus_one = 44533;

   /* Place the line in 'scale' setter function */
   scale_inv = 0x80000000 / scale;

   /* Original expression */
   val0 = (delta_plus_one / scale);

   /* Division using multiplication uint64_t by uint32_t,
      using uint64_t as intermediate result */
   tmp = (uint64_t)(delta_plus_one) * scale_inv;
   /* shift right to produce result */
   val1 = tmp >> 31;

   printf("val0 = %u; val1 = %u\n", val0, val1);
   return 0;
}

Ответ 3

Чтобы начать CODER_LIMIT050, это глупое имя, сделанное особенно глупо благодаря сосуществованию CODER_LIMIT025 и CODER_LIMIT075. Кроме этого, вы, вероятно, не хотите использовать логику короткого замыкания, если в любом случае никаких побочных эффектов нет, поэтому второй оператор while может быть:

while ( ( clow >= CODER_LIMIT025 ) & ( chigh < CODER_LIMIT075 ) )

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

start:
switch ( ( clow >= CODER_LIMIT050 ) | (( chigh < CODER_LIMIT050 )<<1) )
{
default: break;

case 1:
    write_zero ( );
    write_nrbits_as_one ( );
    clow <<= 1;
    chigh = ( chigh << 1 ) | 1;
    goto start;

case 3: // think about this case, is this what you want?
case 2:
    write_one ( );
    clow &= CODER_LIMIT050 - 1;
    chigh &= CODER_LIMIT050 - 1;
    write_nrbits_as_zeros ( );
    clow <<= 1;
    chigh = ( chigh << 1 ) | 1;
    goto start;
}

Если вы хотите оптимизировать разделение на s->scale, спросите себя точно, как это переменная? Если есть только несколько возможных случаев, то шаблон его. Как только это константа времени компиляции, компилятор может попытаться либо найти бит сдвига, если это возможно, либо найти его мультипликативный обратный в поле Галуа GF (4294967296), если он имеет один.