Есть ли более эффективный способ получить длину 32-битного целого числа в байтах?

Question

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

inline int len(uint32 val)
{
    if(val <= 0x000000ff) return 1;
    if(val <= 0x0000ffff) return 2;
    if(val <= 0x00ffffff) return 3;
    return 4;
} 

Кто-нибудь имеет идеи ...классный трюк с битооперацией?Заранее спасибо за помощь!

Answer 1

Как насчет этого?

inline int len(uint32 val)
{
    return 4
        - ((val & 0xff000000) == 0)
        - ((val & 0xffff0000) == 0)
        - ((val & 0xffffff00) == 0)
    ;
}

При удалении ключевого слова inline, g++ -O2 компилирует его в следующий код без ответвлений:

movl    8(%ebp), %edx
movl    %edx, %eax
andl    $-16777216, %eax
cmpl    $1, %eax
sbbl    %eax, %eax
addl    $4, %eax
xorl    %ecx, %ecx
testl   $-65536, %edx
sete    %cl
subl    %ecx, %eax
andl    $-256, %edx
sete    %dl
movzbl  %dl, %edx
subl    %edx, %eax

Если вы не возражаете против машинно-ориентированных решений, вы можете использовать инструкцию bsr, которая ищет первый 1 бит. Затем вы просто делите на 8, чтобы преобразовать биты в байты, и добавляете 1, чтобы сместить диапазон от 0,3 до 1,4:

int len(uint32 val)
{
    asm("mov 8(%ebp), %eax");
    asm("or  $255, %eax");
    asm("bsr %eax, %eax");
    asm("shr $3, %eax");
    asm("inc %eax");
    asm("mov %eax, 8(%ebp)");
    return val;
}

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

Компилятор GNU также имеет интересную встроенную функцию под названием __builtin_clz:

inline int len(uint32 val)
{
    return ((__builtin_clz(val | 255) ^ 31) >> 3) + 1;
}

Для меня это выглядит намного лучше, чем встроенная версия сборки:)

Answer 2

Я сделал небольшой ненаучный тест, просто измерив разницу в вызовах GetTickCount () при вызове функции в цикле от 0 до MAX_LONG раз в компиляторе VS 2010.

Вот что я увидел:

Это заняло 11497 тиков

inline int len(uint32 val)
{
    if(val <= 0x000000ff) return 1;
    if(val <= 0x0000ffff) return 2;
    if(val <= 0x00ffffff) return 3;
    return 4;
} 

В то время как это заняло 14399 тиков

inline int len(uint32 val)
{
    return 4
        - ((val & 0xff000000) == 0)
        - ((val & 0xffff0000) == 0)
        - ((val & 0xffffff00) == 0)
    ;
}

edit: мое представление о том, почему кто-то был быстрее, неверно, потому что:

inline int len(uint32 val)
{
    return 1
        + (val > 0x000000ff)
        + (val > 0x0000ffff)
        + (val > 0x00ffffff)
        ;
}

В этой версии использовано всего 11107 тиков.Так как + быстрее чем - возможно?Я не уверен.

Еще быстрее, хотя бинарный поиск был на 7161 тактах

inline int len(uint32 val)
{
    if (val & 0xffff0000) return (val & 0xff000000)? 4: 3;
    return (val & 0x0000ff00)? 2: 1;
}

И пока самым быстрым является использование встроенной функции MS на 4399 тактах

#pragma intrinsic(_BitScanReverse)

inline int len2(uint32 val)
{
    DWORD index;
    _BitScanReverse(&index, val);

    return (index>>3)+1;

}

Для справки - вот код, который я использовал для профилирования:

int _tmain(int argc, _TCHAR* argv[])
{
    int j = 0;
    DWORD t1,t2;

    t1 = GetTickCount();

    for(ULONG i=0; i<-1; i++)
        j=len(i);

    t2 = GetTickCount();

    _tprintf(_T("%ld ticks %ld\n"), t2-t1, j);


    t1 = GetTickCount();

    for(ULONG i=0; i<-1; i++)
        j=len2(i);

    t2 = GetTickCount();

    _tprintf(_T("%ld ticks %ld\n"), t2-t1, j);
}

Пришлось печатать j, чтобы предотвратить оптимизацию циклов.

