Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет kouzdra ([info]kouzdra)
@ 2005-11-01 14:27:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Mr. President, we must not allow... a mine shaft gap!
У [info]lqp зашла речь об open source. Оставляя в стороне
этические вопросы, интересно подумать о технологических.

Там речь шла о том, что Microsoft пытается на .NET уйти в технологический отрыв (скорее всего прогадит из-за свойственного ему бардака, но это ортогонально к).

Я задумался - какие у OSS community есть действительно серьезные gapы. Очевидные -

- Сборка мусора (Boehm GC - не решение)
- Java

PS: Mine shaft gap

(Добавить комментарий)


[info]polytheme
2005-11-01 14:54 (ссылка)
а чем, собственно, плох Boehm GC ? Тем, что это хакерская поделка, а не научная разработка ? мне этот коллектор весьма хвалили. у нативной java сборщик мусора ужасный, но я не знаю, что про gc говорит наука (мне говорили, что есть старая статья Дейкстры про сборку мусора в параллель, но я не читал).

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 15:06 (ссылка)
Он очень хорош, но это консервативный сборщик мусора (кстати, автор как раз профессиональный специалист по GC - то есть как раз "научная разработка"). Что означает
- он не может уплотнять память
- он не может использовать generational GC, а это для языков наподобие Java/O'Caml критически важно для производительности.

С С++ он очень хорош (потому что там с памятью обращаются по другому, а вот с языками сделанными "под GC" ведет себя безобразно)

Опять же - проблема фрагментации в С/С++ - вечная и программы пишутся с ее учетом. Потому - в С++ это не большой недостаток. В Java же об этом просто не думают.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 22:18 (ссылка)
Немного поправлю: насчет поколений - это неправда. Поколения - это множества, пространственной докализации не требуется.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 22:26 (ссылка)
А как их прибивать без перемещения на новое место?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 22:41 (ссылка)
Обычно добавлением в список свободных.

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

(Ответить) (Уровень выше)


[info]qwerty
2005-11-01 22:49 (ссылка)
Боэмовский сборщик - как раз вполне научная разработка. А сборка мусора - вполне продвинутая наука. Статья же Дейкстры с ошибкой (при параллелизме это часто случается) и малость уже устарела.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]polytheme
2005-11-01 22:57 (ссылка)
да, я знаю, что устарела, она где-то чуть ли не 70-х годов. меня интересует все неэврестическое оттуда, если у вас есть ссылки на статьи, было бы здорово.
А Boehm, кажется, произносится как "Бём".

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:11 (ссылка)
Не знаю, как он произносится - дядька ростом минимум 190 см, дловольно крупынй, любит пиво.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]polytheme
2005-11-01 23:17 (ссылка)
это не так существенно, существенно - где взять статьи :) у меня и Дейкстровской-то нет.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:20 (ссылка)
Если вы меня периодически раз в неделю будете пинать, я все изложу.

(Ответить) (Уровень выше)


[info]polytheme
2005-11-01 23:04 (ссылка)
пардон, "неэвристическое", описка.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:19 (ссылка)
А что там эвристическое? Дейкстре принадлежит формулировка инварианта, который должен обязательно выполняться при параллельной сборке мусора для синхронизации мутатора с коллектором, плюс конкретный алгоритм.

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

Основных способов сохранения инварианта есть два, но с многочисленными вариациями.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]polytheme
2005-11-02 12:20 (ссылка)
я инвариант не совсем понял. правильные видимо вопросы будут такие :
1. какие объекты подлежат сборке ? все черные ? т.е. нужно дополнить
инвариант тем, что из белого (и серого) объекта нет стрелок в черные ?
2. путь имеется в виду путь по ссылкам из полей ?
3. "ссылки на которые уже, а их поля еще не" - "уже" и "ещё не" - черные ?

