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

Я написал функцию, которая считывает входной буфер байтов и создает выходной буфер слов, где каждое слово может быть либо 0x0081 для каждого бита входного буфера, либо 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 );
  }
 }
}

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

12 2
performance algorithm bit-manipulation

12 ответов:

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

Ваши таблицы подстановки могут быть помещены в массив const во время компиляции, так что это может быть в ROM - это дает вам место для простой таблицы 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; 
    }
}

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

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

6

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

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

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

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

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]);
  }
}
Кроме того, если вы обнаружите, что накладные расходы на цикл чрезмерны, вы можете использовать устройство Даффа.
2

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

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);  
    } 
}
2

Исходя из предположения, что 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 );
  }
 }
}

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

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

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

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 (), а также сдвиг и побитовое и, за счет еще одного индекса. Возможно, в вашем случае это и не нужно, но все равно интересно.

1

Я собирался предложить boost:: for_each, так как он распутает петлю, но конец неизвестен. Лучшее, что я думаю, вы получите, это распутать внутреннюю петлю. Я бы искал способы сделать это. boost:: for_each над диапазоном mpl::может быть там опцией.

0

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

0

Я мог бы предложить создать таблицу поиска из 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;
0

Во-первых, поскольку вы немного крутите, измените все на 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;
        }
    }
}
0

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

0

Что сразу приходит на ум:

  • разверните внутренний цикл (компилятор может сделать это уже сейчас, но вы можете оптимизировать дальше, если сделаете это вручную, см. ниже)
  • вместо сохранения "z", держите указатель, который увеличивается (компилятор может сделать это уже)
  • вместо того, чтобы выполнять сравнение, для каждого развернутого элемента сдвиньте вниз смещение, которое вы извлекли, чтобы оно было на втором месте. Добавьте это к 0x7f и поместите это в значение. Это даст вам 0x7F или 0x81 для каждого.

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

EDIT: я бы не стал использовать таблицу подстановки. Стоимость дополнительных пропусков кэша, вероятно, будет больше, чем стоимость простого расчета.

EDIT2: Дайте мне добраться до другого компьютера и запустить компилятор, и я посмотрю, что я могу сделать.

0

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

Вы можете захотеть 

#include <stdint.h>

Он содержит typedef s для целых чисел размера с такими именами, как 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, и компиляторы обычно используют это преимущество при включении оптимизации.

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

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

0