Доброго времени суток, коллеги.

После напряженного рабочего дня возник философский вопрос — а почему разработчикам компилятора нельзя создать compile-time GC? Неужели (теоретически) компилятор не может определить границ использования тех или иных объектов и сгенерировать код корректного удаления объектов в подходящие моменты? Ведь программист выполняет ту же работу. Или такое уже есть?

Сорри за наивность, если у кого-нибудь есть линки на серьезную литературу (работы Boehm'a?) по этому поводу ткните носом.

Здравствуйте, StevenIvanov, Вы писали:

SI>а почему разработчикам компилятора нельзя создать compile-time GC? Неужели (теоретически) компилятор не может определить границ использования тех или иных объектов и сгенерировать код корректного удаления объектов в подходящие моменты?

А как будет работать хрестоматийный пример с сериализацией указателей в файл, и последующей десирализацией их оттуда для дальнейшего использования?

Здравствуйте, StevenIvanov, Вы писали:

SI>Доброго времени суток, коллеги.

SI>После напряженного рабочего дня возник философский вопрос — а почему разработчикам компилятора нельзя создать compile-time GC? Неужели (теоретически) компилятор не может определить границ использования тех или иных объектов и сгенерировать код корректного удаления объектов в подходящие моменты? Ведь программист выполняет ту же работу. Или такое уже есть?

SI>Сорри за наивность, если у кого-нибудь есть линки на серьезную литературу (работы Boehm'a?) по этому поводу ткните носом.

Интересный вопрос.

{
entry = Entry()
if get_magic_result():
   handle_entry( entry );
}

И как тут можно определить?

Здравствуйте, StevenIvanov, Вы писали:

SI>Доброго времени суток, коллеги.

SI>После напряженного рабочего дня возник философский вопрос — а почему разработчикам компилятора нельзя создать compile-time GC? Неужели (теоретически) компилятор не может определить границ использования тех или иных объектов и сгенерировать код корректного удаления объектов в подходящие моменты? Ведь программист выполняет ту же работу. Или такое уже есть?

SI>Сорри за наивность, если у кого-нибудь есть линки на серьезную литературу (работы Boehm'a?) по этому поводу ткните носом.


Такое уже есть — называется escape analysis. Уже применяется в Java. Но работает он только для примитивных случаев. Типа такого:

void f()
{
  Object o = new Object();

  // здесь что-то делаем, но указатель на 'o' никуда не передаём

  // здесь можем безопасно разрушать объект 'o'
}

В таком коде компилятор может разместить объект "на стеке", несмотря на то, что формально такого ("на стеке") в Java нет.

Для более нетривиальных случаев это работать не будет. Т.к. статический control-flow sensitive анализ программы невозможен. Фактически компилятору придётся все время принимать самое пессимистическое решение, что объект может жить дольше. И всё становится ещё печальнее, когда в игру входит многопоточное окружение. Это сводит на нет идею.

Здравствуйте, StevenIvanov, Вы писали:

SI>... Ведь программист выполняет ту же работу.

Это же не аргумент, программист много чего выполняет, не только работу GC.

Здравствуйте, StevenIvanov, Вы писали:

SI>Сорри за наивность, если у кого-нибудь есть линки на серьезную литературу (работы Boehm'a?) по этому поводу ткните носом.
Подобная схема реализована в Cyclone (http://en.wikipedia.org/wiki/Cyclone_programming_language), называется region inference (http://en.wikipedia.org/wiki/Region_inference).

На практике, оно слишком пессемизирует программу во многих случаях и требует из-за этого ручной помощи (типа расстановки refcounted-указателей, которые грешат циклическими ссылками).

Здравствуйте, remark, Вы писали:

R>...

Ясно. Я правильно понял, что это — NP-полная задача и в принципе существующим математическим аппаратом в computer science ее решить нельзя? Это уже доказано, я так понимаю?

StevenIvanov wrote:

> Ясно. Я правильно понял, что это — NP-полная задача и в принципе
> существующим математическим аппаратом в computer science ее решить
> нельзя? Это уже доказано, я так понимаю?
Мне кажется, что это вообще алгоритмически неразрешимая задача, типа проблемы останова.
Скажем

if(какая_нибудь_сложная_математическая_теорема_верна())
{
    удалить_объект();
}

и что? Компилятор должен уметь доказывать любую теорему?

Здравствуйте, ., Вы писали:

.>и что? Компилятор должен уметь доказывать любую теорему?
Зачем? Просто принимаем самое консервативное решение.

Здравствуйте, Daevaorn, Вы писали:

D>

D>{
D>entry = Entry()
D>if get_magic_result():
D>   handle_entry( entry );
D>}
D>

D>И как тут можно определить?

Если entry — это не указатель, а полноценный объект и метод handle_entry в качестве входного параметра принимает именно объект а не ссылку или указатель, то можно.

Cyberax wrote:

> .>и что? Компилятор должен уметь доказывать любую теорему?
> Зачем? Просто принимаем самое консервативное решение.
Может я его не так понял, я думал он хочет точное решение. Иначе чем поможет даже если это NP? Тут ведь даже полный перебор никак не поможет.

Здравствуйте, GGoga, Вы писали:

GG>Здравствуйте, Daevaorn, Вы писали:

D>>

D>>{
D>>entry = Entry()
D>>if get_magic_result():
D>>   handle_entry( entry );
D>>}
D>>

D>>И как тут можно определить?

GG>Если entry — это не указатель, а полноценный объект и метод handle_entry в качестве входного параметра принимает именно объект а не ссылку или указатель, то можно.

Рассмотрим случай ссылок.

Здравствуйте, Alxndr, Вы писали:

A>Здравствуйте, StevenIvanov, Вы писали:

SI>>а почему разработчикам компилятора нельзя создать compile-time GC? Неужели (теоретически) компилятор не может определить границ использования тех или иных объектов и сгенерировать код корректного удаления объектов в подходящие моменты?

A>А как будет работать хрестоматийный пример с сериализацией указателей в файл, и последующей десирализацией их оттуда для дальнейшего использования?

приведите пожалуйста достаточный пример псевдокода.

Здравствуйте, Daevaorn, Вы писали:

D>Здравствуйте, StevenIvanov, Вы писали:

SI>>Доброго времени суток, коллеги.

SI>>После напряженного рабочего дня возник философский вопрос — а почему разработчикам компилятора нельзя создать compile-time GC? Неужели (теоретически) компилятор не может определить границ использования тех или иных объектов и сгенерировать код корректного удаления объектов в подходящие моменты? Ведь программист выполняет ту же работу. Или такое уже есть?

SI>>Сорри за наивность, если у кого-нибудь есть линки на серьезную литературу (работы Boehm'a?) по этому поводу ткните носом.

D>Интересный вопрос.

D>

D>{
D>entry = Entry()
D>if get_magic_result():
D>   handle_entry( entry );
D>}
D>

D>И как тут можно определить?

ну если я правильно понял имелось в виду нечто следующее:

{
  Entity * e = new Entity();
  if( getMagicResult() )
  {
    handleEntity( e );
  }
  // а здесь почему нельзя удалять e?
}

Естественно такой подход не сработает, если getMagicResult возвращает случайный результат, а handleEntity сохраняет e к примеру в глобальных переменных.
Но в таком случае возможно было бы компилятору сгенерировать следующий псевдокод:

{
  Entity * e = new Entity();
  bool generated_flag = true;
  if( getMagicResult() )
  {
    handleEntity( e );
    generated_flag = false;
  }
  if( generated_flag )
  {
     delete e;
  }
}

и дальше продолжать в том же духе в функции handleEntity?

Согласен, накладные расходы будут в runtime, однако их будет существенно меньше чем весь runtime GC

Здравствуйте, igna, Вы писали:

I>Здравствуйте, StevenIvanov, Вы писали:

SI>>... Ведь программист выполняет ту же работу.

I>Это же не аргумент, программист много чего выполняет, не только работу GC.

Вроде бы да, но не совсем. Ведь сделали же runtime GC чтобы программист такой работы не выполнял.

Здравствуйте, StevenIvanov, Вы писали:

SI>Естественно такой подход не сработает, если getMagicResult возвращает случайный результат, а handleEntity сохраняет e к примеру в глобальных переменных.
SI>Но в таком случае возможно было бы компилятору сгенерировать следующий псевдокод:

SI>

SI>{
SI>  Entity * e = new Entity();
SI>  bool generated_flag = true;
SI>  if( getMagicResult() )
SI>  {
SI>    handleEntity( e );
SI>    generated_flag = false;
SI>  }
SI>  if( generated_flag )
SI>  {
SI>     delete e;
SI>  }
SI>}
SI>

SI>и дальше продолжать в том же духе в функции handleEntity?
SI>Согласен, накладные расходы будут в runtime, однако их будет существенно меньше чем весь runtime GC


Это уже референс-каунтинг. Таким подходом (если его обобщить — приделать к каждому объекту счётчик ссылок) можно обрабатывать большинство ситуаций (в т.ч. и в многопоточном приложении). При этом естественно, если среда обещает собирать и циклический мусор, то и традиционный полнометражный GC тоже нужен как напарник-подстаховшик.

Здравствуйте, StevenIvanov, Вы писали:

SI>Ясно. Я правильно понял, что это — NP-полная задача и в принципе существующим математическим аппаратом в computer science ее решить нельзя? Это уже доказано, я так понимаю?

Дело не в NP-полноте, а в недетерминизме — время жизни объектов может зависеть от сигналов с какого-нибудь датчика, который нельзя предсказать просто по законам физики. Из-за этого придется рассчитывать только на худшие случаи, что на практике приведет к отказу от удаления объектов вообще. Например у компилятора нет причин считать невозможным, что юзер не поместит мышку только на одну из кнопок и больше никогда её оттуда не уведет — из-за этого картинка, создаваемая при наведении, вынуждена была бы жить вечно, даже если компилятор проведет весь NP-полный анализ.

По этой же причине не может существовать наилучшего оптимизатора, работающего в compile-time.

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

Здравствуйте, remark, Вы писали:

R>Здравствуйте, StevenIvanov, Вы писали:

SI>>Естественно такой подход не сработает, если getMagicResult возвращает случайный результат, а handleEntity сохраняет e к примеру в глобальных переменных.
SI>>Но в таком случае возможно было бы компилятору сгенерировать следующий псевдокод:

SI>>

SI>>{
SI>>  Entity * e = new Entity();
SI>>  bool generated_flag = true;
SI>>  if( getMagicResult() )
SI>>  {
SI>>    handleEntity( e );
SI>>    generated_flag = false;
SI>>  }
SI>>  if( generated_flag )
SI>>  {
SI>>     delete e;
SI>>  }
SI>>}
SI>>

SI>>и дальше продолжать в том же духе в функции handleEntity?
SI>>Согласен, накладные расходы будут в runtime, однако их будет существенно меньше чем весь runtime GC


R>Это уже референс-каунтинг. Таким подходом (если его обобщить — приделать к каждому объекту счётчик ссылок) можно обрабатывать большинство ситуаций (в т.ч. и в многопоточном приложении). При этом естественно, если среда обещает собирать и циклический мусор, то и традиционный полнометражный GC тоже нужен как напарник-подстаховшик.

не совсем согласен. reference counting заранее предполагает, что на каждый объект будет заведен счетчик безотносительно контекста его(объекта) использования. Соответственно и операции над этим счетчиком будут проводится безотносительно контекста использования объекта.

Т.е. в таком случае:

{
String * s = new String( "хеллоу, народ" );
cout << "s = " << s->asCstr() << "\n";
}

он будет бесполезен.

Плюс счетчик ссылок будет занимать место в хипе для каждого объекта, что в "сферо-конческой" ситуации с миллионом разнородных мелких объектов совсем не гуд.

R>

кстати да, пора

Здравствуйте, StevenIvanov, Вы писали:

R>>Это уже референс-каунтинг. Таким подходом (если его обобщить — приделать к каждому объекту счётчик ссылок) можно обрабатывать большинство ситуаций (в т.ч. и в многопоточном приложении). При этом естественно, если среда обещает собирать и циклический мусор, то и традиционный полнометражный GC тоже нужен как напарник-подстаховшик.

SI>не совсем согласен. reference counting заранее предполагает, что на каждый объект будет заведен счетчик безотносительно контекста его(объекта) использования. Соответственно и операции над этим счетчиком будут проводится безотносительно контекста использования объекта.

А вот операции могут проводится уже учитывая контекст.

SI>Т.е. в таком случае:

SI>

SI>{
SI>String * s = new String( "хеллоу, народ" );
SI>cout << "s = " << s->asCstr() << "\n";
SI>}
SI>

SI>он будет бесполезен.

Например, в таком случае компилятор может не вставлять никаких операций над счётчиком, а сразу вставить удаление объекта.
А вот в примере, который ты привёл выше нужно одно условное увеличение счётчика. В примерах сложнее будет ещё сложнее.


SI>Плюс счетчик ссылок будет занимать место в хипе для каждого объекта, что в "сферо-конческой" ситуации с миллионом разнородных мелких объектов совсем не гуд.

Если ты хочешь в ран-тайм (кстати, это уже совсем не *compile-time* garbage collector) что-то отслеживать, то место в том или ином виде нужно по-любому.

Кстати, есть схема, которая близка к тому что ты привёл и фактически не требует дополнительного места в ран-тайм. Ищи по one-bit reference count.


SI>кстати да, пора

SI>Сорри за наивность, если у кого-нибудь есть линки на серьезную литературу (работы Boehm'a?) по этому поводу ткните носом.
C, в отличии от .нет, не платформа. И бывают случаи когда нужно отправить указатель на живой объект кудато вовне, а потом его могут тебе вернуть. А могут и не вернуть а самостоятельно позвать например Release. А то что вовне не на С может быть написано, а например, вообще периферийной железякой.
А вообще я давно юзаю смартпоинтеры и забыл что такое delete/free (но врочем не забыл, что такое ExFreePool )