Циклические ссылки при подсчете ссылок

Как ты вообще себе это представляешь?

Это сильно затратно и будет ни чем не лучше GC?

Да

Как ты вообще себе это представляешь?

Смотреть классы на этапе компиляции и строить код для удаления циклических графов для какой-то группы классов? По крайне-мере на ЯП уровня Java это было бы наверное возможно. Я собственно сейчас и пытаюсь изучить этот вопрос.

#include <vector>
#include <iostream>

using namespace std;

void moveToB(vector<void*> &a, vector<void*> &b) {
	int n;
	cin >> n;
	for(int i=0; i<n; ++i) {
		b.push_back(a.back());
		a.pop_back();
	}
}

int main(){
	vector<void*> a;
	vector<void*> b;
	int n;
	cin >> n;
	a.push_back((void*)&b);
	for(int i=0; i<n; ++i){
		a.push_back(NULL);
	}
	moveToB(a,b);
	return 0;
}

Циклическая ссылка может возникнуть, а может и не возникнуть. Зависит только от рантайма. Возможны и более сложные случаи, когда a -> b -> c -> a. Это нельзя гарантированно отловить на этапе компиляции. Только если очень сильно урезать возможности программиста, что бы не допустить никакой возможности создания цикла. Но в таком случае ты даже двусвязный список не реализуешь.

В питоне не то что ты хочешь? Там в основном подсчет ссылок, но вдобавок циклы разруливаются.

Циклическая ссылка может возникнуть, а может и не возникнуть

В данном случае это не важно. Анализатор заметит, что b забрасывается в a. А затем происходит обратная операция элементы из a в b.

Анализатору неважно возникнет или нет здесь циклическая ссылка. Ему главное найти вероятную ситуацию её возникновения и сгенерировать для неё код на удаление объектов.

Конечно на уровне крестов это делать сложнее, а на уровне java где все тупо по ссылке задача значительно облегчается.

В питоне не то что ты хочешь?

Хз, но это все же скриптота, на которой как-то не припомню высоконагруженные проекты 7x24. Да и делать это в рантайме наверное лучше используя GC...

Мне же интересно детектить на этапе компиляции с генерацией кода на удаление потенциально зацикливающихся графов объектов.

Анализатору неважно возникнет или нет здесь циклическая ссылка. Ему главное найти вероятную ситуацию её возникновения и сгенерировать для неё код на удаление объектов.

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

http://nim-lang.org/docs/gc.html тут, например, что-то подобное

http://nim-lang.org/docs/gc.html тут, например, что-то подобное

Это GC. В Swift и Rust его нет, там используется автоматический подсчёт ссылок, где код для удаления объектов вставляется компилятором. А-ля smart pointers из C++.

Удобно спорить с самим собой

Вообще, есть какие-нибудь интересные реализации управлением памяти через подсчет ссылок, которые могут обнаруживать и циклические ссылки?

Нет. Самое близкое к тому, что ты хочешь, называется region inference. Практических реализаций, применимых в продакшене вроде бы нет, есть ряд простеньких ни к чему не пригодных реализаций, есть теоретические работы. На русском материала не видел.

Мне же интересно детектить на этапе компиляции с генерацией кода на удаление потенциально зацикливающихся графов объектов.

Опиши примерный алгоритм. Для начала возьми пример двух ссылающихся друг на друга объектов. Распиши, как бы твой алгоритм отработал для простейшей структуры односвязного списка(ведь ему можно сделать петлю). Если справишься, переходи к двусвязному списку. Потом к деревьям.

region inference

Интересная тема, кстати. Жаль, что развивается вяло.

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

У тебя весь код будет в ложной сработке — толку от этого будет ноль.

Вот я тоже над этим думал.

Можно пытаться отслеживать циклы при их создании, но это дорого выходит в общем случае.

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

Но всё это упирается в одну маленькую проблему: если у объектов есть деструкторы/финализаторы/what-you-call-it, то в каком порядке их вызывать для объектов из цикла? При этом следует иметь в виду, что в деструкторах в принципе может находиться произвольный пользовательский код. Вот пара проблем, которые сразу приходят в голову. Может ли деструктор воскресить объект? Гарантирована ли корректность всех полей объекта, когда выполняется деструктор?

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

