Вопрос: Как оптимизировать этот кусок кода в C


Вчера в интервью мне было предложено протестировать 5-й бит в количестве (чтобы проверить, включено ли оно и выключено) и ниже, как я это сделал.

int number = 16;
int mask   = 1<<5;

if ((number & mask) == 0)
    printf("Bit is off");
else
    printf("its on");

но затем он попросил меня оптимизировать этот код и сделать это, не используя эту конкретную маску.

Итак, мои вопросы о том, какую маску я мог бы использовать в этом коде?


6


источник


Ответы:


Возможно, интервьюер хотел посмотреть, как вы отреагировали на простой вызов. Или просто хотел узнать, действительно ли вы поняли C, и вы останетесь на своем месте? Может быть, интервьюер хотел знать, знаете ли вы, что ненулевое значение истинно, и, следовательно, проверить свою глубину понимания C? Или, может быть, вы могли бы сделать двоичный код в гексагоне?

Интервью ИМХО - это много  больше, чем код. Они дорогие. Я всегда старался получить четкое представление о человеке, что-то трудно сделать, написав сообщение или даже по телефону. В конце концов, некоторые из этих людей будут работать с рекрутом!

Скорее всего, самый компактный и, возможно, самый быстрый:

int number = 16;  // is this really what they gave?

printf((number & 0x20)?"its on":"Bit is off"); // did they mean 5th or bit 5?

Редактировать:

Я закодировал оригинальный подход и свою альтернативу и скомпилировал его для ARM Coretx-M3 / 4 (это тот процессор, о котором я пишу сейчас). Он был скомпилирован с -O3. Затем я разобрал каждый скомпилированный файл (используя objdump), чтобы получить ассемблер. Я сделал это так, потому что вывод gcc -S был огромным; который включает в себя много дополнительной информации для ассемблера и компоновщика, что затрудняет поиск кода.

Я заменил printf на dummy_printf, чтобы избежать #including stdio.h, который добавил больше шума. Dummy_printf не совсем то же самое, что и printf, он просто принимает один параметр, но он не дает выход короткому :-)

Источник (все 7 файлов, добавленные для облегчения чтения): http://pastebin.com/PTeApu9n

Полученный в результате конкатенированный вывод objdump (для каждого .o) равен: http://pastebin.com/kHAmakE3

Как вы можете видеть, оригинал скомпилирован для:

