LINUX.ORG.RU

Вопрос по поводу «Неопределённого Поведения» в языке Си


0

0

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

int a,b;

a=1;

b=(a++) + (5*a++);

Если добавить в язык правило, которое гарантирует порядок вычислений операндов "слева направо", то неопределённость пропадает. Насколько это ухудшит возможности оптимизации?

При текущем стандарте мне нужно вводить дополнительную (временную) переменную для устранения неопределённости. Это не совсем удобно.

int a,b, temp;

a=1;

temp=a++;

b=temp + (5*a++);

anonymous

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

А так не прокатит?

int a, b;
a = 1;
a++;
b = a + 5 * a;

andreyu ★★★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

int a,b;
a=1;
b=a + 5 * (a + 1); 
a += 2

может так?

Legioner ★★★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> может так?

Черт, соврал таки. Да, это правильно. Но не оптимально. Хотя очень много зависит от AI компилятора.

eugine_kosenko ★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

Если речь идёт об оптимизации на уровне +-1 машинной команды, С плохо для этого подходит.

Legioner ★★★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> А так не прокатит?

Нет. Мой пример приведен от фонаря, но могут быть варианты, в которых имеет смысл делать два инкремента. Например, в языке C++ (хотя мой вопрос по обычному Си) я могу не знать точно действия функции-члена. Она может сохранять своё состояние между вызовами.

Меня интересует насколько будут хуже возможности для оптимизации, если принять более чёткие правила порядка вычислений?

anonymous ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

Откуда вообще взялась эта фраза

>разработчики языка Си умышленно оставили "неопределённость"

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

Особенно вторая часть? Педивикия говорт, что

> In computer science, undefined behavior is a feature of some programming languages — most famously C. In these languages, to simplify the specification and allow some flexibility in implementation, the specification leaves the results of certain operations specifically undefined.

...чтобы упростить спецификации и позволить гибкость в имплементации...

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

Uncle_Theodore ★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> Например, вот фрагмент кода.
>
> int a,b;
>
> a=1;
>
> b=(a++) + (5*a++);
>
> Если добавить в язык правило, которое гарантирует порядок вычислений операндов "слева направо", то неопределённость пропадает. Насколько это ухудшит возможности оптимизации?

Это неправда, между прочим. Неопределённость ещё и в том, что side effects могут вычисляться в любое время, и от определённого порядка общая неопределённость не пропадёт. Т.е. операция i++ внутри выражения не атомарна.

Legioner ★★★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

Не совсем понятно о какой неопределенности идет речь ? Вроде все определенно - операции одного ранга выполняются в соответствии с правилом ассоциативности - для префиксной справа, для постфиксной слева. Для операции () слева. Или я не о том ?

koTuk ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> Но не оптимально. Хотя очень много зависит от AI компилятора.

фактически то что нужно сделать -- это простое линейное
преобразование -- такие вещи по моему стоит поручать
оптимизироать компилятору.

например gcc сам способен определить несовместность
некоторых простейших линейных выражений, типа:

if (x > 1)
{
  if (y > 1 && x + y < 1)
  {
     impossible;
  }
}

dilmah ★★★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

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

koTuk ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> Не совсем понятно о какой неопределенности идет речь ?

стандат специфициует что между sequence points нельзя больше одного раза модифициовать один объект

dilmah ★★★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

Тогда это не неопределенность а ошибка - а автор топика провакатор ;) Пишите понятные конструкции тем более что на таком коде нечего оптимизировать.

koTuk ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

На правах личного мнения.

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

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

> При текущем стандарте мне нужно ... Это не совсем удобно.

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

В стиле языка высокого уровня, инкремент в примере стоило бы сделать явно, а не пихать всё в одну строку. В стиле низкоуровневого хака стоило бы сразу расписать всё, что надо, и сделать b=6*a+чтото; a+=сколькото. Кстати, Ваш код компилятор успешно заменит на int a=const, int b=const, т.ч. пример сомнительный.

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

Если хотите выдуманный пример - пожалуйста: посчитать div(f(),g()), где f() и g() - некомутативные функции, в стековой модели вызовов. Получим что-то типа

call g; will push g() result to stack
call f; will push f() result to stack
call div; will take 2 args from stack and put 1 arg to stack

Здесь переставить вызовы нельзя, т.к. операция div принимает аргументы именно в этом порядке. Если навязать порядок вызова, придётся ставить лишние операции по перестановке аргументов.

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

alexsaa ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> Не совсем понятно, о какой неопределенности идет речь? ... это не неопределенность, а ошибка

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

> Откуда вообще взялась эта фраза "разработчики языка Си умышленно оставили неопределённость"

Вот цитата "The reason some behavior has been left undefined is to allow the compiler to generate more efficient executable code for well-defined behavior". Источник.

http://en.wikipedia.org/wiki/Criticism_of_the_C_programming_language#Undefine...

> хорошо работать, а не записывать то, что он делает, самым кратким образом.