кроме этого, инварианту удовлетворяет ситуация, когда все объекты белые.
это, видимо, начальная ситуация.

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

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-02 12:47 (ссылка)
Еще раз - инвариант про синхронизацию мутатора (пользовательской программы) и коллектора (сборщика мусора) в процессе параллельной (parallel или concurrent, в данном контексте не важно) сборки мусора. Мутатору разрешается менять ссылки между объектами, но только так, чтобы в момент активности коллектора был выполнен инвариант.

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

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

В самом начале достижимые из корней объекты серые, а все остальое белое. Если корни представлены обним объектов (теоретически это удобно, практически - нет), то только этот один объект серый. Стеки, если они не обычные объекты в куче, - часть корней.

В самом конце серых объектов нет - есть только черные (живые) и белые (мусор).

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]polytheme
2005-11-02 14:15 (ссылка)
ага, я понял. для меня было внове, что коллектор накладывает условия на мутатор. я думал, программа сама по себе, только предоставляет информацию о ссылках.

инвариант теперь я понял так : если объект доступен, то путь к нему по ссылкам обязательно пройдет через серый объект.

осталось непонятно :
1. пусть в ходе работы мутатор "должен нарушить инвариант", т.е., например, родить новый белый объект и сослаться на него из черного. верно ли, что при этом работа мутатора должна прерваться, а коллектор должен заняться перекраской - так оно работает ? т.е. вопрос, видимо, про дополнительные действия.
2. не понял, почему мутатор не может подвесить черный объект.
3. правильно ли я понял, что мусор можно собирать, когда серых объектов не останется - т.е. самый конец - это и есть момент, в который можно собирать мусор.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-02 20:29 (ссылка)
Нет, инавриант вы поняли не совсем правильно - если объект как-либо доступен, то должен найтись хотя бы один путь, проходящий через серый на границе черного и белого. Путей же может быть много. Ваш инвариант тоже был бы достаточным, но слишком сильным.

1. Мутатор все равно должен хоть какие-то доп. действия производить. Даже если он просто пишет объект в почтвоый ящик коллектору. Нулевых расходов, наверно, можно достугнуть при наличии неограниченного избытка процессоров и сугубо аппаратной реализации этих самых дополнительных действий. Такого никто давно уже не делают. Если процессоров мало, то важно выполнить эти дополнительные действия побыстрее, а уж кому они запишутся, не столь важно.

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

3. В пределах одного цикла сборки мусора - да. Каждый цикл состоит из нескольких фаз. Можно (и нужно) несколько циклов крутить одновременно со смещением по фазе.

(Ответить) (Уровень выше)


[info]qwerty
2005-11-02 12:55 (ссылка)
Задача обычная - определить, какие объекты недостижимы и освободить их. Эта задача может не решаться за один полный цикл сборки мусора. Более того, не всякий алгоритм гарантирует сборку за заранее заданное число шагов, хотя такие алгоритмы считаются плохими.

(Ответить) (Уровень выше)


(Анонимно)
2005-11-01 15:10 (ссылка)
То есть если Sun выпустит-таки JVM в Open Source (включая тамошний GC), то проблемы не будет?

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

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 15:25 (ссылка)
Нормальный сборщик мусора требует поддержки трансляторного backend (нужно протащить информацию о типах через все оптимизации). То есть - практически полного переписывания gcc-шного backend. А это очень серьезная работа.

Сам-то по себе более или менее приличный сборщик написать несложно и много где он и написан.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 22:31 (ссылка)
На самом деле, с неточными корнями можно жить, а про структуры в памяти обычно все известно (за исключением неразмеченных объединений, ссылок на ссылки и некоторых страшных приведений, если в языке они есть). Если же речь идет о динамической компиляции (например, жабы) в нативный код, то компилятор в этом случае свой, поэтому и научить его можно чему угодно.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 22:39 (ссылка)
Это все известно до того, как по этому делу пройдется двадцать проходов GCC-шного бэкэнда.
Теоретически научить их сохранять всю эту информацию несложно. Практически - их надо для
этого переписать полностью.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 22:45 (ссылка)
Да нет, представление структур в памяти проходы не меняют (для этого анализ всего приложения потребовался бы). А стек и статику можно консервативным образом просматривать. Другой способ - вынуждать компилятор отказываться от оптимизаций в точках сборки мусора. Точки эти совсем не везде.

