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


_>Ммм, при слове escape-analysis у меня появляется ассоциация исключительно с соответствующим механизмом в Java, который работает как раз не на уровне компилятора, а на уровне виртуальной машины (причём ещё и на вероятностных принципах, анализируя рантаймовые параметры). Если ты имел в виду что-то другое (статическое, на этапе компиляции), то значит у нас тут просто небольшое рассогласование в терминологии.
Ок, поясню: размещение в куче позволяет объекту пережить тот стек-фрейм, в котором он был создан.
Это необходимо, если ссылка на этот объект покидает этот стек-фрейм. Если же время жизни всех ссылок на этот объект ограничено временем жизни стек-фрейма, то можно разместить этот объект на стеке прозрачно для всего остального кода.
Проверка этой гипотезы и называется escape analysis: мы смотрим, не "сбегает" ли ссылка. Кто это делает — компилятор или среда — неважно. Механизм — один и тот же.
В управляемой среде компилятор может отловить только самые очевидные случаи. Инлайнинг и прочий хардкор, который может позволить уточнить результаты escape-analysis, производится на уровне JIT.
Насколько я знаю, никаких вероятностей в Java нету — ведь если мы с вероятностью 1% ошибаемся, то один раз из ста у нас наружу уходит ссылка на разрушенный объект.

_>Ты действительно хочешь сказать, что в программирование не встречается задач, где входные данные уже гарантированно отсортированы? )
Гарантии может дать только статически верифицируемый код. Поэтому наиболее эффективный способ — это ввести тип SortedList, который будет гарантировать наличие сортировки независимо от количества коммитов в репозиторий, прошедших со дня первоначальной сборки.
Это — ровно то же самое, что и строка, оборудованная предвычисленной длиной.
Лет десять назад я тут вёл споры с одним фанатом императивного программирования, который уверял меня, что в программировании прямо-таки постоянно встречаются строки, про длину которых заранее ничего неизвестно.
Примеры он, правда, привести затруднился — пришлось придумать воображаемый сетевой протокол.
И тут у нас всё точно так же: важно предотвратить нарушение инвариантов. По-хорошему, конструктор обязан удостовериться за O(N) что массив и правда отсортирован.

_>Ну так если бы возможность задавать намерения, позволяла это эффективно делать для произвольных задач и с нулевым оверхедом, то я бы тоже не отказался от такого. Но к сожалению волшебных палочек не существует. Даже упоминаемые выше ranges из C++ годятся не для всех задач (хотя с обсуждаемым случаем работы по отсортированному массиву естественно справляются)...
Если начинать с задачи "минимизировать оверхед", то мы никогда не построим удобного языка. Надо начинать с задачи "обеспечить выразительность", а уже потом заниматься устранением abstraction penalty.
Тем более, что методик по борьбе с abstraction penalty придумано вагон и маленькая тележка — начиная ещё со Smalltalk с его хотспоттингом и работ Ершова по частичным вычислениям.

_>Не вижу никакой принципиальной разницы между случаем отсортированного int[] и myfields[], отсортированного по какому-то из полей структуры myfields. И в том и в другом случае тебе всё равно приходится руками писать тот же самый императивный код в своей реализации where для данного типа.
Нет. Where пишется один раз для SortedDictionary<T>, также, как и i4o, который уже написан. Там внутри — анализ предиката в поисках сравнений ключевого атрибута с параметром, перестроение предиката на "индексную" и "остаточную" части, и потом выполнение кода. Никакой специфики для пользовательского типа там нет.


_>С чего это переписывать полностью императивный код при правке предиката? Или ты думаешь он там какой-то ассемблерной магией задаётся, а не той же самой банальной строчкой с условием? )
Может, я и правда чего-то не понимаю?
Давайте в студию пример императивного кода, который заменяет вот такой вот примитивный query comprehension:

var t = from p in persons where p.Age >= 18 && p.Age <= 65 && p.Name.StartsWith("K") select p

Предположим, что persons — массив, который уже отсортирован по Age.
Как изменится код, если отсортировать массив по Name?
Как изменится код, если отсортировать массив сначала по Name, потом по Age?
Как изменится код, если отсортировать массив сначала по Age, потом по Name?

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


