Проблема производительности: NAL Unit Wrapping

Question

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

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

Функция принимает входной поток данных (фактически случайные биты с точки зрения энтропии) и упаковывает его в единицу NAL. Это включает размещение escape-кодов: любая последовательность байтов 00 00 00, 00 00 01, 00 00 02 или 00 00 03 заменяется на 00 00 03 XX, где XX - это последний байт исходной последовательности. Как можно догадаться, они размещаются только примерно в 1 на каждые 4 миллиона байтов ввода, учитывая шансы против такой последовательности - так что это проблема, когда человек ищет огромный объем данных и почти ничего не делает для это за исключением очень редких случаев. Однако, поскольку «выполнение чего-либо» включает вставку байтов , это усложняет задачу. Текущий неоптимизированный код следующий 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 байт данных.

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

---

Answer 1

Хм ... как насчет этого?

#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 есть некоторое дублирование усилий, от которого было бы неплохо избавиться.

Answer 2

Применение очевидных оптимизаций к вашему коду:

#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 3

Мне кажется, что пока вы копируете побайтово, вы не будете сталкиваться с проблемами выравнивания слов при обращении к памяти, и это будет замедлять вас.

Итак, я бы предложил следующее (извините за псевдокод, мой C / C ++ в значительной степени забыт):

• Поиск, чтобы найти следующую точку вставки
  [Алгоритм поиска Boyer-Moore был бы хорошим выбором, так как он сублинейный (не нужно проверять каждый байт)]
• Блок-копия неизмененного блока
  [Насколько я понимаю, GCC и другие хорошие компиляторы C ++ могут превратить вызов memcpy() непосредственно в правильную инструкцию процессора, обеспечивая почти оптимальную производительность]
• Вставьте измененный код
• Повторите, пока не будет сделано

Answer 4

Такой тест безумно зависит от вашего компилятора и настроек процессора / памяти. В моей системе моя улучшенная версия имеет ту же скорость, что и версия Майка Ф. strlen / memcpy.

Answer 5

Быстрее версия моего предыдущего ответа:

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

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 7

Майк Ф, большое спасибо за «маловероятное» предложение: следующее примерно на 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% быстрее, чем оригинал (!!!) Я до сих пор не могу понять, почему вероятный () в условии цикла помогает вообще ... должно быть, gcc снова странный.

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

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