Answer 3

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

Answer 4

Двоичный поиск МОЖЕТ сэкономить несколько циклов, в зависимости от архитектуры процессора.

inline int len(uint32 val)
{
    if (val & 0xffff0000) return (val & 0xff000000)? 4: 3;
    return (val & 0x0000ff00)? 2: 1;
}

Или, обнаружение, которое является наиболее распространенным случаем, может снизить среднее число циклов, если большинство входных данных составляют один байт (например, при построении кодировок UTF-8, но тогда ваши точки останова не будут 32/24 / 16/8):

inline int len(uint32 val)
{
    if (val & 0xffffff00) {
       if (val & 0xffff0000) {
           if (val & 0xff000000) return 4;
           return 3;
       }
       return 2;
    }
    return 1;
}

Теперь короткий случай делает наименьшее количество условных тестов.

Answer 5

Если битовые операции быстрее, чем сравнение на вашей целевой машине, вы можете сделать это:

inline int len(uint32 val)
{
    if(val & 0xff000000) return 4;
    if(val & 0x00ff0000) return 3;
    if(val & 0x0000ff00) return 2;
    return 1;
} 

Answer 6

У вас может быть более эффективное решение в зависимости от вашей архитектуры.

В MIPS есть инструкция "CLZ", которая подсчитывает количество старших нулевых битов числа.То, что вы ищете здесь, по сути 4 - (CLZ(x) / 8) (где / - целочисленное деление).PowerPC имеет эквивалентную инструкцию cntlz, а x86 имеет BSR.Это решение должно упростить до 3-4 инструкций (не считая затрат на вызов функции) и ноль ветвей.

Answer 7

В некоторых системах это может быть быстрее на некоторых архитектурах:

inline int len(uint32_t val) {
   return (int)( log(val) / log(256) );  // this is the log base 256 of val
}

Это также может быть немного быстрее (если сравнение занимает больше, чем побитовое и):