Какова все-таки задача? Собирать мусор в Ц/Ц++ или в динамически компилируемом языке?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 22:53 (ссылка)
А что делать с типами объектов в куче? Да и заставить gcc отказываться хоть
от чего-то - та еще задачка. Там местами есть комментарии вроде "не пытайтесь
вот здесь соптимизироват. От этого оно падает. Почему - мы сами не знаем".

Задача - Сборка мусора в статически компилируемом языке, но на базе GCC-backend.
Поскольку "другого backend'a у нас для вас нет" :)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:10 (ссылка)
В куче - писать идентификатор типа в заголовок. Если устроена виртуальность через таблицы, и виртуальность предполагается активно использовать, можно вместо идентификатора использовать обязательную ссылку на таблицу.

Заставлять отказываться - для этого не надо в компилятор лезть. Можно дополнительную косвенность где нужно устроить, и оптимизации сами в том месте отпадут. У меня виртуевая машина таким образом на Ц/Ц++ написана, компилируется обычным компилятором, в т.ч. и гцц, при этом может в кучу ссылаться, и консервативной сборки не требуется.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 23:18 (ссылка)
Не знаю - как факт - boehm GC в oss-ные программы пихают почем зря.
С вполне одинаковым результатом. Может - просто от лени.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:24 (ссылка)
Это мне известно :-)
Если о фрагментации и о случайных, но маловероятных граблях не заботиться, то вполне хороший вариант.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 23:32 (ссылка)
Он сильно тормозит. По объективным причинам - именно, что не generational.
Просто опытный факт - есть смысл профилять и короткоживущие объекты пересаживать
по возможности в стек. Очень помогает. Но это хорошо для С/С++, где это просто.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:39 (ссылка)
Угу. Аппаратный барьер записи прикрутить можно, но наверняка будет тормозить. А для программного барьера нужно лезть ручками в компилятор, отчего смысл прикручивания именно Боэма сразу исчезает.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 23:46 (ссылка)
Для incremental он там, кстати, прикручен - тормозит, кстати, не фатально - раза в
полтора-два. Другое дело, что incremental там не очень нужен - куда лучше просто
в idle стартовать время от времени GC (у него есть возможность повесиь хук, который
позволяет сборку быстро прервать).

Жабский incremental GC куда ужаснее. Еще в 1.4 он тормозил невероятно -
до полной неюзабельности. В 1.5 - не смотрел.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:58 (ссылка)
Ну не знаю я, почему плох сборщик в персональной жабе. Найди мл. Будника, он с ней гораздо более знаком. Заодно и...

В моей мелкой жабе ничего такого не наблюдается.

Поскольку разработка уже почти совсем переехала в Питер, могу выдать ссылочки на разработчиков. Если закидать их говном, возможно, они зашевелятся :-)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-02 00:05 (ссылка)
Да выдай - тем более, небось я их всех знаю. Хотя сейчас мне это все
фиолетово. С GC меня доставало то, что при определенных раскладах в
идее паузы от GC по полторы-две секудны начинали идти регулярно и
довольно сильно мешали жить. Сейчас мне идея как-то по фигу.

Я вообще сейчас сильно пересмотрел все эти подходы. Скажем - у меня
сейчас оно из двухъ половинок - собственно движок и фронтэнд, который
с ним общается через pipe. Так что паузы в движке фронтнд не блокируют.

Соответственно - кнопочки давятся быстро, а все остальное - не столь уж
важно. Да и по поводу вселенской рулезности GC я как-то сомневаться начал.
Потому как от пересаживания на пулы оно стало не только быстрее, но и правильнее
внутре.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-02 00:26 (ссылка)
Угу. Я пулы тоже очень люблю.

