优化算术编码器

Question

我正在优化名为PackJPG的C库的编码步骤

我使用英特尔 VTune 分析了代码，发现当前的瓶颈是 PackJPG 使用的算术编码器中的以下函数：

void aricoder::encode( symbol* s )
{   
    // update steps, low count, high count
    unsigned int delta_plus_one = ((chigh - clow) + 1);
    cstep = delta_plus_one / s->scale;
    chigh = clow + ( cstep * s->high_count ) - 1;
    clow  = clow + ( cstep * s->low_count );

    // e3 scaling is performed for speed and to avoid underflows
    // if both, low and high are either in the lower half or in the higher half
    // one bit can be safely shifted out
    while ( ( clow >= CODER_LIMIT050 ) || ( chigh < CODER_LIMIT050 ) ) {
        if ( chigh < CODER_LIMIT050 ) { // this means both, high and low are below, and 0 can be safely shifted out
            // write 0 bit
            write_zero();
            // shift out remaing e3 bits
            write_nrbits_as_one();

        }
        else { // if the first wasn't the case, it's clow >= CODER_LIMIT050
            // write 1 bit
            write_one();
            clow  &= CODER_LIMIT050 - 1;
            chigh &= CODER_LIMIT050 - 1;
            // shift out remaing e3 bits

            write_nrbits_as_zeros();
        }
        clow  <<= 1;
        chigh = (chigh << 1) | 1;

    }

    // e3 scaling, to make sure that theres enough space between low and high
    while ( ( clow >= CODER_LIMIT025 ) && ( chigh < CODER_LIMIT075 ) ) {
        ++nrbits;
        clow  &= CODER_LIMIT025 - 1;
        chigh ^= CODER_LIMIT025 + CODER_LIMIT050;
        // clow  -= CODER_LIMIT025;
        // chigh -= CODER_LIMIT025;
        clow  <<= 1;
        chigh = (chigh << 1) | 1;

    }
}

这个函数好像借鉴了一些来自:http://paginas . Fe . up . pt/~ vinho za/itpa/BOD den-07-algorithm-tr . pdf我已经设法对函数做了一些优化(主要是通过加快位写的速度)但是现在卡住了。

秒-

该代码是使用 MSVC（来自 Visual Studio 2013）编译的，具有以下设置：

/GS /Qpar- /GL /analyze- /W3 /Gy- /Zc:wchar_t /Zi /Gm- /Ox /sdl /Fd"Release\vc120.pdb" /fp:precise /D "WIN32" /D "NDEBUG" /D "_WINDOWS" /D "_USRDLL" /D "PACKJPG_EXPORTS" /D "_CRT_SECURE_NO_WARNINGS" /D "BUILD_DLL" /D "_WINDLL" /D "_UNICODE" /D "UNICODE" /errorReport:prompt /WX- /Zc:forScope /arch:IA32 /Gd /Oy- /Oi /MT /Fa"Release\" /EHsc /nologo /Fo"Release\" /Ot /Fp"Release\PackJPG.pch" 

关于如何进一步优化这个有什么想法吗？

更新1到目前为止，我已经尝试了所有建议，这是最快的版本：

void aricoder::encode( symbol* s )
{   
    unsigned int clow_copy = clow;
    unsigned int chigh_copy = chigh;
    // update steps, low count, high count
    unsigned int delta_plus_one = ((chigh_copy - clow_copy) + 1);
    unsigned register int cstep = delta_plus_one / s->scale;

    chigh_copy = clow_copy + (cstep * s->high_count) - 1;
    clow_copy = clow_copy + (cstep * s->low_count);

    // e3 scaling is performed for speed and to avoid underflows
    // if both, low and high are either in the lower half or in the higher half
    // one bit can be safely shifted out
    while ((clow_copy >= CODER_LIMIT050) || (chigh_copy < CODER_LIMIT050)) {
        if (chigh_copy < CODER_LIMIT050) {  // this means both, high and low are below, and 0 can be safely shifted out
            // write 0 bit
            write_zero();
            // shift out remaing e3 bits
            write_nrbits_as_one();

        }
        else { // if the first wasn't the case, it's clow >= CODER_LIMIT050
            // write 1 bit
            write_one();
            clow_copy &= CODER_LIMIT050 - 1;
            chigh_copy &= CODER_LIMIT050 - 1;
            // shift out remaing e3 bits

            write_nrbits_as_zeros();
        }
        clow_copy <<= 1;
        chigh_copy = (chigh_copy << 1) | 1;

    }

    // e3 scaling, to make sure that theres enough space between low and high
    while ((clow_copy >= CODER_LIMIT025) & (chigh_copy < CODER_LIMIT075)){
        ++nrbits;
        clow_copy &= CODER_LIMIT025 - 1;
        chigh_copy ^= CODER_LIMIT025 + CODER_LIMIT050;
        // clow  -= CODER_LIMIT025;
        // chigh -= CODER_LIMIT025;
        clow_copy <<= 1;
        chigh_copy = (chigh_copy << 1) | 1;

    }
    clow = clow_copy;
    chigh = chigh_copy;
}