на которой как-то не припомню высоконагруженные проекты 7x24

youtube, не?

Смотреть классы на этапе компиляции и строить код для удаления циклических графов для какой-то группы классов

как то это уже черезчур для ARC

Это нельзя гарантированно отловить на этапе компиляции

Можно, смотри Rust :)

Можно, смотри Rust :)

нельзя, и в Rust точно так же можно сделать циклические ссылки.

Можно, смотри Rust :)

Да что ты говоришь. Если это не циклическая ссылка в расте, что я трамвай.

use std::cell::RefCell;
use std::rc::Rc;

struct List {
	data : char,
	next : RefCell<Option<Rc<List>>>
}

fn make_cycle() -> Rc<List> {
	let a = Rc::new(List {
		data : 'a',
		next : RefCell::new(None)
	});
	let b = Rc::new(List {
		data : 'b',
		next : RefCell::new(None)
	});
	let c = Rc::new(List {
		data : 'c',
		next : RefCell::new(None)
	});
	{
		let mut p = a.next.borrow_mut();
		*p = Some(b.clone());
		let mut p = b.next.borrow_mut();
		*p = Some(c.clone());
		let mut p = c.next.borrow_mut();
		*p = Some(a.clone());
	}
	return a;
}

fn main(){
	let mut ptr = make_cycle();
	for _ in 0 .. 6 {
		println!("{}", ptr.data);
		let tmp : Option<Rc<List>> = ptr.next.borrow().clone();
		match tmp {
			None => {
				println!("wow, not loop");
				break
			},
			Some(p) => ptr = p
		}
	}
}

Можно, смотри Rust :)

Rust этого не умеет.

Есть мнение, что подсчёт ссылок медленнее сборки мусора. Сборка мусора бывает очень навороченная, с поколениями.

Сборка мусора требует больше ресурсов. Она(кроме специальных, затраченных под реалтайм, случаев) плохо предсказуема. Она не позволяет универсально управлять другими ресурсами. Она не даёт никаких гарантий о времени уничтожения объекта и финализатора.

Иногда это нормально. Иногда нет.

Сборка мусора требует больше ресурсов.

Это, конечно, не так. Общее время, затрачиваемое на сборку мусора, значительно меньше, чем общее время, затрачиваемое на подсчет ссылок и аллокацию/деаллокацию, проблема только, в том что это время не распределено равномерно.

Но дело ведь не только в скорости, но и в памяти. Думаю, под ресурсами имелось в виду и это. Опять же, запуск сборки может тормозить систему в целом, что может быть неприемлемо.

Но дело ведь не только в скорости, но и в памяти.

Память гц жрет меньше чем счетчик.

Память гц жрет меньше чем счетчик.

Наверное потому всякие Java, .NET и пр. жрут ее как не в себя.

Наверное потому всякие Java, .NET и пр. жрут ее как не в себя.

А зачем не жрать если можно жрать? Я память покупаю не за тем чтобы она свободной была а за тем, чтобы использовалась. При этом, конечно же, никто не мешает ограничить потребление памяти уровнем программы со счетчиком, если надо.

Есть мнение, что подсчёт ссылок медленнее сборки мусора.

В рантайме не будет подсчета ссылок или сборки мусора. Я обдумываю комплекс ЯП+демон или ЯП+ide, который во время работы пользователя с сырцами будет генерировать метаданные в перемешку с нативным кодом (или байт-кодом+jit пока хз).

На основе метаданных в нативный код будет автоматически инъектится сгенерированный код по выделению/освобождению памяти за пользовательскими объектами.

Не больше, не меньше, иначе смысла нет в этом новом ЯП из 21 века, если не удасться сделать подобную штуку. Тогда придется продолжать юзать либо ЯП из 20 века, либо поделки от хипстеров, либо застрявших в 70-х автортетов от ИТ.

