Как оптимизировать эту простую функцию, которая переводит входные биты в слова?

Question

Я написал функцию, которая считывает входной буфер байтов и создает выходной буфер слов, где каждое слово может быть либо 0x0081 для каждого бита ON входного буфера, либо 0x007F для каждого бита OFF.Длина входного буфера указана.У обоих массивов достаточно физического места.У меня также есть около 2 Кбайт свободной оперативной памяти, которую я могу использовать для поиска таблиц или около того.

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

void inline BitsToWords(int8    *pc_BufIn, 
                        int16   *pw_BufOut, 
                        int32   BufInLen)
{
 int32 i,j,z=0;

 for(i=0; i<BufInLen; i++)
 {
  for(j=0; j<8; j++, z++)
  {
   pw_BufOut[z] = 
                    ( ((pc_BufIn[i] >> (7-j))&0x01) == 1? 
                    0x0081: 0x007f );
  }
 }
}

Пожалуйста, не предлагайте какую-либо библиотечную, компиляторную или CPU / аппаратную оптимизацию, потому что это многоПроект платформы.

Answer 1

У меня также есть около 2 Кбайт свободной оперативной памяти, которую я могу использовать для таблиц поиска

Ваши таблицы поиска могут быть помещены в массив const во время компиляции, поэтому он может быть в ПЗУ- это дает вам место для простого 4KB стола?

Если вы можете позволить себе 4 КБ места в ПЗУ, единственной проблемой является построение таблицы в виде инициализированного массива в файле .c - но это нужно сделать только один раз, и вы можете написать скрипт для выполненияэто (что может помочь обеспечить его правильность, а также может помочь, если вы решите, что таблица должна измениться по какой-то причине в будущем).

Вам необходимо выполнить профилирование, чтобы обеспечить копирование из ПЗУ наМассив назначения на самом деле быстрее, чем вычисление того, что нужно ввести в пункт назначения - я не удивлюсь, если что-то вроде:

/* untested code - please forgive any bonehead errors */
void inline BitsToWords(int8    *pc_BufIn, 
                        int16   *pw_BufOut, 
                        int32   BufInLen)
{
    while (BufInLen--) {
        unsigned int tmp = *pc_BufIn++;

        *pw_BufOut++ = (tmp & 0x80) ? 0x0081 : 0x007f;
        *pw_BufOut++ = (tmp & 0x40) ? 0x0081 : 0x007f;
        *pw_BufOut++ = (tmp & 0x20) ? 0x0081 : 0x007f;
        *pw_BufOut++ = (tmp & 0x10) ? 0x0081 : 0x007f;
        *pw_BufOut++ = (tmp & 0x08) ? 0x0081 : 0x007f;
        *pw_BufOut++ = (tmp & 0x04) ? 0x0081 : 0x007f;
        *pw_BufOut++ = (tmp & 0x02) ? 0x0081 : 0x007f;
        *pw_BufOut++ = (tmp & 0x01) ? 0x0081 : 0x007f; 
    }
}

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

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

Answer 2

Я полагаю, вы не можете использовать пареллизм?

---

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

Если я правильно понимаю, каждый байт во входном массиве выдает 16 байтов в выходной.Таким образом, таблица поиска, которая дает 16-байтовый вывод для одного байтового ввода, должна занимать 4 КБ - это больше, чем вы должны сэкономить.

Вместо этого вы можете разделить каждый байт на две части по 4 бита, что уменьшитразмер запрашиваемой таблицы до 256 байт:

int16[0x0F][4] values = {...};
void inline BitsToWords(int8    *pc_BufIn, int16   *pw_BufOut, int32   BufInLen)
{  
  for(int32 i=0; i<BufInLen; ++i, BufOut+=8)
  {
    memcpy(pw_BufOut,values[pc_BufIn[i]&0x0F]);
    memcpy(pw_BufOut+4,values[(pc_BufIn[i]&0xF0)>>4]);
  }
}

Кроме того, если вы обнаружите, что издержки цикла чрезмерны, вы можете использовать Устройство Даффа .

Answer 3

Первая попытка:

void inline BitsToWords(int8    *pc_BufIn,  
                        int16   *pw_BufOut,  
                        int32   BufInLen) 
{ 
 int32 i,j=0;
 int8 tmp;
 int16 translate[2] = { 0x007f, 0x0081 };

 for(i=0; i<BufInLen; i++) 
 { 
  tmp = pc_BufIn[i];
  for(j=0x80; j!=0; j>>=1) 
  { 
   *pw_BufOut++ = translate[(tmp & j) != 0];
  } 
 } 
} 