• 通过使用避免一个分支

遗憾的是，以下建议并未提高性能：

• 用带有goto语句的switch替换第一个while循环
• 使用定点算法进行除法（产生舍入误差）
• 打开开关-

@example认为，不是除法变慢，而是除法的一个操作数的内存访问。这似乎是正确的。根据VTune，我们经常在这里遇到缓存未命中。关于如何解决这个问题的任何建议？

Answer 1

To start offCODER_LIMIT050是一个愚蠢的名称，由于CODER_LIMIT025和CODER_LIMIT075的共存而变得特别愚蠢。除此之外，如果没有副作用，您可能不想使用短路逻辑，所以第二个while语句可以是：

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

第一个while块可以进一步优化，将每次迭代的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-

Answer 2

这不是完整的答案。此代码演示了如何使用定点算法执行快速整数除法。广泛应用于DSP和信号处理。注意，只有在很少发生“规模”更改的情况下，代码才有意义进行优化。此外，在“scale”值较小的情况下，可以重写代码以使用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;
}

Answer 3

根据VTune，我们经常在这里遇到缓存未命中。关于如何解决这个问题的任何建议？

我们组织数据的方式直接影响数据局部性的性能，因此缓存机制的表现取决于此。因此，为了实现这一点，我们的程序应该尽可能地进行线性内存访问，并且应该避免任何间接的内存读/写(基于指针的数据结构)。这真的会受到高速缓存机制的欢迎，因为拥有L1高速缓存的内存的概率会明显更高。

查看代码和VTune报告时，看起来最重要的数据是传递给这个特定函数的参数。这个对象的各种数据成员在这个特定的函数中被使用(内存读取)。

void aricoder::encode( symbol* s )

现在，程序访问此对象的数据成员的位置有以下代码：

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

从这两个VTune报告中，我们可以验证所有三个内存访问都有不同的计时。这表明这些数据位于此特定对象的不同偏移。在访问其中一个时-

> < li>

将最常访问的数据成员放入对象中的热区。这意味着我们应该将所有这些成员放在对象的第一个/顶部。通过这种方式，我们将有更好的机会将我们的对象放入对象的第一个缓存行。因此，我们应该尝试按照数据成员访问来重新组织对象内存布局。我假设您没有处理这个对象中的虚拟表，因为它们不太适合缓存机制。

您的整个程序可能是这样组织的：在这一点上（即执行此函数），一级缓存已满，因此程序试图从二级缓存和此转换访问它，会有更多的CPU周期（峰值）。在这种情况下，我认为我们不能做太多，因为这是机器的一种限制，从某种意义上说，我们太过扩大了我们的边界，试图处理太低级别的东西。

您的对象似乎是POD的类型，因此会有线性访问。这很好，没有改进的余地。但是，我们的分配方式可能会对缓存机制产生影响。如果每次都分配它，则在当前函数内执行时可能会产生影响。

除此之外，我认为我们还应该参考以下SO帖子，其中非常详细地讨论了这些概念（数据缓存/指令缓存）。这些帖子也有很好的链接，其中包含有关此内容的深入分析和信息。

什么是“缓存友好型”代码？

如何用c写指令缓存友好的程序？

我建议你应该试着参考这些帖子。它们对理解这些概念的内部结构非常有帮助，即使它可能不会帮助你优化当前的代码。可能你的程序已经优化了，我们对此无能为力：）。