_>Ммм, при слове escape-analysis у меня появляется ассоциация исключительно с соответствующим механизмом в Java, который работает как раз не на уровне компилятора, а на уровне виртуальной машины (причём ещё и на вероятностных принципах, анализируя рантаймовые параметры). Если ты имел в виду что-то другое (статическое, на этапе компиляции), то значит у нас тут просто небольшое рассогласование в терминологии.
Ок, поясню: размещение в куче позволяет объекту пережить тот стек-фрейм, в котором он был создан.
Это необходимо, если ссылка на этот объект покидает этот стек-фрейм. Если же время жизни всех ссылок на этот объект ограничено временем жизни стек-фрейма, то можно разместить этот объект на стеке прозрачно для всего остального кода.
Проверка этой гипотезы и называется escape analysis: мы смотрим, не "сбегает" ли ссылка. Кто это делает — компилятор или среда — неважно. Механизм — один и тот же.
В управляемой среде компилятор может отловить только самые очевидные случаи. Инлайнинг и прочий хардкор, который может позволить уточнить результаты escape-analysis, производится на уровне JIT.
Насколько я знаю, никаких вероятностей в Java нету — ведь если мы с вероятностью 1% ошибаемся, то один раз из ста у нас наружу уходит ссылка на разрушенный объект.

_>Ты действительно хочешь сказать, что в программирование не встречается задач, где входные данные уже гарантированно отсортированы? )
Гарантии может дать только статически верифицируемый код. Поэтому наиболее эффективный способ — это ввести тип SortedList, который будет гарантировать наличие сортировки независимо от количества коммитов в репозиторий, прошедших со дня первоначальной сборки.
Это — ровно то же самое, что и строка, оборудованная предвычисленной длиной.
Лет десять назад я тут вёл споры с одним фанатом императивного программирования, который уверял меня, что в программировании прямо-таки постоянно встречаются строки, про длину которых заранее ничего неизвестно.
Примеры он, правда, привести затруднился — пришлось придумать воображаемый сетевой протокол.
И тут у нас всё точно так же: важно предотвратить нарушение инвариантов. По-хорошему, конструктор обязан удостовериться за O(N) что массив и правда отсортирован.

_>Ну так если бы возможность задавать намерения, позволяла это эффективно делать для произвольных задач и с нулевым оверхедом, то я бы тоже не отказался от такого. Но к сожалению волшебных палочек не существует. Даже упоминаемые выше ranges из C++ годятся не для всех задач (хотя с обсуждаемым случаем работы по отсортированному массиву естественно справляются)...
Если начинать с задачи "минимизировать оверхед", то мы никогда не построим удобного языка. Надо начинать с задачи "обеспечить выразительность", а уже потом заниматься устранением abstraction penalty.
Тем более, что методик по борьбе с abstraction penalty придумано вагон и маленькая тележка — начиная ещё со Smalltalk с его хотспоттингом и работ Ершова по частичным вычислениям.

_>Не вижу никакой принципиальной разницы между случаем отсортированного int[] и myfields[], отсортированного по какому-то из полей структуры myfields. И в том и в другом случае тебе всё равно приходится руками писать тот же самый императивный код в своей реализации where для данного типа.
Нет. Where пишется один раз для SortedList<T>, также, как и i4o, который уже написан. Там внутри — анализ предиката в поисках сравнений ключевого атрибута с параметром, перестроение предиката на "индексную" и "остаточную" части, и потом выполнение кода. Никакой специфики для пользовательского типа там нет.


_>С чего это переписывать полностью императивный код при правке предиката? Или ты думаешь он там какой-то ассемблерной магией задаётся, а не той же самой банальной строчкой с условием? )
Может, я и правда чего-то не понимаю?
Давайте в студию пример императивного кода, который заменяет вот такой вот примитивный query comprehension:

var t = from p in persons where p.Age >= 18 && p.Age <= 65 && p.Name.StartsWith("K") select p

Предположим, что persons — массив, который уже отсортирован по Age.
Как изменится код, если отсортировать массив по Name?
Как изменится код, если отсортировать массив сначала по Name, потом по Age?
Как изменится код, если отсортировать массив сначала по Age, потом по Name?