Компилятор у такого ЯП конечно будет медленее (поэтому и демон или ide, чтобы компилить на каждый чих и держать индекс кода в памяти), чем у тех же крестов, но с другой стороны он должен параллелится. Как раз к времени его стабилизации, такие процы устареют Встречайте: 10 ядер 20 потоков

А зачем не жрать если можно жрать?

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

который во время работы пользователя с сырцами будет генерировать метаданные в перемешку с нативным кодом (или байт-кодом+jit пока хз).

На основе чего? как твой демон будет определять какие метаданные генерировать?

Затем, что кеши проца все еще нельзя докупать.

А при чем тут кеш проца?

А потому на кеш линиях у тебя будет меньше данных попадать => будет больше обменов с отожранной оперативкой => будут тормоза.

Каким образом? Достижимых данных (которые будут кешироваться) одинаковое количество, а те данные, что занимают оперативку, но недостижимы, в кеше все равно не лежат.

в кеше все равно не лежат.

При этом локальность данных при использовании сборщика выше => кешмисов меньше. Достижимых данных, кстати, тоже будет меньше, с-но то что не попадет в кеш изза того что reference counter выжирает память может туда попасть при использовании сборщика.

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

Достижимых данных (которые будут кешироваться) одинаковое количество

Это если jit все грамотно заоптимизирует, вручную то всегда можно лучше заоптимизировать.

а те данные, что занимают оперативку, но недостижимы, в кеше все равно не лежат

Они же не просто так её занимают, а значит в какие-то моменты будут вытеснять кеш.

Как определять это время жизни, его границы и в какие места инъектить код проверок на возможное освобождение объекта - я так далеко еще не заходил )

Это алгоритмически неразрешимая задача. Такие дела.

Это если jit все грамотно заоптимизирует

При чем тут вообще джит вообще?

вручную то всегда можно лучше заоптимизировать.

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

Они же не просто так её занимают

Именно тчо просто так. Они недостижимы, никогда не будут использованы (т.к. использовать их невозможно) а потому никогда не попадут в кеш (т.к. к ним не будет обращений).

Кто-то это доказал или пытался делать на практике?

Речь шла о Java и .NET, а о не каком-то ЯП+GC в ваккууме. А Java не умеет банальный ValueType, а когда и сумеет в 10-ке, то со своими ограничениями. А потому грамотные оптимизации на джит тут причем, без него Java на кешах творила бы ад и израиль.

Что там не умеет .NET я хз, но вроде он меньше памяти выжирает. За него ничего не буду говорить.

Кто-то это доказал или пытался делать на практике?

Это довольно-таки очевидно, чтобы отдельно кто-то доказывал.

А Java не умеет банальный ValueType

Но это никак не связано с GC.

А потому грамотные оптимизации на джит тут причем, без него Java на кешах творила бы ад и израиль.

Нет, ни при чем.

Это довольно-таки очевидно, чтобы отдельно кто-то доказывал.

Хочешь сказать невозможно отследить в сырцах все возможные места входа/выхода для конкретного объекта? И отметить места возможного освобождения ресурсов для этого объекта? Например, в той же Java (если пока опустить jni и генерацию байт-кода в рантайме)?

Хочешь сказать невозможно отследить в сырцах все возможные места входа/выхода для конкретного объекта? И отметить места возможного освобождения ресурсов для этого объекта?

Конечно нет:

f x = if (pred x) then [] else (cons 0 x)

х - список. Как ты тут что отследишь если время жизни х зависит от pred x, то есть от вида самого х, которые нельзя определить до рантайма?

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

Для этого тебе придётся настолько сузить класс задач, что твой ЯП будет никому не нужен, так что можешь просто считать, что это невозможно.

Тут вроде упоминали уже region inference

В дополнение к region inference ищите shape analysis

Ну да, и он не работает. Как раз из-за того, что задача алгоритмически неразрешима.

Кто он? Есть много работ с описанием разных алгоритмов. Что конкретно не работает?

Вы какую из работ по этому вопросу имеете в виду? Или вы об отсутствии промышленной реализации?