从我过去所看到的情况来看，StackOverflow似乎喜欢编程方面的挑战，例如从快速字符转换为字符串的练习问题，该问题得到了数十种响应。这是一项优化挑战：采用一个非常简单的功能，看看是否可以提出一种更智能的方法。

我已经有一个函数想要进一步优化一段时间，但是我总是发现我的优化存在一些漏洞，导致错误的输出-在某些罕见的特殊情况下，它们会失败。但是，有了该功能，我一直认为应该可以做得更好。

该函数获取输入数据流(从熵的角度来看实际上是随机位)，并将其包装到NAL单元中。这涉及放置转义码：将00 00 00、00 00 01、00 00 02或者00 00 03的任何字节序列替换为00 00 03 XX，其中XX是原始序列的最后一个字节。可以猜到，考虑到这种序列的几率，每输入400万个字节，它们只会放置大约1个。因此，这是一个挑战，因为其中一个人要搜索大量数据，而对其中的任何内容几乎不执行任何操作。非常罕见的情况。但是，由于"做某事"涉及插入字节，因此使事情变得有些棘手。当前未优化的代码为以下C：

src和dst是指向字节数组的指针，end是指向输入数据结尾的指针。

int i_count = 0;
while( src < end )
{
    if( i_count == 2 && *src <= 0x03 )
    {
        *dst++ = 0x03;
        i_count = 0;
    }
    if( *src == 0 )
        i_count++;
    else
        i_count = 0;
    *dst++ = *src++;
}

此功能的通用输入大小范围大约在1000到1000000字节的数据之间。

我的最初想法包括一个函数(以某种方式)快速搜索输入中是否需要转义码的情况，以避免在不需要放置转义码的绝大多数输入中避免更复杂的逻辑。

解决方案

将明显的优化应用于代码：

#define unlikely(x) __builtin_expect((x),0)

while( src < end )
{
    const char s = *src++;
    if( unlikely(i_count==2 && s<=0x03) )
    {
        *dst++ = 0x03;
        i_count = 0;
    }
    if( unlikely(s==0) )
        i_count++;
    else
        i_count = 0;
    *dst++ = s;
}

Mike F，非常感谢"不太可能"的建议：以下内容比原始内容快10％：

#define unlikely(x) __builtin_expect((x),0)
while( src < end )
{
    if( unlikely(i_count == 2) && unlikely(*src <= 0x03) )
    {
        *dst++ = 0x03;
        i_count = 0;
    }
    if( unlikely(*src == 0) )
        i_count++;
    else
        i_count = 0;
    *dst++ = *src++;
}

而且，更好的是，以下内容比原始(!!!)快50％，我仍然不知道为什么循环条件中的可能性()可能根本没有帮助...必须再次变得怪异。

#define unlikely(x) __builtin_expect((x),0)
#define likely(x) __builtin_expect((x),1)
while( likely(src < end) )
{
    if( unlikely(i_count == 2) && unlikely(*src <= 0x03) )
    {
        *dst++ = 0x03;
        i_count = 0;
    }
    if( unlikely(*src == 0) )
        i_count++;
    else
        i_count = 0;
    *dst++ = *src++;
}

但是，我希望的不仅仅是优化当前的幼稚方法。我怀疑肯定有比仅单独处理每个字节更好的方法。

while (src < end-2)
{
    if ((src[0] == 0) && (src[1] == 0) && (src[2] <= 3))
    {
        dst[0] = 0;
        dst[1] = 0;
        dst[2] = 3;
        dst[3] = src[2];
        src += 3;
        dst += 4;
    }
    else
        *dst++ = *src++;
}
while (src < end)
    *dst++ = *src++;

嗯...这样的事情怎么样？

#define likely(x) __builtin_expect((x),1)
#define unlikely(x) __builtin_expect((x),0)

while( likely(src < end) )
{
    //Copy non-zero run
    int runlen = strlen( src );
    if( unlikely(src+runlen >= end) )
    {
        memcpy( dest, src, end-src );
        dest += end-src;
        src = end;
        break;
    }

    memcpy( dest, src, runlen );
    src += runlen;
    dest += runlen;

    //Deal with 0 byte
    if( unlikely(src[1]==0 && src[2]<=3 && src<=end-3) )
    {
        *dest++ = 0;
        *dest++ = 0;
        *dest++ = 3;
        *dest++ = *src++;
    }
    else
    {
        *dest++ = 0;
        src++;
    }
}

在strcpy和memcpy之间有一些重复的工作，尽管可以消除。

我以前的答案的较快版本：

while (src < end-2)
{
    if (src[0] == 0)
    {
        if (src[1] == 0)
        {
            if (src[2] <= 3)
            {
                dst[0] = 0;
                dst[1] = 0;
                dst[2] = 3;
                dst[3] = src[2];
                src += 3;
                dst += 4;
            }
            else
            {
                dst[0] = 0;
                dst[1] = 0;
                dst[2] = src[2];
                src += 3;
                dst += 3;
            }
        }
        else
        {
            dst[0] = 0;
            dst[1] = src[1];
            src += 2;
            dst += 2;
        }
    }
    else
        *dst++ = *src++;
}
while (src < end)
    *dst++ = *src++;

像这样的测试疯狂地取决于编译器和处理器/内存设置。在我的系统上，改进版本的速度与Mike F的strlen / memcpy版本完全相同。

在我看来，只要我们逐字节复制，访问内存时就会遇到字对齐问题，这些问题会让我们放慢速度。

因此，我建议采取以下措施(对不起，对于伪代码，我的C / C ++基本上被人遗忘了)：

• 搜索以查找下一个插入点[Boyer-Moore搜索算法将是一个不错的选择，因为它是亚线性的(不需要检查每个字节)]
• 块复制未更改的块[我的理解是，GCC和其他良好的C ++编译器可以将memcpy()调用直接转换为正确的处理器指令，从而提供接近最佳的性能]
• 插入修改后的代码
• 重复直到完成