Вторая попытка, бесстыдно воровать у Майкл Берр (который уже получил +1 от меня):

void inline BitsToWords(int8    *pc_BufIn,  
                        int16   *pw_BufOut,  
                        int32   BufInLen) 
{ 
    while (BufInLen--) { 
        int16 tmp = *pc_BufIn++; 

        *pw_BufOut++ = 0x007f + ((tmp >> 6) & 0x02); 
        *pw_BufOut++ = 0x007f + ((tmp >> 5) & 0x02); 
        *pw_BufOut++ = 0x007f + ((tmp >> 4) & 0x02); 
        *pw_BufOut++ = 0x007f + ((tmp >> 3) & 0x02); 
        *pw_BufOut++ = 0x007f + ((tmp >> 2) & 0x02); 
        *pw_BufOut++ = 0x007f + ((tmp >> 1) & 0x02); 
        *pw_BufOut++ = 0x007f + (tmp & 0x02); 
        *pw_BufOut++ = 0x007f + ((tmp << 1) & 0x02);  
    } 
} 

Answer 4

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

static int16 [] lookup = {
  0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 
  0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x0081, 
  0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x0081, 0x007f, 
  0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x007f, 0x0081, 0x0081,
  /* skip 251 entries */
  0x0081, 0x0081, 0x0081, 0x0081, 0x0081, 0x0081, 0x0081, 0x0081, 
};

void inline BitsToWords(int8 * input, int16 * output, int32 length) {
  while ( length-- ) {
    memcpy( output, lookup[ *input++ ], 16 );
    output += 8; 
  }
}

Проблема в том, что сама таблица поиска будет 4 КБ (256 * 16), что больше, чем у вас есть. Это можно обойти одним из двух способов. Самое простое и маленькое решение будет примерно таким:

static int16 [] lookup = {
  0x007f, 0x007f, 0x007f, 0x007f, 
  0x007f, 0x007f, 0x007f, 0x0081, 
  0x007f, 0x007f, 0x0081, 0x007f, 
  0x007f, 0x007f, 0x0081, 0x0081,
  /* skip 11 entries */
  0x0081, 0x0081, 0x0081, 0x0081, 
};

void inline BitsToWords(int8 * input, int16 * output, int32 length) {
  while ( length-- ) {
    int 8 c = *input++;
    memcpy( output, &lookup[ c &0x0f ], 8 );
    memcpy( output+4, &lookup[ c >> 4 ], 8 );
    output += 8; 
  }
}

Более сложным, но, возможно, более быстрым способом было бы использовать последовательность Де Брюина для кодирования всех возможных значений поиска. Это уменьшило бы таблицу поиска с 4 КБ до 512 + 14, но потребовало бы дополнительного уровня косвенности и другой индексной таблицы (256 байтов), в общей сложности 782 байта. Это приведет к удалению одного из вызовов memcpy (), а также сдвига и побитового вычисления, и за счет еще одного индекса. Вероятно, не обязательно в вашем случае, но все равно интересно.

Answer 5

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

void inline BitsToWords(int8  * restrict pc_BufIn, 
                        int16 * restrict pw_BufOut, 
                        int32            BufInLen)

Это позволит компилятору выполнять оптимизации, которые в противном случае были бы недопустимы.Обратите внимание, что ваш компилятор может использовать другое ключевое слово;Я думаю, что некоторые используют __restrict__ или могут иметь атрибут, специфичный для компилятора.Обратите внимание, что единственным требованием является то, что pc_bufIn и pw_bufOut не перекрываются.Это должно дать вам немедленное повышение производительности, так как компилятор не будет пытаться перечитывать pc_bufIn всякий раз, когда записывается pw_bufOut (сохраняя вам 7 чтений на каждые 8 ​​записей).

Если это ключевое словонедоступна, возможна альтернативная оптимизация:

{
 char* bufInEnd = pc_bufIn + BufInLen;
 While(pc_bufIn != bufInEnd) {
 {
  char tmp = *pc_bufIn++;
  for(int j=0; j<8; j++)
  {
   *pw_BufOut++ =  ( (tmp & (0x80 >> j) != 0)? 
                    0x0081: 0x007f );
  }
 }
}

Приведенное выше небольшое переписывание, на мой взгляд, легче выполнить, поскольку оно однозначно указывает путь, по которому идет процессор, но я надеюсь, что оптимизация очевидна: Storeзначение pc_bufIn[i] для временной локальной переменной вместо нажатия указателя на каждую итерацию внутреннего цикла.

Другая, менее очевидная оптимизация будет использовать все более распространенное векторное оборудование, доступное на большинстве процессоров (включая NEON от ARM).и Intel SSE) для получения результата 16 байтов за раз.Я бы порекомендовал изучить этот вариант.

