?

Log in

темные закоулки языка C - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

темные закоулки языка C [мар. 9, 2013|02:48 pm]
Anatoly Vorobey
Some dark corners of C

Набор забавных малоизвестных особенностей C. Самый интересный пример там, на мой взгляд - следующие две функции:
void foo1(int *x, int *y, int *z) {
  *x += *z;
  *y += *z;
}

void foo2(int *x, int *y, int *z) {
  int w = *z;
  *x += w;
  *y += w;
}


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

Правильный ответ: [Нажмите, чтобы прочитать]в первом случае компилятор не может исключить возможность того, что x==z.

Я также не знал, что в C99 есть ключевое слово restrict, которое решает эту проблему.
СсылкаОтветить

Comments:
[User Picture]From: pphantom
2013-03-09 12:53 pm
Я бы не назвал ее малоизвестной. Программисты, которым нужно выжимать максимальную производительность из кода, обычно об этом знают. А приведенный пример (и исправление ситуации с помощью restrict) - чуть ли не главная причина меньшей производительности Си по сравнению с Фортраном в вычислительных задачах.
(Ответить) (Thread)
[User Picture]From: avva
2013-03-09 12:57 pm
Таких программистов относительно мало.

Ну и вообще - анти-интуитивные вещи забываются или не приходят на ум. Программист знает, что конечно же x!=z, и для того, чтобы помнить, что компилятор об этом не знает, нужна ментальная дисциплина. Скажу про себя: я хорошо знаю об этой проблеме теоретически, даже сталкивался с ней раз или два практически, оптимизируя какой-то код (очень давно), и все равно во время чтения этой презентации заново удивился.
(Ответить) (Parent) (Thread)
[User Picture]From: vodianoj
2013-03-09 09:20 pm
Программист, разработчик функции, как мне кажется, так же как и компилятор не знает, что x!=z.
Если программист, хотел сделать то, что делает фу2 и при этом он написал фу1, то это просто баг потому, что в случаях, когда x==y эти функции ведут себя по разному. Меньшая эффективность тут как раз наименьшая из возможных проблем.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-10 08:18 am
Это функция слабенькая, только для примера. Настоящие функции — это перемножение матриц, например, 100500 х 100500. А теперь внимание, вопрос: как такую функцию написать? Как foo1 или как foo2?
(Ответить) (Parent) (Thread)
[User Picture]From: vodianoj
2013-03-11 06:15 am
В таком случае я бы не выделял это в отдельную функцию - лишняя строчка кода, но не будет потенциального бага.
(Ответить) (Parent) (Thread)
[User Picture]From: igorlord
2013-03-09 01:15 pm
The possibility of aliasing seems like a rather obvious everyday concern.

In any case, both examples show a somewhat defective C code that I would not pass on a code review. When *z is not intended to be modified, I would insist that it is marked as const. I do wonder if that const would cause the compiler to assume no aliasing. Something I may want to try...
(Ответить) (Thread)
[User Picture]From: salas
2013-03-09 02:31 pm
Checked on gcc 4.7.2 (Ubuntu amd64), doesn't look like that. If *b after foo1(a, b, a) depended on that const, this corner would be even darker.
(Ответить) (Parent) (Thread)
[User Picture]From: deadkittten
2013-03-09 01:22 pm
Добавлю, что gcc с опциями -O3 или -O4 начинает "самовольно" догадываться, верно ли, что x==z . Иногда это приводит к малопонятным ошибкам.
(Ответить) (Thread)
[User Picture]From: panikowsky
2013-03-09 01:25 pm
Если заголовок Вашего поста - это перевод названия презентации, то он не совсем точен: мне кажется, "dark corners of C" лучше перевести как "темные закоулки языка C".
(Ответить) (Thread)
[User Picture]From: avva
2013-03-09 01:31 pm
да, вы правы, спасибо. Мне не пришел в голову хороший аналог dark corners. Сейчас изменю на ваш вариант.
(Ответить) (Parent) (Thread)
[User Picture]From: hryu
2013-03-09 01:32 pm
Да, как-то не сообразил :)
(Ответить) (Thread)
[User Picture]From: _winnie
2013-03-09 01:48 pm
> компилятор генерирует более эффективный код для второй из них, foo2
Нужна оговорка, "обычно генерирует" :) У меня тут вчера было волшебство - "менее эффективный" код с assert-тами работает быстрее чем оптимизированная версия без них. http://users.livejournal.com/_winnie/379152.html
(Ответить) (Thread)
[User Picture]From: kot_begemot
2013-03-09 02:06 pm
Потому что кладёт w в регистр и лазает в память за значением *z один раз, а не два.
(Ответить) (Thread)
[User Picture]From: penguinny
2013-03-09 02:20 pm
Опыт работы в ассемблере даёт это знание самым непосредственным образом. Кстати, тесно связанный трюк в ассемблере Z80 служил как один из самых быстрых (и точно самый компактный) способ очистки экрана:

ld hl,screen_addr
ld de,screen_addr+1
ld bc,6143
ld (hl),0
ldir

Команда ldir копирует bc байт информации, начинающейся с адреса hl, в блок памяти, начинающийся с адреса de. С учётом выбранных адресов, 0 вручную пишется в первый байт, а затем копируется из первого во второй, из второго в третий, и т.д. Экран очищается по индукции.