Вы правы, но в 1981-м году Брайан Керниган приводил очень похожий аргумент против языка Pascal (смотрите раздел Flow Control в его статье Why Pascal is not my favorite language). В старом Pascal-е не было гарантий для порядка логических вычислений (не было таких правил как в Си для || и &&). В результате часто нужна дополнительная временная переменная.

Преимущества чёткого порядка вычислений очевидны:

1) код более понятен

2) код более предсказуем (не всегда есть время изучать тонкости)

Меня же интересуют недостатки чёткого порядка вычислений. Они вообще есть?

anonymous ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> не было гарантий для порядка логических вычислений

Кстати, Керниган назвал это "смерть от тысячи мелких порезов, а не от одного удара в жизненно важную точку".

anonymous ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

>>>b=(a++) + (5*a++);

>> Не совсем понятно, о какой неопределенности идет речь? ... это не неопределенность, а ошибка

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

Высасываете проблему из пальца. Что вам не понятно - в каком порядке будет вычисляться выражение ? Первыми вычисляются операции с наивысшим приоритетом - это скобки - у них ассоциативность слева направа - так с какого перепугу компилятор должен начинать вычислять опреанды для вторых скобок которые справа да еще выполнять при этом операцию с меньшим приоритетом ?

koTuk ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

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

anonymous ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

>koTuk, вы вообще не понимает, о чём идёт разговор. Почитайте внимательно стандарт языка Си. Я пытаюсь обсудить не приоритет операций, а порядок вычисления их операндов.

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

koTuk ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

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

Я так и сделал в своём вопросе (у меня же там два фрагмента кода). Но это требует введения дополнительных переменных. И я уже выше писал вот это.

"в 1981-м году Брайан Керниган приводил очень похожий аргумент против языка Pascal (смотрите раздел Control Flow в его статье Why Pascal is not my favorite language). В старом Pascal-е не было гарантий для порядка логических вычислений (не было таких правил как в Си для || и &&). В результате часто нужна дополнительная временная переменная."

"смерть от тысячи мелких порезов, а не от одного удара в жизненно важную точку"

anonymous ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

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

koTuk ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> что вы там определели промежуточную переменную еще не значит что компилятор ее действительно создаст

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

anonymous ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> Ну, в статье у Кернигана был пример для Pascal-я while (i <= XMAX) and (x[i] > 0) do ...

не понял связи. Да, для && и || введены спецправила early out, потому что это очень часто встречается на практике. В принципе такое же правило можно ввести и для умножения (early out если первый аргумент ноль), но это нужно гораздо меньше и будет только путать народ.

dilmah ★★★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

dilmah, причина может быть любой. Пример.

1) функция f() сохраняет своё состояние между вызовами и при этом

2) чётные вызовы для меня в пять раз важнее нечётных (по какой угодно причине, алгоритм такой).

В итоге проще всего будет

f()+5*f();

anonymous ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

хорошо. Тогда я тебе могу только помочь с красивым названием для временной переменной: acc или accum:)

dilmah ★★★★★ ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

> Тогда я тебе могу только помочь с красивым названием

Это и так было понятно. А есть ли конкретные примеры, когда второй операнд выгоднее вычислять раньше первого?

anonymous ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

>> что вы там определели промежуточную переменную еще не значит что компилятор ее действительно создаст

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

Я так понял по тексту что вы видимо и к с++ имеете отношение тогда скажите мне - зачем вы создаете какие то свои классы ? они же не существуют реально но в исходном тексте они есть - они тоже затрудняют чтение программы ?

koTuk ()

Re: Вопрос по поводу "Неопределённого Поведения" в языке Си

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

Чтобы не было сомнений по поводу оптимизации привожу ваш пример:

bash-3.2$ cat 2.c
//#!/usr/local/bin/tcc -run

#include <stdio.h>

int main (void) 
{

    int a, b, temp;

    a = 1;
    temp = a++;
    b = temp + (5*a++);

    printf("a = %i\n", a);
    printf("b = %i\n", b);

    return(0);
}

bash-3.2$ gcc -O3 2.c
bash-3.2$ ./a.out
a = 3
b = 11

bash-3.2$ gcc -O3 -S 2.c
bash-3.2$ cat 2.s
        .file   "2.c"
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "a = %i\n"
.LC1:
        .string "b = %i\n"
        .text
        .p2align 4,,15
.globl main
        .type   main, @function
main:
        leal    4(%esp), %ecx
        andl    $-16, %esp
        pushl   -4(%ecx)
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ecx
        subl    $20, %esp
        movl    $3, 4(%esp)
        movl    $.LC0, (%esp)
        call    printf
        movl    $11, 4(%esp)
        movl    $.LC1, (%esp)
        call    printf
        addl    $20, %esp
        xorl    %eax, %eax
        popl    %ecx
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
        .size   main, .-main
        .ident  "GCC: (GNU) 4.2.4 (CRUX)"
        .section        .note.GNU-stack,"",@progbits

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

koTuk ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.