void original_bit5(int number) {
    int mask = 1<<5;

    if ((number & mask) == 0)
   0:   f010 0f20   tst.w   r0, #32
   4:   d005        beq.n   1a <original_bit5+0x1a>
        dummy_printf("Bit is off");
    else
        dummy_printf("its on"); 
   6:   f240 0000   movw    r0, #0
   a:   f2c0 0000   movt    r0, #0
   e:   f7ff bffe   b.w 0 <dummy_printf>

void original_bit5(int number) {
    int mask = 1<<5;

    if ((number & mask) == 0)
        dummy_printf("Bit is off");
  12:   f240 0000   movw    r0, #0
  16:   f2c0 0000   movt    r0, #0
  1a:   f7ff bffe   b.w 0 <dummy_printf>
  1e:   bf00        nop

Я думаю, что вызов dummy_printf использует цепочку вызовов по вызову, т. Е. Dummy_printf не вернется к этой функции. Очень эффективный!

Нет кода ввода функции, поскольку первые четыре параметра функции передаются в регистры r0-r3.

Вы не можете видеть адреса двух строк, загружаемых в r0. Это потому, что это не связано.

Ты это видишь:

int mask = 1<<5;    
if ((number & mask) == 0)

составлен для:

   0:   f010 0f20   tst.w   r0, #32
   4:   d005        beq.n   1a <original_bit5+0x1a>

Так 1<<5 а также (... == 0), являются компилятором для более прямой и эффективной последовательности инструкций. Существует ветвь для соответствующего вызова dummy_printf.

Мой код компилируется в:

void my_bit5(int number) {
    dummy_printf((number & 0x20)?"its on":"Bit is off");    
   0:   f240 0200   movw    r2, #0
   4:   f240 0300   movw    r3, #0
   8:   f010 0f20   tst.w   r0, #32
   c:   f2c0 0200   movt    r2, #0
  10:   f2c0 0300   movt    r3, #0
  14:   bf14        ite ne
  16:   4610        movne   r0, r2
  18:   4618        moveq   r0, r3
  1a:   f7ff bffe   b.w 0 <dummy_printf>
  1e:   bf00        nop

Это также похоже на оптимизацию хвостового вызова, т. Е. Нет возврата от этой функции, потому что нет необходимости в одном, возврат dummy_printf будет возвращаться непосредственно к main ()

То, что вы не видите, это два регистра, r2 и r2 будут содержать адреса двух строк. Это потому, что это не связано.

Как вы видите, есть инструкция условного исполнения 'ite', которая загружает регистр параметров r0 либо регистром r2, либо регистром r3. Таким образом, в этом коде нет ветви.

Для простого процессора с конвейерной обработкой это может быть весьма эффективным. На простом конвейерном процессоре ветвь может вызывать «конвейерную остановку», в то время как части трубопровода очищаются. Это зависит от процессора и процессора. Поэтому я предполагаю, что gcc получил это правильно и сгенерировал лучшую последовательность кода, чем выполнение ветки. Я не проверял.

Поднятый Лундином, я придумал это:

void union_bit5(int number) {
    union { int n; struct { unsigned :5; unsigned bit :1; }; } tester;
    tester.n = number;

    if (tester.bit)
        dummy_printf("Bit is on");
    else
        dummy_printf("its off");    
}

Он явно не включает маску или смещение бит. Это почти наверняка зависит от компилятора, вам придется протестировать его, чтобы он работал (glerk! - (

gcc для ARM генерирует один и тот же код (bne vs beq, но который может быть отрегулирован) в качестве решения OP, поэтому нет оптимизации, но он удаляет маску:

void union_bit5(int number) {
    union { int n; struct { unsigned :5; unsigned bit :1; }; } tester;
    tester.n = number;

    if (tester.bit)
   0:   f010 0f20   tst.w   r0, #32
   4:   d105        bne.n   1a <union_bit5+0x1a>
        dummy_printf("Bit is on");
    else
        dummy_printf("its off");    
   6:   f240 0000   movw    r0, #0
   a:   f2c0 0000   movt    r0, #0
   e:   f7ff bffe   b.w 0 <dummy_printf>
void union_bit5(int number) {
    union { int n; struct { unsigned :5; unsigned bit :1; }; } tester;
    tester.n = number;

    if (tester.bit)
        dummy_printf("Bit is on");
  12:   f240 0000   movw    r0, #0
  16:   f2c0 0000   movt    r0, #0
  1a:   f7ff bffe   b.w 0 <dummy_printf>
  1e:   bf00        nop

Для чего это стоит:

(number & 0x20)? dummy_printf("its on") : dummy_printf("Bit is off");

gcc для ARM генерирует точно такой же код, что и OP. Он генерирует ветви, а не условные инструкции.

Резюме:

  1. Исходный код скомпилирован в очень эффективную последовательность инструкций
  2. Тройной ...?...:... оператор может скомпилировать код, который не включает ветви на ARM Cortex-M3 / 4, но может также генерировать обычные инструкции ветвления.
  3. В этом случае сложно написать более эффективный код, чем оригинал :-)

Я добавлю, ИМХО, стоимость выполнения printf настолько огромна по сравнению с бит-тестом, что беспокоиться об оптимизации бит теста слишком мало; это не удается Закон Амдаля , Соответствующей тактикой для теста бит является обеспечение использования -O3 или -Os.


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

#define BIT5(val) (((val)&0x20)?1:0)
const unsigned char bit5[256] = {
BIT5(0x00),BIT5(0x01), BIT5(0x02),BIT5(0x03), 
BIT5(0x04),BIT5(0x05), BIT5(0x06),BIT5(0x07),
// ... you get the idea ...
BIT5(0xF8),BIT5(0xF9), BIT5(0xFA),BIT5(0xFB), 
BIT5(0xFC),BIT5(0xFD), BIT5(0xFE),BIT5(0xFF)
};

//...
if (bit5[(unsigned char)number]) {
    printf("its on");
} else {
    printf("Bit is off");
}

Это удобный метод, если есть, например, некоторые сложные битовые шаблоны, например, периферийный регистр, который нуждается в преобразовании в решение или переключении. Это O (1) тоже

Вы могли бы объединить два! -)


6



Есть два способа проверить бит:

if (number & (1 << bit)) { ... }
if ((number >> bit) & 1) { ... }

Я думаю, это будет интересно для вас: http://graphics.stanford.edu/~seander/bithacks.html


2



Еще один способ

1: сдвиньте правое число 5 раз, чтобы 5-й бит стал 0-м справа (т.е. LSB).
2: Теперь логика - это номера с LSB, поскольку 1 нечетны, а числа с 0 равны. Убедитесь, что с использованием% 2

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

И быстрее, чем целочисленная модульная операция? ,

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


1



Вы уверены, что вы должны переместить его 5 бит ? Как насчет этого:

int n = 16;
printf ("%d\n", (n >> 4) % 2); 

1



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

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

Вот код, который gcc 4.2.1-O3 производит для if((number >> 5) & 1)):

0000000100000ee0    pushq   %rbp
0000000100000ee1    movq    %rsp,%rbp
0000000100000ee4    shrl    $0x05,%edi
0000000100000ee7    notl    %edi
0000000100000ee9    andl    $0x01,%edi
0000000100000eec    movl    %edi,%eax
0000000100000eee    leave
0000000100000eef    ret

и для if(number & (1 << 5)):

0000000100000ee0    pushq   %rbp
0000000100000ee1    movq    %rsp,%rbp
0000000100000ee4    shrl    $0x05,%edi
0000000100000ee7    notl    %edi
0000000100000ee9    andl    $0x01,%edi
0000000100000eec    movl    %edi,%eax
0000000100000eee    leave
0000000100000eef    ret

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


0



(number & 16)?printf("yes"):printf("no");

0



Все смещаются вправо. Я хочу быть оригинальным и смещаться влево:

#define INDEX 5

int number = 16;

if (number<<(sizeof(number)*8-INDEX-1)<0)

  printf("Bit #%d is set in %d.\n", INDEX, number);
else    
  printf("Bit #%d is NOT set in %d.\n", INDEX, number);

Этот код является уродливым и абсолютно  зависит от реализации (стандарт C говорит, что результат не определен). На x86 он работает, и он несколько эффективнее, потому что MSB всегда копируется в бит # 7 («знак») регистра флагов, который можно протестировать с помощью одного jns инструкция.

Другими словами, для INDEX 5 у вас есть:

[...]
shl $0x1F, %eax
test %eax, %eax
jns 8053635
[...]

Исходное решение OP более чистое, и именно так должен выглядеть производственный код.


0



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

Если мы проанализируем этот код, это то, что мы получаем:

1<<5 переводится в буквальный 32 во время компиляции. Нет никакой разницы в производительности между письмом int mask = 1<<5; а также int mask = 32;, но последнее гораздо труднее понять.

В дальнейшем,

  • if ((number & mask) == 0) полностью эквивалентна
  • if ((number & 32) == 0) полностью эквивалентна
  • if ((number & (1<<5)) == 0)

Существует два случая:

  • Либо компилятор должен найти ячейку памяти для сохранения маски.
    • Если пользователь объявляет переменную маску, значение будет храниться там.
    • Если пользователь не объявил переменную, значение будет храниться в невидимой временной переменной.
    • Потребление ОЗУ в двух вышеуказанных случаях полностью эквивалентно.
  • Или компилятору не нужно хранить маску в любом месте. Он будет оптимизировать всю переменную маски или числовой литерал и испечь их вместе с остальной частью инструкции программы.

Какой из этих двух будет выбран, зависит от того, будет ли int number = 16; изменен или не от точки объявления до оператора if, где происходит маскировка.

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


0



Простите следующий ответ:

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

запрос на k-й бит может означать, что младший значащий бит - это нулевой бит, чтобы (число & 1 << 5) не выполнялось. Но это не проблема. Он попросил оптимизацию. Когда-то причина, по которой вы выходите из интервью, не имеет к вам никакого отношения. В этом случае это их потеря; всегда будет другая возможность для собеседования.


0



Попробовать новичку c ученика

int number = 16;
if(16 == number&(0x10))
    puts("true");
else
    puts("false");

0



В одном из интервью я дал следующий ответ, и он был доволен, но небольшое изменение в вопросе было «проверить, установлен ли n-й бит.

int N = 16;
printf ("%d\n", (N >> (n-1)) % 2); 

Таким образом, когда вы делаете ответ общим, Не совсем уверен, какой из них (ниже) работает быстрее для этого примера.

1<<(n-1) & N (or)
N>>(n-1) % 2 (or)
N>>(n-1) & 1

0