Про ещё более быстрый способ очистки экрана я лучше рассказывать не буду.
(Ответить) (Thread)
[User Picture]From: kray_zemli
2013-03-09 04:13 pm
говорят, как-то через стек можно ещё было. вы его имели в виду?
(Ответить) (Parent) (Thread)
[User Picture]From: penguinny
2013-03-09 04:31 pm
Да, именно так. Регистр стека устанавливался в конце экрана, один из 16-битных регистров очищался и затем в частично развёрнутом цикле многократно сохранялся в стек. 16-битные операции на 8-битном процессоре! Шок.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-03-09 02:40 pm
Я этого не видел раньше, кажется. Красиво!
(Ответить) (Parent) (Thread)
[User Picture]From: gdy
2013-03-10 09:26 am
А почему очень сильный-то?
Не сильнее const - если бы у потока не было оператора для const char*, а только для char*, та же ситуация бы была, нет?
(Ответить) (Parent) (Thread)
[User Picture]From: alex_vinokur
2013-03-10 10:05 am
Да, скорее всего, так.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-10 09:44 pm
Сильный потому, что оператор для const char* есть ;)
(Ответить) (Parent) (Thread)
From: qehgt
2013-03-09 04:40 pm
Ещё можно написать "const int* z" в параметрах, это позволит компилятору считать, что "*z" не будет меняться при работе с "*x" и "*y"
(Ответить) (Thread)
From: huzhepidarasa
2013-03-09 05:30 pm
Не позволит. "const int* z" означает только, что *z не может меняться через z.
(Ответить) (Parent) (Thread)
From: qehgt
2013-03-09 05:48 pm
Позволит. Могу место в Стандарте показать.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-09 05:58 pm
Покажите.


void foo(int *x, int *y, const int *z) {
*x += *z;
*y += *z;
}

int xx = 3, yy = 4;

void bar()
{
foo(&xx, &yy, &xx);
}


Что говорит Стандарт по этому поводу?

Edited at 2013-03-09 18:03 (UTC)
(Ответить) (Parent) (Thread)
From: qehgt
2013-03-09 06:12 pm
Пожалуй, был не прав.
(Ответить) (Parent) (Thread)
[User Picture]From: yms
2013-03-09 05:07 pm
надо же, не знал, сколько чудес кроется за C99...
причем не все из них вошли в C++, даже 11.

Edited at 2013-03-09 17:09 (UTC)
(Ответить) (Thread)
[User Picture]From: pphantom
2013-03-09 05:29 pm
В С99 действительно много весьма полезных добавлений, причем они удачно дополняют язык, не меняя его идеологии. C++ дополнялся намного хуже, превратившись в громадную солянку из всего подряд.
(Ответить) (Parent) (Thread)
From: asox
2013-03-09 09:44 pm
С99 шёл своим путём, отдельным от С++
(Ответить) (Parent) (Thread)
[User Picture]From: yms
2013-03-10 02:01 am
Да теперь уж понятно... Я чистым си перестал интересоваться году в 1992 :)
(Ответить) (Parent) (Thread)
From: asox
2013-03-10 09:31 am
Ну я тоже, собснна. Так только слышал краем уха.
С99 вообще странно существует - почти как f77, f90 и т.д.
(Ответить) (Parent) (Thread)
[User Picture]From: andybil
2013-03-09 07:18 pm

Гавно

Из вашего поста следует, что за время от создания Си до сего дня ничего в программировании не сделано, даже Фортран не обогнали, тоесть идёт деградация.

Спасибо за откровенность.
Я с этим согласен. Например, найдите картинку в Гугле "Одноногий мужик в шляпе" и посмотрите сто первых результатов. Сразу видно достижения функционального программирования и прочего компьютерсаенс: полное гавно.
(Ответить) (Thread)
[User Picture]From: migmit
2013-03-09 09:15 pm
Не знаю, сообразил бы я про x==z (я читаю через RSS, и ответ успел увидеть до того, как задумался над вопросом), но точно знаю, что на практике я бы написал второй вариант, а не первый. Просто потому, что дважды разыменовывать один указатель — некрасиво. К тому же, компиляторы C и C++ я привык a priori считать экстремально тупыми, и даже не задумываюсь над такими оптимизациями.
(Ответить) (Thread)
From: asox
2013-03-09 09:47 pm
О!
+100500
А в общем случае - фиг знает что и как соптимизирует компилятор, и подгонять код под оптимизацию конкретной версии конкретного компилятора - извращение.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-10 08:14 am
От этой привычки надо бы потихоньку отказываться. Компиляторы нонче оптимизируют лучше среднего программиста.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-03-10 09:27 am
Как показывает исходный пост — не надо.

Другой вопрос, что к оптимизации надо подходить грамотно, сначала делая профайлинг.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-10 04:36 pm
Нет, не показывает. Он показывает, если он что-то показывает, что программист, не задумываясь, вносит «оптимизации», меняющие смысл программы. А компилятор нет.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-03-10 04:54 pm
Ну как — не показывает. Если от привычки не отказываться, то в подобную ловушку не попадаешь.

Другой вопрос, что, опять-таки, для меня основной критерий — это не тупость компилятора, а "некрасиво".
(Ответить) (Parent) (Thread)
[User Picture]From: mopexod
2013-03-10 08:44 am
Вот же ж, пардон, блядь какая, это компилятор! Да нахер он об этом думает? Это же замена однгого side-effect-а на другой. Причем, если первый еще можно отладить, но на втором будешь тупить два часа, не веря в такое вероломство.
(Ответить) (Thread)
[User Picture]From: migmit
2013-03-10 09:27 am
Эм... чего?
(Ответить) (Parent) (Thread)
[User Picture]From: mopexod
2013-03-10 09:48 am
Посмотрел внимательно и понял: херню написал.
(Ответить) (Parent) (Thread)
From: Alex P
2013-03-10 03:19 pm
А если после int w = *z; написать x = &w; компилятор догадается что w изменится в первом суммировании и его во втором брать из регистра нельзя а только из памяти?
(Ответить) (Thread)
[User Picture]From: avva
2013-03-10 03:20 pm
Да, конечно.
(Ответить) (Parent) (Thread)