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

Ответ 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;
}

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

Ответ 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, чтобы предотвратить оптимизацию циклов.

Ответ 3

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

Ответ 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;
}

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

Ответ 5

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

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

Ответ 6

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

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

Ответ 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;
    ...

РЕДАКТИРОВАТЬ по тристопии: версия последнего варианта версии 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;
}

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

Ответ 8

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

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

Ответ 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

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

Pascal Cuoq с ручным оптимизацией (также и престиж):

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().

Ответ 10

Хорошо еще одна версия. Подобно Fred, но с меньшим количеством операций.

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

Ответ 11

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

int precalc[1<<16];
int precalchigh[1<<16];
void doprecalc()
{
    for(int i = 0; i < 1<<16; i++) {
        precalc[i] = (i < (1<<8) ? 1 : 2);
        precalchigh[i] = precalc[i] + 2;
    }
}
inline int len(uint32 val)
{
    return (val & 0xffff0000 ? precalchigh[val >> 16] : precalc[val]);
}

Ответ 12

Минимальное количество бит, необходимое для хранения целого числа:

int minbits = (int)ceil( log10(n) / log10(2) ) ;

Число байтов:

int minbytes = (int)ceil( log10(n) / log10(2) / 8 ) ;

Это полностью связанное FPU решение, производительность может быть или не быть лучше, чем условный тест, но заслуживает изучения.

[EDIT] Я провел расследование; простой цикл из десяти миллионов итераций выше принял 918 мс, тогда как решение FredOverflow приняло всего 49 мс (VС++ 2010). Таким образом, это не улучшается с точки зрения производительности, но может оставаться полезным, если бы это было количество бит, которое требовалось, и возможны дальнейшие оптимизации.

Ответ 13

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

"Ого! Более 10 миллионов раз... Вы имеете в виду, что если вы выдержите три цикла из этой функции, вы сэкономите до 0.03s?"

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

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

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

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

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

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

Ответ 14

Если я помню 80x86 asm правильно, я бы сделал что-то вроде:

  ; Assume value in EAX; count goes into ECX
  cmp eax,16777215 ; Carry set if less
  sbb ecx,ecx      ; Load -1 if less, 0 if greater
  cmp eax,65535
  sbb ecx,0        ; Subtract 1 if less; 0 if greater
  cmp eax,255
  sbb ecx,-4       ; Add 3 if less, 4 if greater

Шесть инструкций. Я думаю, что такой же подход будет работать и для шести инструкций по используемому ARM.