Answer 6

Во-первых, вы делаете это для 8-сегментного дисплея, не так ли?

Возможно, вы захотите

#include <stdint.h>

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

void inline BitsToWords(int8    *pc_BufIn, 
                        int16   *pw_BufOut, 
                        int32   BufInLen)
{
  //int32 i,j,z=0;
  /* This is a place you might want to use a different type, but
   * I don't know for sure.  It depends on your processor, and I
   * didn't use these variables */

  int8 * end = pc_BufIn + BufInLen; /* So that you can do pointer math rather than
                                    * index. */
  while (end < pc_BufIn)
  {
    uint_fast8_t cur = *(pc_BufIn++);
    uint_fast8_t down = 8;

    do
    {
       *(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 ); /* When the bottom bit is set, add 2 */
       /* By doing this with addition we avoid a jump. */

       cur >>= 1; /* next smallest bit */
    } while (--down);
  }
}

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

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

*(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 );
cur >>= 1; /* next smallest bit */
*(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 );
cur >>= 1; /* next smallest bit */
*(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 );
cur >>= 1; /* next smallest bit */
*(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 );
cur >>= 1; /* next smallest bit */
*(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 );
cur >>= 1; /* next smallest bit */
*(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 );
cur >>= 1; /* next smallest bit */
*(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 );
cur >>= 1; /* next smallest bit */
*(pw_BufOut++) = 0x07f + ( (mask&cur)<< 1 );

Для внешнего цикла я изменил его, просто увеличивая указатель вместо того, чтобы использовать array[index] и индексный тест в качестве вашего условия.Многие процессоры на самом деле могут сделать pointer+offset для вас, и на этих процессорах метод pointer++ не может быть выигрышным для вас.В этом случае я бы посоветовал вам попытаться изменить внешний цикл и отсчитать ваш индекс до index < 0.Попытка уменьшить его непосредственно перед тестом часто приводит к тому, что устанавливаются те же флаги, что и при явном тестировании значения против 0, и компиляторы обычно используют это при включении оптимизации.

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

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

Answer 7

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

Вы можете использовать модифицированное устройство Даффа:

void inline BitsToWords(int8    *pc_BufIn, 
                        int16   *pw_BufOut, 
                        int32   BufInLen)
{
    uint32 i,j,z=0;

    for(i=0; i<BufInLen; i++)
    {
        uint8   byte = pc_BufIn[i];
        for (j = 0; j < 2; ++j)
        {
            switch (byte & 0x0F)
            {
                case 0:     // 0000 binary
                    pw_BufOut[z++] = 0x7F;
                    pw_BufOut[z++] = 0x7F;
                    pw_BufOut[z++] = 0x7F;
                    pw_BufOut[z++] = 0x7F;
                    break;
                case 1:     // 0001 binary
                    pw_BufOut[z++] = 0x7F;
                    pw_BufOut[z++] = 0x7F;
                    pw_BufOut[z++] = 0x7F;
                    pw_BufOut[z++] = 0x81;
                    break;
                case 2:     // 0010 binary
                    pw_BufOut[z++] = 0x7F;
                    pw_BufOut[z++] = 0x7F;
                    pw_BufOut[z++] = 0x81;
                    pw_BufOut[z++] = 0x7F;
                    break;

               // And so on ...
                case 15:        // 1111 binary
                    pw_BufOut[z++] = 0x81;
                    pw_BufOut[z++] = 0x81;
                    pw_BufOut[z++] = 0x81;
                    pw_BufOut[z++] = 0x81;
                    break;
            } // End: switch
            byte >>= 1;
        }
    }
}

Answer 8

Если вы не возражаете против наличия 256 pw_Bufout в памяти, вы можете попытаться сгенерировать все возможные выходные данные и пропустить второй цикл, изменив его на pw_BufOut [i] = perm [pc_BufIn [i]]; (Пермь является массивом со всеми перестановками)

Answer 9

Я мог бы предложить создать таблицу поиска из 8 возможных однобитовых масок (то есть 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80) и затем использовать их для сравнения с вашим битовым полем в цикле. Псевдокод (битовые маски выше называются bitmask, в соответствующем порядке):

for(i=0,i<BufInLen;i++)
  for(j=0;j<8;j++,z++)
    pw_BufOut[z]=(pc_BufIn[i]&bitmask[j])==0?0x007f:0x0081;

Answer 10

Вы можете извлечь pc_BufIn[i] во внешний цикл. Также на первый взгляд при обратном отсчете во втором цикле можно пропустить расчет 7-j.