C/C++, стандарти, компілятори, оптимізація...

Довелося недавно розповідати про представлення цілих знакових, зокрема -- від'ємних, чисел у C/C++ (signed int і сімейство). Так як часу було мало, і всі відомі мені архітектури (x86, AVR, ARM) використовують доповняльний код, (two's complement),  розповідав лише про нього. Зокрема, продемонстрував, що буде, якщо до максимального додатного значення, яке влазить у певний тип, додати 1, або від максимального за модулем від'ємного, відняти 1. (Див. додаток 1, або рисунок праворуч.)

#include <iostream>
#include <climits>

using namespace std;

int main()
{
 int m=-INT_MAX;
 cout << m << endl;
 --m;
 cout << m << endl;
 --m;
 cout << m << endl; 

 ++m;
 cout << m << endl;  

 }

Подивився на то мій колега, Орест Гера, і зауважив, що, здається, в стандарті такого не пише. Навів приклад, де компілятор відхиляється від цього правила.


Довелося лізти в стандарт. (Для визначеності, цитати нижче взяті з стандарту C++-98/(версії від 2003 року). Аналогічний текст присутній і в стандарті C++-11.)

• 3.9.1 (Fundamental types) - 3: For each of the signed integer types, there exists a corresponding (but different) unsigned integer type: “unsigned char”, “unsigned short int”, “unsigned int”, and “unsigned long int,” each of which occupies the same amount of storage and has the same alignment requirements (3.9) as the corresponding signed integer type [40]; that is, each signed integer type has the same object representation as its corresponding unsigned integer type.  The range of nonnegative values of a signed integer type is a subrange of the corresponding unsigned integer type, and the value representation of each corresponding signed/unsigned type shall be the same. Виноска 40 не має відношення до теми.
• 3.9.1 (Fundamental types) - 4: Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo \(2^n\) where  n is the number of bits in the value representation of that particular size of integers [41]. Виноска 41 каже: This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned inte-ger type.
• 3.9.1 (Fundamental types) - 7: Types bool, char, wchar_t, and the signed and unsigned integer types are collectively called integra types.[43] A synonym for integral type is integer type.  The representations of integral types shall define values by use of  a pure binary numeration system.[44] [Example: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types.]. Виноска 43 відношення до теми не має, вона про перерахункові типи, виноска 44: A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position. (Adapted from the American National Dictionary for Information Processing Systems.
• 5.3.1 (Unary operators) - 7: The operand of the unary - operator shall have arithmetic or enumeration type and the result is the negation of its operand.  Integral promotion is performed on integral or enumeration operands.  The negative of an unsigned quantity is computed by subtracting its value from \(2^n\) , where n is the number of bits in the promoted operand.  The type of the result is the type of the promoted operand.

Тобто, якщо коротко, для беззнакових типів поведінка за переповнення задана чітко --- переноси у відсутні старші розряди просто відкидати. Унарний мінус для беззнакових операндів повинен давати від'ємне число у доповняльному коді. Однак, доповняльний код не нав'язується для від'ємних чисел! Більше того, явно стверджується, що стандарт сумісний з іншими методами представлення від'ємних чисел (див. додаток 1).

Зроблено це, очевидно, щоб на апаратурі, яка не використовує доповняльний код, компілятори не мусили емулювати його. (Традиція С --- бути максимально близькою до "заліза".). Однак, переважна більшість сучасних процесорів та контролерів використовують саме доповняльний код, тому проблем із відсутністю в стандарті явної вимоги не мало б бути? Неправильно. Стандарт --- свого роду юридичний документ. Він, (з поправкою на помилки), дозволяє все, що має бути явно дозволено, забороняє все, що має бути явно заборонено, і залишає на розсуд реалізації все решта. Тому компілятори не зобов'язані вважати, що від'ємні числа записані у доповняльному коді. І вони тим користуються!

Той же колега запропонував мінімальний приклад:

#include <iostream>
#include <climits>
#include <cstdlib>

using namespace std;

bool foo(int x)
{
 int sum = x + 2;
 return x < 0 || sum > 0;
}

int main()
{
 std::cout.setf(std::ios::boolalpha);

 int m=INT_MAX;
 cout << " (x < 0) or (sum > 0) is: " << foo(m) << endl;

 system("PAUSE");
 return 0;
}

Якщо задати x=INT_MAX, зрозуміло, що x+2 дасть знакове переповнення, і хоча x>0, sum вийде меншим нуля. Тому вираз (x<0 або sum>0) не буде істинним, дорівнюватиме 0 (false). Але це -- тільки в припущенні, що за переповнення, після найбільшого додатного йтиме найбільше за модулем від'ємне.

Що ж на практиці? Всі випробувані компілятори (декілька версій gcc, по одній clang, icc, VS2010), у всіх випадках дали для x значення 2147483647, для sum --- -2147483647. Тобто, нічого хитрувати не пробували. Результати ж роботи функції представлені у таблиці:

Компілятор	Результат роботи функції
Visual Studio 2010 Express, x86-32 Default Debug	false
Visual Studio 2010 Express, x86-32 Default Release	false
mingw, x86-32, gcc 4.6.2	false
mingw, x86-32, gcc 4.6.2 -O3	false
mingw, x86-32, gcc 4.6.2 -Os	false
mingw, x86-32, gcc 4.6.2 -O3 --expensive-optimizations	false
mingw64, x86-32/64, gcc 4.7.2	false
mingw64, x86-32/64, gcc 4.7.2 -O3	true
mingw64, x86-32/64, gcc 4.7.2 -Os	true
mingw64, x86-32/64, gcc 4.7.2 -O2	true
mingw64, x86-32/64, gcc 4.7.2 -O1	false
mingw64, x86-32/64, gcc 4.8.0	false
mingw64, x86-32/64, gcc 4.8.0 -O3	true
mingw64, x86-32/64, gcc 4.8.0 -Os	true
mingw64, x86-32/64, gcc 4.8.0 -O2	true
mingw64, x86-32/64, gcc 4.8.0 -O1	false
mingw64, x86-32, clang 3.2	false
mingw64, x86-32, clang 3.2 -O0 (Default --- O2)	false
mingw64, x86-32, clang 3.2 -O3	false
mingw64, x86-32, clang 3.2 -Os	false
Linux, CentOS5, x86-64, gcc 3.4.6	false
Linux, CentOS5, x86-64, gcc 3.4.6 -O3	false
Linux, CentOS5, x86-64, gcc 3.4.6 -Os	false
Linux, CentOS5, x86-64, gcc 3.4.6 -O3 --expensive-optimizations	false
Linux, CentOS5, x86-64, gcc 4.1.2	false
Linux, CentOS5, x86-64, gcc 4.1.2 -O3	false
Linux, CentOS5, x86-64, gcc 4.1.2 -Os	false
Linux, CentOS5, x86-64, gcc 4.1.2 -O3 --expensive-optimizations	false
Linux, CentOS5, x86-64, gcc 4.5.1	false
Linux, CentOS5, x86-64, gcc 4.5.1 -O3	false
Linux, CentOS5, x86-64, gcc 4.5.1 -Os	false
Linux, CentOS5, x86-64, gcc 4.5.1 -O3 --expensive-optimizations	false
Linux, Debian, x86-32, gcc 4.6.3	false
Linux, Debian, x86-32, gcc 4.6.3 -O3	false
Linux, Debian, x86-32, gcc 4.6.3 -Os	false
Linux, Debian, x86-32, gcc 4.6.3 -O3 --expensive-optimizations	false
Linux, Debian, x86-32, gcc 4.7.2	false
Linux, Debian, x86-32, gcc 4.7.2 -O3	true
Linux, Debian, x86-32, gcc 4.7.2 -Os	true
Linux, Debian, x86-32, gcc 4.7.2 -O2	true
Linux, Debian, x86-32, gcc 4.7.2 -O1	false
Linux, CentOS5, x86-64, icc 11.1 20091130	false
Linux, CentOS5, x86-64, icc 11.1 20091130 -O3	false
Linux, CentOS5, x86-64, icc 11.1 20091130 -Os	false
Linux, CentOS5, x86-64, icc 11.1 20091130 -O3 --expensive-optimizations	false

Як бачимо, VS-2010, clang 3.2, icc 11.1, gcc 3.4, gcc 4.1, gcc 4.5, gcc 4.6, не залежно від платформи (із випробуваних комбінацій та випробуваних третіх чисел версії, але все ж), виводили, як і очікувалося, false. Новіші gcc, gcc 4.7 та gcc 4.8 скористалися вільністю в стандарті, і заоптимізували результат, виводячи true! (Ймовірно, міркуючи, що раз x>0, то і x+додатне число, буде більшим нуля.) При тому, він, зрозуміло, відрізняється від очікуваного... Хоча, хто що очікує --- їх поведінка ближча до природних математичних очікувань щодо сум.

gcc 4.7+ демонстрували цю поведінку лише з -O2 і більш сильними опціями оптимізації, але не для -O1. Правда, для 4.7.2, спроба вмикати по одній опції, що відрізняють -O2 від -O1, не дала такого результату. Або я щось впустив, або до нього приводить комбінація кількох опцій зразу. Полінувався детальніше розбиратися. Якщо читати changes-log для gcc 4.7, там згадується про покращення міжпроцедурної оптимізації, наприклад: "Heuristics now take into account that after inlining code will be optimized out because of known values (or properties) of function parameters." і "The inter-procedural constant propagation pass has been rewritten. It now performs generic function specialization.".  Можливо, це воно. Або саме воно дозволяє спрацювати якійсь іншій оптимізації.

Чи можна тут вивести якусь мораль? Не знаю...

Зрозуміло, що пишучи власні програми, темними кутками стандартів користуватися не слід. Але концепція доповняльного коду --- аж ніяк не темний куток. Довелося лізти в стандарт, перевіряти. З іншого боку, компілятор ніби теж нічого поганого не робить... Тільки результат несподіваний. Але і покладатися на переповнення знакових чисел, як виявляється, теж не дуже хороша практика.

На разі --- все,

дякую за увагу!

_______________________________________________________________________

Додаток 1 -- кодування від'ємних чисел

Якщо коротко, це такий хитрий спосіб представити потенційно від'ємні числа. Зрозуміло, що знак слід якось відмічати. Так як він може набувати двох значень, + та -, одним із бітів доведеться пожертвувати.Ось як саме це зробити -- точки зору розходяться.  (Всі приклади, для простоти --- 8-бітні)

Найпростіший підхід -- один біт виділити під знак, решту під модуль числа. Спосіб незручний -- під час всіх математичних операцій слід окремо пильнувати за знаком, крім того ще й існує два нуля, +0 і -0. (Наприклад, для 8-бітних знакових чисел, 0000 0000, і 1000 0000 .)  Зате знайомий нам із алгебри. Використовувався в деяких ранніх машинах (стаття у Вікі, на яку посилання вище, наводить, як приклад, IBM 7090).

+5 -- 0000 0101b

-5 -- 1000 0101b

Дещо більш просунутий, Ones' complement (не вдалося знайти офіційний переклад, доповнення до 1?) -- теж виділяє старший біт як знак, однак представляє негативні числа побітовим not, "обертанням", відповідних додатних. При цьому від'ємні числа отримуються просто :

+5 -- 0000 0101b

-5 -- 1111 1010b

Арифметика для такого кодування дещо простіша. Розглянемо на прикладі додавання. (З іншими операціями теж просто, але писати підручник по двійковій арифметиці неохота поки. :)  Додатні числа додаються звично, поки результат поміщається у наявній розрядності (наприклад, у 7 бітів для 8-бітного знакового), результат буде правильним. Якщо додати від'ємне та додатне число, і результат від'ємний, то все теж просто:

-5 -- 1111 1010b

+                  

+3 -- 0000 0011b

___    __________

-2 -- 1111 1101b

 Якщо ж результат буде додатним:

-5 --   1111 1010b

+                    

+7 --   0000 0111b

___    __________

 2 -- 1 0000 0001b

то результат виходитиме невірним, про це свідчитиме перенос у відсутній, 9-й, (8-й, якщо нумерувати, як прийнято у комп'ютерному світі, з нуля) розряд --- так-зване переповнення. Щоб виправити його, слід додати 1:  0000 0001b+1b=0000 0010b, якраз десяткове 2. 

Тобто, алгоритм додавання простий --- додаємо, якщо є перенос, додаємо до результату одиничку.

Ще один метод, offset binary, (двійковий зсув?), оголошує, що найбільше за модулем від'ємне буде представлене всіма нулями, найбільше додатне --- всіма одиницями. При цьому вибирається певне число, K, яке вважатимемо нулем. Якщо вибрати \(K=2^{n-1}\), де n --- розрядність чисел, то воно майже співпадатиме із доповнювальним представленням, тільки знаковий біт буде інвертованим. Одна із переваг -- оператори порівняння даватимуть правильну відповідь завжди, тоді як для доповнювального представлення, лише коли знаки співпадають.

Цікаве представлення --- із від'ємною основою системи числення. Замість 2 взяти -2. Тоді нульовий біт, \((-2)^0=1\) відповідатиме одиницям, перший --- \((-2)^1=-2\), другий -- \((-2)^2=4\). Спосіб цікавий, хоч і екзотичний. Кажуть (стаття з Вікі), що його було реалізовано в польському комп'ютері BINEG, в 1957-59 роках. Математичні операції складні.

Іноді також пориваються використовувати для знаку наймолодший, а не найстарший, біт, і т. д. і т. п.

Нарешті, найбільш поширеною системою є доповняльний код, (Two's complement). У ньому, щоб отримати від'ємне число, всі біти модуля інвертують (побітове not), до результату додаючи одиницю:

+5 -- 0000 0101b

-5 -- 1111 1011b

Щоб знайти модуль, операцію достатньо повторити  --- інвертуємо, додаємо 1.

При цьому, не тільки додавання додатних чисел зразу даватиме правильний результат, але й додавання будь-яких комбінацій додатних та від'ємних:

-5 -- 1111 1011b

+                  

+3 -- 0000 0011b

___    __________

-2 -- 1111 1110b

якщо трапиться перенос, його просто відкидаємо:

-5 --   1111 1011b

+                    

+7 --   0000 0111b

___    __________

 2 -- 1 0000 0010b

Виглядає це, на прикладі 4-бітних чисел, якось так:

Цей код має наступну властивість: якщо від найбільшого, за модулем, від'ємного числа, відняти 1, отримаємо найбільше додатне. Яке буде на одиницю більше за модуль "найвід'ємнішого" --- це ще одна властивість, замість "від'ємного нуля" маємо ще одне ненульове число. Звичайно, справедливе і зворотне --- якщо до найбільшого додатного додати одиницю, отримаємо найбільше за модулем від'ємне.

Додаток 2

Компілятор має певну свободу у перетасовуванні виразів, якщо це не суперечить стандарту. Через помилку побачив це ще з однієї, незапланованої, сторони.

Частина випробувань проводилася із трішки модифікованою програмою:

#include <iostream>
#include <climits>
#include <cstdlib>

using namespace std;

bool foo(int x)
{
 cout << "x = " << x << endl;
 int sum = x + 2;
 cout << "sum = " << sum << endl;
 cout << "x<0 : " << (x<0) << endl;
 cout << "sum>0 : " << (sum > 0) << endl;
 return x < 0 || sum > 0;
}

int main()
{
 std::cout.setf(std::ios::boolalpha);

 int m=INT_MAX;
 cout << " (x < 0) or (sum > 0) is: " << foo(m) << endl;

 system("PAUSE");
 return 0;
}

Насправді, така програма могла виконуватися по іншому, але у всіх випробуваних випадках результат виклику функції співпадав із результатом для програми вище.

Однак була помічена цікава особливість. Програма, якщо вчитатися --- не зовсім коректна. Вивід її залежатиме від порядку обчислення аргументів операторів. Тому, вона може виводити як (заплановане, але некоректно реалізоване):

x = 2147483647
sum = -2147483647
x<0 : false
sum>0 : false
 (x < 0) or (sum > 0) is: false

так і цілком законне:

  (x < 0) or (sum > 0) is: x = 2147483647
sum = -2147483647
x<0 : false
sum>0 : false
false

Тепер видно, де помилка? ;-)

Так ось:

• gcc 3.4.6, лише із опціями -O3, -O2, -Os, 
• clang 3.2, з будь-якими опціями, включаючи -O0,
• icc, з будь-якими опціями, включаючи -O0,

вивели другий варіант, всі інші комбінації версій компіляторів та їх опцій, включаючи gcc 3.4.6 без опцій та з -O1, вивели перший.

Як би там не було, НЕ ПИШІТЬ ТАК!

Додаток 3 - Upd 2018-06-24

Дуже давно було цікаво, чи є актуальні архітектури, які користуються для від'ємних цілих чисел не доповнювальним кодом (two's complement). В пропозиції на стандартизацію трапився огляд: Signed Integers are Two’s Complement: Survey of Signed Integer Representations.

Єдиною умовно живою є: UNIVAC_1100/2200, і то, цитуючи: "In short, the only machine the author could find using non-two’s complement are made by Unisys, and no counter-example was brought by any member of the C++ standards committee. Nowadays Unisys emulates their old architecture using x86 CPUs with attached FPGAs for customers who have legacy applications which they’ve been unable to migrate." (Див. також список за посиланням -- там також про DSP пише, на них була певна "надія").