代码之家 › 专栏 › 技术社区 › psihodelia

如何优化这个将输入位转换成单词的简单函数?

bit-manipulation algorithm performance c c++

psihodelia · 技术社区 · 14 年前

我已经编写了一个函数,它读取字节的输入缓冲区,并生成字的输出缓冲区,其中每个字可以是输入缓冲区的每个on位的0x0081,也可以是每个off位的0x007f。给出了输入缓冲区的长度。两个阵列都有足够的物理位置。我还有大约2字节的空闲RAM,我可以用它来查找表。

现在,我发现这个函数是我在实时应用程序中的瓶颈。它将被频繁地调用。你能提出一个优化这个功能的方法吗?我看到一种可能是只使用一个缓冲区并进行就地替换。

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/硬件的优化,因为它是一个多平台项目。

12 回复 | 直到 14 年前

Michael Burr 14 年前

我还有大约2字节的空闲RAM,我可以用来查找表。

您的查阅表格可以放置在 const 在编译时数组,所以它可以在ROM中—这是否为您提供了直接的4KB表的空间?

如果您能够提供4KB的ROM空间,那么唯一的问题就是在 .c 文件-但这只需要执行一次,您可以编写一个脚本来执行(这可能有助于确保它是正确的,如果您决定以后由于某种原因需要更改表,也可能会有所帮助)。

您必须进行概要分析,以确保从ROM到目标阵列的拷贝实际上比计算进入目标阵列所需的速度要快-如果有以下情况,我不会感到惊讶:

/* 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; 
    }
}

最终会更快。我希望该函数的优化构建将所有内容都保存在寄存器中或编码到指令中,除了每个输入字节的一次读取和每个输出字的一次写入。或者差不多。

您可以通过一次处理多个输入字节来进一步优化,但是接下来必须处理对齐问题,以及如何处理不是所处理块大小的倍数的输入缓冲区。这些问题并不难处理,但它们确实会使事情复杂化,而且不清楚您可能期望得到什么样的改进。

JoeG 14 年前

我想你不能用平行论?

这只是一个猜测——你真的需要一个分析器来指导——但我认为查找表可以工作。

如果我理解正确,输入数组中的每个字节在输出中产生16个字节。所以一个为一个单字节输入提供16字节输出的查找表应该取4kib——这比您需要的空间要大。

您可以将每个字节拆分为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]);
  }
}

此外,如果发现循环开销过大,可以使用 Duff's Device .

Community CDub 7 年前

第一次尝试:

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];
  } 
 } 
}

第二次尝试,无耻地从 Michael Burr (谁已经从我这里得到了+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);  
    } 
}

greyfade 14 年前

假设 pc_bufIn 和 pw_bufOut 指向不重叠的内存区域,我可以在头脑中想出一些优化方法。首先,可以将指针声明为非别名:

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

这将允许编译器执行优化,否则是不允许的。请注意,编译器可能使用不同的关键字;我认为有些用法 __restrict__ 或者可能具有编译器特定的属性。请注意,唯一的要求是 蟾酥 和 普氏蟾蜍 不要重叠。由于编译器不会尝试重新读取,因此这会立即提高性能。 蟾酥 无论何时 普氏蟾蜍 写入(每8次写入保存7次读取)。

如果该关键字不可用,则可以进行其他优化:

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

对我来说,上面的轻微重写更容易遵循,因为它明确地说明了CPU所采用的路径,但我希望优化是显而易见的:将值存储在 pc_bufIn[i] 到一个临时局部变量,而不是在内部循环的每次迭代中点击指针。

另一个不太明显的优化将利用大多数CPU上日益常见的矢量硬件(包括ARM的Neon和Intel的SSE)一次合成16个字节的结果。我建议调查一下这个选择。

Craig Trader 14 年前

如果您打算使用原始速度,那么使用查找表(以避免使用位移位的内部循环)可能是最好的方法。

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

存在的问题是,查找表本身是4KB(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; 
  }
}

更复杂但可能更快的方法是使用 De Bruijn sequence 对所有可能的查找值进行编码。这会将查找表从4KB减少到512+14,但需要额外的间接级别和另一个索引表(256字节),总共782字节。这将删除memcpy()调用中的一个,以及shift和bitswise和,而代价是再多一个索引。在你的案例中可能不需要,但还是很有趣。

Edward Strange 14 年前

我打算为每个人推荐一个Boost::,因为它将分解循环,但最终还不知道。我认为你能得到的最好的办法就是解开内环。我会想办法的。Boost::for_each over an MPL::range may be an option there.

jopa 14 年前

你可以提取 pc_BufIn[i] 进入外环。同样,当在第二个循环中向后计数时,您可以跳过 7-j 计算。

VeeArr 14 年前

我可能建议创建一个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;

Thomas Matthews 14 年前

首先,因为你有点烦躁,所以把所有东西都改成无符号。这就消除了因延长标志或其他与标志相关的操作而产生的任何不良影响。

您可以使用修改过的Duff设备:

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

Radu Chivu 14 年前

如果您不介意在内存中有256个pw_bufout,您可以尝试生成所有可能的输出,并通过将其更改为pw_bufout[i]=perm[pc_bufin[i];(perm是具有所有排列的数组)

Chris Walton 14 年前

立即想到的是:

展开内部循环(编译器可能已经这样做了,但如果手动进行,可以进一步优化,请参见下面的内容)
不要保留“z”,而是保留一个递增的指针(编译器可能已经这样做了)
不要对每个展开的项执行比较,而是向下移动提取的移位,使其位于第二位。把这个加到0x7f上,并把它放入值中。这将给您每个0x7f或0x81。

最好的办法是看看为目标平台生成了什么样的汇编程序,看看编译器在做什么。

编辑:我不会使用查阅表格。额外缓存未命中的成本可能会超过简单计算的成本。

伊迪丝2:让我去另一台电脑,启动编译器,我看看我能做些什么。

nategoose 14 年前

首先,你这样做是为了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 内存块到其他东西(我想是一块硬件)。然后,您可以减少输出阵列的内存需求,这可能会提高缓存性能。