inline int len(uint32_t val) {
    if (val & ~0x00FFffFF) {
        return 4;
    if (val & ~0x0000ffFF) {
        return 3;
    }
    if (val & ~0x000000FF) {
        return 2;
    }
    return 1;

}

Если вы используете 8-битный микроконтроллер (например, 8051 или AVR), тогда это будет работать лучше всего:

inline int len(uint32_t val) {
    union int_char { 
          uint32_t u;
          uint8_t a[4];
    } x;
    x.u = val; // doing it this way rather than taking the address of val often prevents
               // the compiler from doing dumb things.
    if (x.a[0]) {
        return 4;
    } else if (x.a[1]) {
       return 3;
    ...

EDIT от tristopia: версия последнего варианта с поддержкой Endianness

int len(uint32_t val)
{
  union int_char {
        uint32_t u;
        uint8_t a[4];
  } x;
  const uint16_t w = 1;

  x.u = val;
  if( ((uint8_t *)&w)[1]) {   // BIG ENDIAN (Sparc, m68k, ARM, Power)
     if(x.a[0]) return 4;
     if(x.a[1]) return 3;
     if(x.a[2]) return 2;
  }
  else {                      // LITTLE ENDIAN (x86, 8051, ARM)
    if(x.a[3]) return 4;
    if(x.a[2]) return 3;
    if(x.a[1]) return 2;
  }
  return 1;
}

Из-за const любой компилятор, достойный его соли, будет генерировать код только для правильного порядка байтов.

Answer 8

Вы можете избежать условных переходов, которые могут быть дорогостоящими, если распределение ваших чисел не облегчает прогноз:

return 4 - (val <= 0x000000ff) - (val <= 0x0000ffff) - (val <= 0x00ffffff);

Изменение <= на & ничего не изменит на современном процессоре. Какая у вас целевая платформа?

Вот сгенерированный код для x86-64 с gcc -O:

    cmpl    $255, %edi
    setg    %al
    movzbl  %al, %eax
    addl    $3, %eax
    cmpl    $65535, %edi
    setle   %dl
    movzbl  %dl, %edx
    subl    %edx, %eax
    cmpl    $16777215, %edi
    setle   %dl
    movzbl  %dl, %edx
    subl    %edx, %eax

Конечно, есть инструкции сравнения cmpl, но за ними следуют setg или setle вместо условных ветвей (как обычно). Это условная ветвь, которая стоит дорого на современном конвейерном процессоре, а не сравнение. Так что эта версия сохраняет дорогие условные ветки.

Моя попытка оптимизировать сборку gcc вручную:

    cmpl    $255, %edi
    setg    %al
    addb    $3, %al
    cmpl    $65535, %edi
    setle   %dl
    subb    %dl, %al
    cmpl    $16777215, %edi
    setle   %dl
    subb    %dl, %al
    movzbl  %al, %eax

Answer 9

Просто чтобы проиллюстрировать, основываясь на ответе FredOverflow (это хорошая работа, слава и +1), распространенную ловушку в отношении веток на x86.Вот сборка FredOverflow, выведенная gcc:

movl    8(%ebp), %edx   #1/.5
movl    %edx, %eax      #1/.5
andl    $-16777216, %eax#1/.5
cmpl    $1, %eax        #1/.5
sbbl    %eax, %eax      #8/6
addl    $4, %eax        #1/.5
xorl    %ecx, %ecx      #1/.5
testl   $-65536, %edx   #1/.5
sete    %cl             #5
subl    %ecx, %eax      #1/.5
andl    $-256, %edx     #1/.5
sete    %dl             #5
movzbl  %dl, %edx       #1/.5
subl    %edx, %eax      #1/.5
# sum total: 29/21.5 cycles

(задержка в циклах должна читаться как Прескотт / Нортвуд)

Сборка, оптимизированная вручную Паскалем Куоком (также слава):

cmpl    $255, %edi      #1/.5
setg    %al             #5
addb    $3, %al         #1/.5
cmpl    $65535, %edi    #1/.5
setle   %dl             #5
subb    %dl, %al        #1/.5
cmpl    $16777215, %edi #1/.5
setle   %dl             #5
subb    %dl, %al        #1/.5
movzbl  %al, %eax       #1/.5
# sum total: 22/18.5 cycles

Редактировать: решение FredOverflow, использующее __builtin_clz():

movl 8(%ebp), %eax   #1/.5
popl %ebp            #1.5
orb  $-1, %al        #1/.5
bsrl %eax, %eax      #16/8
sarl $3, %eax        #1/4
addl $1, %eax        #1/.5
ret
# sum total: 20/13.5 cycles

и сборку gcc для вашего кода:

movl $1, %eax        #1/.5
movl %esp, %ebp      #1/.5
movl 8(%ebp), %edx   #1/.5
cmpl $255, %edx      #1/.5
jbe  .L3             #up to 9 cycles
cmpl $65535, %edx    #1/.5
movb $2, %al         #1/.5
jbe  .L3             #up to 9 cycles
cmpl $16777216, %edx #1/.5
sbbl %eax, %eax      #8/6
addl $4, %eax        #1/.5
.L3:
ret
# sum total: 16/10 cycles - 34/28 cycles

, в которой строка кэша командвыборки, которые являются побочным эффектом инструкций jcc, вероятно, ничего не стоят для такой короткой функции.

Ответвления могут быть разумным выбором, в зависимости от входного распределения.

Редактировать:добавлено решение FredOverflow, использующее __builtin_clz().

Answer 10

Паскалю Куоку и еще 35 людям, которые проголосовали за его комментарий:

"Ух ты! Более 10 миллионов раз ... Вы имеете в виду, что если вы выжмете три цикла из этой функции, высохранить столько, сколько 0,03 с? "

Такой саркастический комментарий в лучшем случае грубый и оскорбительный.

Оптимизация часто является кумулятивным результатом 3% здесь, 2% там.3% от общей емкости - это ничего , на которое можно чихнуть.Предположим, это была почти насыщенная и непараллелизуемая стадия в трубе.Предположим, загрузка ЦП возросла с 99% до 96%.Простая теория очередей говорит о том, что такое уменьшение загрузки ЦП уменьшило бы среднюю длину очереди более чем на 75%.[качественное (нагрузка делится на 1-нагрузку)]

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

Показатели прибыльности чего-либо имеют тенденцию к росту, и замена конкретного процессора на месте или покупка более быстрой коробки зачастую просто не вариант.

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

Паскаль Куок должен принести оригинальному постеру извинения.