Еще и баги бывают, как в самом GC, так и в программах, ее использующих. Типа необнуления какого-нибудь более не используемого указателя. Или каких-нибудь хэш-таблиц, которые никогда сами не чистятся.

Впрочем, если очень хочется, можно GC и сочесть с пулами.

Вообще же от задачи зависит. Иногда пулами плохо.

(Ответить) (Уровень выше)


[info]qwerty
2005-11-01 23:36 (ссылка)
По-хорошему нужно вставить в деревца узелок gc-safe point, научить бэкенд в таких узелках дампить таблички локальных указателей и производных значений, плюс для инкрементности и поколений еще 1-2 узелка для программной реализации барьера. Если хочется легковесных процессов, нужно их стеки регистрировать.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 23:41 (ссылка)
Там нет дерева. Там rtl - что не очень плохо, но это фактически ассемблер целевой машины,
который итеративно улучшают разными проходами. С точностью до распределения регистров уже
изначальный совершенно неоптимиизированный rtl можно дампить в .s файл без проблем (собственно
-O0 так и делает - предаврительно абы как распределив регистры).

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:55 (ссылка)
Это я тоже знаю. Можно дампить и высокоуровневый ПЯ в текст (-fdump-translation-unit), можно и похачить, чтобы его назад засосать, только он не удобен излищней высокоуровневостью.

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

(Ответить) (Уровень выше)


[info]potan
2005-11-02 13:27 (ссылка)
Не gcc единым...
IMHO, компилятор надо писать с нуля, более модульным. И на языке типа Haskell.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-02 13:40 (ссылка)
Скорее ML, но нужно, колнечно. Неразрешимой проблемы тут нет.
Только вот быстро это сделать не получится.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]potan
2005-11-02 14:33 (ссылка)
Почему? ML ближе к императивному программированию, что для многих задач будет плюсом. Но для компилятора это не требуется - есть вход и есть выход, все вполне функционально описывается.
Haskell здесь более уместен.

(Ответить) (Уровень выше)


[info]qwerty
2005-11-01 22:21 (ссылка)
Сборщиков мусора в Сановских жабах несколько. Самый хороший (весь из себя параллельный и софтреалтаймовый, который публике пока не видно) открывать в обозримом будущем не собираются.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 22:30 (ссылка)
А вот мне интересно - пожалуй наименее проблемый сборщик мусора из всех, которые я видел - в O'Caml.
При этом очень простой. Тупой, можно даже сказать.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 22:35 (ссылка)
Навороченный - это GarbageFirst. Первое сообщение было с год назад, не знаю, опубликовано ли, но у меня есть. Он в основном лечит проблемы большого количества памяти и процессоров.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-01 22:46 (ссылка)
Статью я читал, но нынешний явно испытыват трудности уже на стадии incremental GC.
В чем O'Caml-евый не замечен.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-01 23:00 (ссылка)
Нынешних в персональной жабе в исходниках можно сконфигурировать 4 разных. Я ею не пользуюсь, поэтому не знаю, что там в бинарниках скомпилировано. Раньше еще и ключик был, чтобы переключать сборщики из командной строчки (тогда их внутри было два).

Сосет же персональная жаба по другой причине - никто ей, на самом-то деле, активно не занимается. Контора вяло балансирует между жопой и преджопием, никакой непосредственной прибыли с вложений в персональную жабу нет.

(Ответить) (Уровень выше)


[info]potan
2005-11-02 13:24 (ссылка)
На сколько я помню лучший GC сейчас у OCaml. А он вполне свободный.

(Ответить) (Ветвь дискуссии)


[info]qwerty
2005-11-02 22:07 (ссылка)
Лучший - в каком смысле и по сравнению с чем? Очень многое зависит от языка, платформы и требований к программе.

(Ответить) (Уровень выше)