?

Log in

No account? Create an account

Удивительное рядом, но оно не определено - Общество дровосеков Бердичева по изучению Мишны

Oct. 13th, 2016

12:39 am - Удивительное рядом, но оно не определено

Previous Entry Share Next Entry

Задачка для оптимизирующих программистов (по крайней мере на C++)

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

    int *p = (int*)malloc(4);
    int *q = (int*)realloc(p, 4);
    *p = 1;
    *q = 2;
    if (p == q) {
        printf("%d %d\n", *p, *q);
    }

Comments:

[User Picture]
From:yigal_c
Date:October 13th, 2016 08:18 am (UTC)
(Link)
Строго говоря, будет всё что угодно в пределах возможностей компьютера.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 13th, 2016 02:50 pm (UTC)
(Link)
Нет, если оптимизации будут выполнены, то всё undefined behavior будет ликвидировано.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:krakozabr
Date:October 13th, 2016 08:21 am (UTC)

Хм

(Link)
Я не оптимизирующий программист.

Но доступные мне (различные) компиляторы делали одно и то же:

2 2
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 13th, 2016 02:49 pm (UTC)

Re: Хм

(Link)
Внизу febb пишет, что уже доступен компилятор, делающий подразумеваемую оптимизацию ("1 2").
(Reply) (Parent) (Thread)
[User Picture]
From:b0p0h0k
Date:October 13th, 2016 08:22 am (UTC)
(Link)
Не вижу причин для не "2 2".

Оговорка: я не сильно много знаю про xx-rated C, так что глядел на это в парадигме C.

Edited at 2016-10-13 08:31 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 13th, 2016 02:48 pm (UTC)
(Link)
Очень может быть, что и в режиме какого-нибудь нового С оптимизация будет та же, и получится "1 2". Вопрос для размышления: что именно разрешает компилятору так сделать?
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:October 13th, 2016 08:22 am (UTC)
(Link)
Жулики. Комитетчики и компиляторщики. UB со всеми вытекающими.

Кстати, ролик вышел некоторое время назад (блин, там столько вывалили! смотреть - не пересмотреть), можно было не ходить, а смотреть тюбик в халате и тапках, попивая чай.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 13th, 2016 02:47 pm (UTC)
(Link)
Это мы знаем, что формально там есть UB, а компилятор этого не знает, и стандарт ему говорит думать про другое, отсюда и все лулзы.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:febb
Date:October 13th, 2016 11:04 am (UTC)
(Link)
Наверное realloc оставит всё как есть.
Тогда программа напечатает: "2 2\n"
(Reply) (Thread)
[User Picture]
From:febb
Date:October 13th, 2016 11:15 am (UTC)
(Link)
Интересно что с оптимизацией оно напечатало "1 2\n"
Забавно)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:yurikhan
Date:October 13th, 2016 11:15 am (UTC)
(Link)

Отыгрываю Omniscient Omnipotent Lawful Evil компилятор. Предполагаю sizeof(int) ≤ 4, иначе всё ещё интереснее.

В первой строчке malloc может вернуть nullptr, если памяти нет, или ненулевой указатель на область памяти не менее 4 байт.

Во второй строчке realloc может вернуть (a) nullptr, если p == nullptr и памяти всё ещё нет; (b) указатель p; или же (c) указатель, отличный от p, если реализация стандартной библиотеки не связана ограничением делать все разрешённые оптимизации. В последнем случае указатель p становится невалидным.

В третьей строчке делается разыменование указателя p без проверки, что он не нулевой и валидный, варианты (a) и (c) ведут к UB.

В качестве разрешённой оптимизации предполагаем, что UB не происходит — память всегда есть, а realloc не реаллочит по пустякам. Далее везде считаем, что p == q.

Раз p == q, то запись единицы в третьей строке избыточна. Выоптимизируем её.

В четвёртой строке пишем двойку, если escape-анализ покажет, что значение указателя p или q куда-то выходит из рассматриваемого фрагмента. Если же не выходит, то никто не может легально получить доступ к этой памяти, поэтому запись в память тоже выоптимизируем, а в следующих трёх строчках будем делать вид, что записали.

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

В шестой строке память не читаем. Используем тот факт, что мы только что сделали вид, что записали туда двойку, а переменная не volatile. Форматную строку "%s %s\n" в объектник не пишем, поскольку результат форматирования известен на этапе компиляции. Вызов printf заменяем на puts("2 2\n").

(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 13th, 2016 02:44 pm (UTC)
(Link)
Канва рассуждения правильная, но некоторые детали отсутствуют, поэтому вывод неправильный. На самом деле будет "1 2\n", как уже получилось у febb выше.
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:October 13th, 2016 03:38 pm (UTC)
(Link)
Придумал только такой вариант, который требует извращенного оптимизатора, который «ошибается» в предположениях. Он знает, что размер для realloc() такой же, как у заведенного ранее указателя, поэтому (вообще говоря, ошибочно (?)) предполагает, что realloc() не перемещает указатель. Тогда (корректный вывод) будет выполнено условие p == q, и if можно выбросить. Правда, еще придется предположить, что первый malloc() никогда не возвратит NULL, это уж не знаю, почему может быть (например, оптимизатор заметит, что указатели нигде далее налево не ходят, поэтому можно заменить аллокацию в куче на аллокацию на стеке). Но в реальном запуске выясняется, что (1) оптимизатор ошибся в первом предположении, (2) после освобождения p страница не сдохла, поэтому его можно разыменовывать без сегфолта. Поэтому печатается "1 2".
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 13th, 2016 03:51 pm (UTC)
(Link)
Если компилятор предполагает, что realloc не перемещает указатель, то он, максимально оптимизируя в соответствии с этим предположением, будет обязан выбросить *p = 1.
(Reply) (Parent) (Thread)
[User Picture]
From:ormuz
Date:October 13th, 2016 03:41 pm (UTC)
(Link)
Strict aliasing rule!

Компилятор может не думать о реаллоке и предпооагает q отдельной областью памяти
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 13th, 2016 03:49 pm (UTC)
(Link)
p и q одного типа, поэтому strict aliasing rule не при делах, но направление мысли правильное.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:October 15th, 2016 09:16 pm (UTC)
(Link)
А вот это интереснее.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main(void)
{
  int* p = malloc(sizeof(int));
  uintptr_t ap = (uintptr_t)p;
  int* q = realloc(p, sizeof(int));
//  *p = 1;
  *(int*)ap = 1;
  *q = 2;
//  if (p == q)
  if ((int*)ap == q)
  {
//    printf("%d %d\n", *p, *q);
    printf("%d %d\n", *(int*)ap, *q);
  }
  return 0;
}



Edited at 2016-10-15 09:20 pm (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 15th, 2016 09:58 pm (UTC)
(Link)
Ты б говорил, что печатается.

В принципе, любое поведение компилятора можно объяснить фразой "изощрён, но не злонамерен".
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:dvv
Date:October 16th, 2016 12:38 am (UTC)
(Link)
Идеальный компилятор должен выдать ошибку компиляции, соптимизировав время выполнения и футпринт программы до нуля.

Edited at 2016-10-16 12:40 am (UTC)
(Reply) (Thread)