Performance challenge: NAL Unit Wrapping

Question

From what I've seen in the past, StackOverflow seems to like programming challenges, such as the fast char to string exercise problem which got dozens of responses. This is an optimization challenge: take a very simple function and see if you can come up with a smarter way of doing it.

I've had a function that I've wanted to further optimize for quite some time but I always find that my optimizations have some hole that result in incorrect output--some rare special case in which they fail. But, given the function, I've always figured one should be able to do better than this.

The function takes an input datastream (effectively random bits, from an entropy perspective) and wraps it into a NAL unit. This involves placing escape codes: any byte sequence of 00 00 00, 00 00 01, 00 00 02, or 00 00 03 gets replaced with 00 00 03 XX, where XX is that last byte of the original sequence. As one can guess, these only get placed about 1 in every 4 million bytes of input, given the odds against such a sequence--so this is a challenge where one is searching an enormous amount of data and doing almost nothing to it except in very rare cases. However, because "doing something" involves inserting bytes, it makes things a bit trickier. The current unoptimized code is the following C:

src and dst are pointers to arrays of bytes, and end is the pointer to the end of the input data.

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

Common input sizes to this function range from roughly between 1000 and 1000000 bytes of data.

Initial ideas of mine include a function which (somehow) quickly searches the input for situations where an escape code is needed, to avoid more complex logic in the vast majority of inputs where escape codes don't need to be placed.

---

Answer 1

Applying the obvious optimisations to your code:

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

Answer 2

Mike F, thanks a lot for the "unlikely" suggestion: the following is about 10% faster than the original:

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

And, even better, the following is 50% faster than the original (!!!) I still can't figure out why the likely() in the loop condition helps at all... must be gcc being weird again.

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

However, I was hoping for more than just optimizing the current naive approach; I suspect there must be a better way to do it than merely handling every byte individually.

Answer 3

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

Answer 4

Hmm...how about something like this?

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

There's some duplication of effort between strcpy and memcpy it'd be nice to get rid of though.

Answer 5

Faster version of my previous answer:

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

Answer 6

A test like this is insanely dependent on your compiler and processor/memory setup. On my system, my improved version is the exact same speed as Mike F's strlen/memcpy version.

Answer 7

It seems to me that as long as you're copying byte-by-byte you'll be falling foul of word alignment issues when accessing memory, and these will be slowing you down.

So, I'd suggest the following (sorry for the pseudo code, my C/C++ is largely forgotten):

• Search to find the next insertion point
  [The Boyer-Moore search algorithm would be a good bet, as it's sublinear (doesn't need to examine every byte)]
• Block copy the unchanged block
  [My understanding is that GCC and other good C++ compilers can turn the memcpy() call directly into the correct processor instruction, giving near optimal performance]
• Insert the altered code
• Repeat until done