Арифметический сдвиг влево более чем на 31 разряд

[bekas]

Предполагается, что следующая программа
выполняется в Microsoft Visual C++ 6.0:

#include <stdio.h>

int n1 = 31, n2 = 32, n3 = 33;

int main(int argc, char **argv)
{
printf("a) %x %x %x\n", 5<<n1, 5<<n2, 5<<n3);
printf("b) %x %x %x\n", 5<<31, 5<<32, 5<<33);
return(0);
}

и печатает результат:

a) 80000000 5 a
b) 80000000 0 0

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

a) 80000000 0 0
b) 80000000 0 0

Этот же вопрос можно отнести и к компиляторам C++ других
платформ, у которых разрядность int равна 32 бита.

[незваный гость]

Вопрос сразу - а в каком режиме компилируется программа (C или C++)? MS по умолчанию определяет по расширению файла.

[Sanyok]

to bekas:
Пробовали в ассемблерный код это перевести? Мож, тогда все прояснится? Я откомпилировал GCC, watcom C/C++ (из состава mingw) - результат тот же, что и у Вас. При обоих режимах (С и С++) получается одно и то же. Ща в асменный код переведу и позыркаю

[незваный гость]

Я поспешил задать вопрос. Согласно стандарту обоих языков, поведение оператора << не определено, если величина сдвига больше либо равна разрядности (а также если левый операнд отрицательный). В случае явного значения обеих величин, MS использует константные вычисления в компиляторе. В компиляторе (по-видимому) все целые значения хранятся и обрабатываются как 64битные, и лишь потом приводятся к нужной разрядности. В случае же вычисления в программе MS вполне резонно использует команду Intel'овского процессора, которая игнорирует биты старше 5го (32рарядный сдвиг).

Более точно сей тест выглядит таким образом:

#include <stdlib.h>

void foo(int n5, int n31, int n32, int n33) {
    printf("%d << %d: %x %x %x %x", n5, n31, 5 << 31, 5 << n31, n5 << 31, n5 << n31);
    printf("%d << %d: %x %x %x %x", n5, n32, 5 << 32, 5 << n32, n5 << 32, n5 << n32);
    printf("%d << %d: %x %x %x %x", n5, n33, 5 << 33, 5 << n33, n5 << 33, n5 << n33);
}

int main(int argc, char** argv) {
    foo(5, 31, 32, 33);
}

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

[Sanyok]

Незванный гость, Вы как всегда правы - в случае констант (при втором вызове printf) компилятор использовал константные вычисления. Это хорошо видно из асменного кода (компилятор GCC, у MS я опции перевода в асм не нашел)

Используется синтаксис ASM

        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        andl    $-16, %esp
        movl    $0, %eax
        movl    %eax, -4(%ebp)
        movl    -4(%ebp), %eax
        call    __alloca
        call    ___main
        movl    $5, %eax
        movb    _n3, %cl
        sall    %cl, %eax
        pushl   %eax
        movl    $5, %eax
        movb    _n2, %cl
        sall    %cl, %eax
        pushl   %eax
        movl    $5, %eax
        movb    _n1, %cl
        sall    %cl, %eax
        pushl   %eax
        pushl   $LC0
        call    _printf
        addl    $16, %esp
        pushl   $0
        pushl   $0
        pushl   $-2147483648
        pushl   $LC1
        call    _printf
        addl    $16, %esp
        movl    $0, %eax
        leave
        ret

Видно невооруженным глазом, что во втором случае компилер сразу грузит в качестве параметров нули, а в первом что-то пытается вычислять(и, похоже, команда sall дает не совсем те результаты, что ожидал bekas)!

[незваный гость]

Позвольте обратить Ваше внимание на следующий фрагмент:

   movl   $5, %eax
   movb   _n1, %cl
   sall   %cl, %eax 

Id est, GCC грузит второй операнд как байт! Он знает, что только 5 бит использутся, и не утруждает себя и процессор грузить слово.

[Sanyok]

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

[незваный гость]

Sanyok писал(а):

:) Хотя я слышал, что иногда лучше все-таки оперировать словами (а не байтами). Вроде как скорострельность будет больше, если данные в памяти выровнены по границам слов, и грузятся соответственно тоже словами.

Это очень тонкий вопрос. И самое главное - а хотите ли Вы оптимизировать программу на таком уровне. Главная проблема - это слишком многое зависит от конкретного процессора и конкретного железа (контроллера памяти и самой памяти). Точное априорное предсказание поведения возможно, но требует просто колосальных трудозатрат. Motorola, например, публикует схемы выполнения команды в процессоре с правилами их наложения, et cetera. И, несмотря на их подробность, я не уверен, что они достаточно полны и точны.

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

Мой вывод такой - оптимизация всей программы того не стоит. Надо писать аккуратно и грамотно. Если этого мало - найти 10% кода, тратящих 90% времени, и оптимизировать их. В остальном довериться авторам компилятора и библиотеки. (Я видел как-то серьезный memcpy() для Intel'а - с опережающей закачкой в кэш процессора, оптимизацией размера обращения к памяти, и прочее. Ну их на фиг. Я лучше буду благодарным пользователем такой библиотеки - до тех пор, пока сам не сяду писать библиотеку. Или не прижмет крепенько.)

Помимо всего прочего, оптимизированный код хуже читается, и дороже в сопровождении, что немаловажно.

[bekas]

to Sanyok:

Чтобы получить ассемблерный код для MS, необходимо:

1) По Alt+F7 открыть окно 'Project Settings'
2) Выбрать закладку 'C/C++'
3) В выпадающем списке 'Category' выбрать 'Listing Files'
4) В выпадающем списке 'Listing file type' выбрать подходящую
опцию, например, 'Assemble,Machine Code,and Source'
5) Перекомпилиривоть проект с предварительным Clean

В соответствующем каталоге, например, Release, для каждого '.cpp'
появится символьный файл '.cod', содержащий ассемблерные команды.

to незванный гость:

(а также если левый операнд отрицательный). - имелся в виду правый операнд?

[Sanyok]

Вот, то что MS наваял:

Используется синтаксис ASM

_main   PROC NEAR
; File shift.c
; Line 6
        push    ebp
        mov     ebp, esp
; Line 7
        mov     eax, 5
        mov     ecx, DWORD PTR _n3
        shl     eax, cl
        push    eax
        mov     edx, 5
        mov     ecx, DWORD PTR _n2
        shl     edx, cl
        push    edx
        mov     eax, 5
        mov     ecx, DWORD PTR _n1
        shl     eax, cl
        push    eax
        push    OFFSET FLAT:$SG343
        call    _printf
        add     esp, 16                                 ; 00000010H
; Line 8
        push    0
        push    0
        push    -2147483648                             ; 80000000H
        push    OFFSET FLAT:$SG344
        call    _printf
        add     esp, 16                                 ; 00000010H
; Line 9
        xor     eax, eax
; Line 10
        pop     ebp
        ret     0
_main   ENDP

Как видите - один черт, что тот, что другой. Все дело в том, как процессор выполняет комаду сдвига.

[незваный гость]

bekas писал(а):

(а также если левый операнд отрицательный). - имелся в виду правый операнд?

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

[незваный гость]

Маленькое уточнение - в С-99 уточнено, что для отрицательных значений результат сдвига влево не определен.