рекурсия и итерация

Память в стеке выделяется точно так же, как в перемещающем GC.

а затраты времени на перемещение в перемещающем GC ты конечно не считаешь, да? Он у тебя с помощью магии перемещает? REP MOVS для дебилов, да?

При чем тут перемещение, если речь велась о выделении памяти?

При чем тут перемещение, если речь велась о выделении памяти?

*, а когда память закончится, то что делать?

эти посты писали разные люди, или один идиот?

Так что будет с твоим гениальным «сборщиком» когда кончится память?

Так что будет с твоим гениальным «сборщиком» когда кончится память?

тоже, что и с твоим.

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

тут кричали, что у них GC — «только инкремент». Это довольно грустно, что в их коде — всё работает, а вот в моём — почему-то нет. Может ты мне объяснишь, как их сборщик умудряется выделять память «только инкрементом», причём она не кончается? И как он выделяет регистровую память?

А то мне — ещё грустнее, чем этому ослику...

С нормальным сборщиком мусора память от реконструкции дерева не закончится. А у тебя закончится.

Может ты мне объяснишь, как их сборщик умудряется выделять память «только инкрементом», причём она не кончается?

Если будет кончаться - запустится сборка и память найдется..

а затраты времени на перемещение в перемещающем GC ты конечно не считаешь, да? Он у тебя с помощью магии перемещает?

Выигрыш от компактификации многократно перевешивает накладные расходы на перемещение.

С нормальным сборщиком мусора память от реконструкции дерева не закончится. А у тебя закончится.

тогда не говори, что «только инкремент». Пойми — либо крестик, либо трусы. Чудес не бывает в этом мире. Да, у меня рухнет этот код. У тебя — зависнет. Я такое наблюдал неоднократно. Бороться с нехваткой мозгов можно только покупкой новых мозгов. Повторяю — чудес не бывает. Кнут ещё в семидесятых это всё доказал, и у него есть пруфы, со строгим матаном. Ищи ошибку, если такой умный. Я верю Кнуту, а не тебе.

Может ты мне объяснишь, как их сборщик умудряется выделять память «только инкрементом», причём она не кончается?

Если будет кончаться - запустится сборка и память найдется..

за сигаретами сбегаешь? Пока твой GC всё повесил? Помни, что память *одна* в большинстве случаев, и ВСЁ ждёт, пока эта память занята. Например твоим GC. Намного лучше(дешевле!) повесить пару ядер на вычисление оптимального выделенного блока, чем вешать ВСЁ. Потому сишный malloc(3) предпочтителен в 95% случаев. А если ты не в состоянии сделать free(3) в нужный момент — вон из профессии. Никакая прокладка типа allways jit'а тебя не спасёт от течки. Смирись с этим.

Выигрыш от компактификации многократно перевешивает накладные расходы на перемещение.

сиё есть бред и мечта. Доказательство опубликовано Кнутом более 30 лет назад.

Доказательство опубликовано Кнутом более 30 лет назад.

Я думаю, что тогда были совсем другие сборщики.

Я думаю, что тогда были совсем другие сборщики.

математика тогда тоже была совсем другой? Ну тогда извини...

Hint: матан «исправляется» только магией. А делить на ноль умеет только Б-г.

Алгоритмы сборки стали другими.

алгоритмы НЕ стали «другими». Они только развиваются и улучшаются. Причём почти всегда в сторону специализации. Т.е. старый алгоритм затачивают под новый случай. Но принципиально в них ничего не меняется.

Если у тебя нет виртуальной машины с поддержкой GC, результат в любом случае непереносим.

а с wm тоже будет не переносим. Точнее, тебе придётся эту твою wm везде таскать для «переносимости». Т.е. это конечно ххорошо, если тебе её по любому надо таскать, как например в javascript, и мирится с её overhead'ом.

тогда не говори, что «только инкремент».

Хорошо, не только. Но этим «не только» можно полностью пренебречь. То есть 99.9% времени будет занимать именно инкремент.

Да, у меня рухнет этот код. У тебя — зависнет.

С чего же он зависнет? Ничего подобного.

Пока твой GC всё повесил?

С чего он что-то повесит? В случае малого дерева сборка будет быстрее, чем вызов одного маллока. Ты когда вызываешь маллок идешь за сигаретами?

Помни, что память *одна* в большинстве случаев, и ВСЁ ждёт, пока эта память занята.

Открой для себя конкурентные инкрементальные сборщики.

Потому сишный malloc(3) предпочтителен в 95% случаев. А если ты не в состоянии сделать free(3) в нужный момент — вон из профессии.

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

сиё есть бред и мечта.

Только выигрыш в сотни тысяч раз перед дефолтными аллокаторами доказан практикой.

Доказательство опубликовано Кнутом более 30 лет назад.

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

Hint: матан «исправляется» только магией.

Просто ты не знаешь матана, в этом вся проблема. Подходы со временем очень сильно меняются. Те доказательства, которыми пользовались математики полторы сотни лет назад, например, сейчас и за доказательства не считаются особо.

Причём почти всегда в сторону специализации.

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

В таком случае если выделять память аллокаторами «влоб» - это будет тормозить, очень, очень силньо тормозить. В сишка обычно проблема решается за счет предварительного выделения памяти, выделения блоками и т.д. - но для функциональных кейзов эти способы неприменимы. И сборщик тут - это как раз оптимальный алгоритм выделения памяти для данного кейза.

Хорошо, не только. Но этим «не только» можно полностью пренебречь. То есть 99.9% времени будет занимать именно инкремент.

ага. В синтетических тестах, где для массива в 1000 эл-тов имеется 64Гб RAM. На боевом сервере это всё начинает тупить и тормозить, хотя там тоже 64Гб, но массивов там 100500, и размером они по 100500.

С чего же он зависнет? Ничего подобного.

так и будет, когда твой перемещающий GC начнёт _перемещать_. Включи голову и осознай, что для этого нужно ВСЁ останавливать.

ИЧСХ, если у тебя этот твой GC будет НЕ работать 99.9% времени, то когда он таки включится, работы накопится в тысячу раз БОЛЬШЕ, чем если-бы он работал на каждой аллокации. Но ты же 999 аллокаций делал только инкремент. А теперь — страдай и жди.

Повторяю: чудес не бывает, если ты отложил работу, то ты НЕ СДЕЛАЛ работу. Так вот, GC именно ОТКЛАДЫВАЕТ работу по наведению порядка.

В случае малого дерева сборка будет быстрее, чем вызов одного маллока.

докажи это странное заключение.

Открой для себя конкурентные инкрементальные сборщики.

они освобождают какую-то другую память?

К сожалению, маллок/фри - это медленно, сильно медленно.

это пока сборка не запустилась, а откладывается. Да, тогда malloc медленный. Вот только работа GC всё равно только ОТКЛАДЫВАЕТСЯ.

Только выигрыш в сотни тысяч раз перед дефолтными аллокаторами доказан практикой.

тут главное, что-бы сборка не включилась во время теста.

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

область применимости описана — когда памяти не хватает, и приходится запускать GC (или когда maloc(3) уже не справляется, и тратит слишком много времени на поиск)

А когда памяти как грязи — мой super_malloc работает ничуть не хуже, и не медленнее. Особенно в 64х битах и со свопом (куда и будет складываться автоматически ненужный мусор)

Просто ты не знаешь матана, в этом вся проблема. Подходы со временем очень сильно меняются. Те доказательства, которыми пользовались математики полторы сотни лет назад, например, сейчас и за доказательства не считаются особо.

а те теоремы тоже устарели? Сумма квадратов катетов уже не равна квадрату гипотенузы? Да? Ну дай пруф на ютуб, я посмотрю ролик с доказательством, и пойду топится.

но для функциональных кейзов эти способы неприменимы. И сборщик тут - это как раз оптимальный алгоритм выделения памяти для данного кейза.

это верно. Осталось немного: докажи, что стратегия использования памяти в ФП сама по себе является оптимальной для существующих архитектур. А то для меня это не очевидно.

докажи это странное заключение.

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

они освобождают какую-то другую память?

Нет, ту же самую. но при этом выполнение программы им останавливать не надо.

это пока сборка не запустилась, а откладывается. Да, тогда malloc медленный. Вот только работа GC всё равно только ОТКЛАДЫВАЕТСЯ.

Смотри, фишка в том, что _удаление_ информации с перемещающим сборщиком вообще не вызывает времени. Выделение - вызывает очень мало времени. Реальное время занимает компактификация - которая зависит от размера _достижимых_ данных. Другими словами, с ростом интенсивности выделения/освобождений памяти стоимость GC практически не растет. С другой стороны она растет с ростом текущей потребности памяти.

С аллокаторами все наоборот - их стоимость практически не растет с ростом потребностей в памяти, но линейна по вызываемым маллок/фри.

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

Повторяю: чудес не бывает, если ты отложил работу, то ты НЕ СДЕЛАЛ работу. Так вот, GC именно ОТКЛАДЫВАЕТ работу по наведению порядка.

Да нет, GC совершает ДРУГУЮ работу. Это другой алгоритм. И сложность у GC и у аллокаторов разная (зависит от разных параметров).

так и будет, когда твой перемещающий GC начнёт _перемещать_. Включи голову и осознай, что для этого нужно ВСЁ останавливать.

Еще раз - читай про конкурентные сборщики.

тут главное, что-бы сборка не включилась во время теста.

Тебе вопрос на засыпку - сколько будет время занимать сборка перемещающего сборщика после выполнения задачи? Правильно - 0 (точнее время, слабо отличимое от нуля, сколько-то он работать все-таки будет). Сам догадаешься почему, или тебе объяснить?

область применимости описана — когда памяти не хватает, и приходится запускать GC (или когда maloc(3) уже не справляется, и тратит слишком много времени на поиск)

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

а те теоремы тоже устарели?

Теоремы не устарели. Я говорил о методах доказательства.

это верно. Осталось немного: докажи, что стратегия использования памяти в ФП сама по себе является оптимальной для существующих архитектур. А то для меня это не очевидно.

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

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

ОК, а что такого тормозного нужно сделать моему malloc'у? Выиграть партию в преферанс?

Нет, ту же самую. но при этом выполнение программы им останавливать не надо.

это как, если у тебя скажем массив, с которым ты СЕЙЧАС работаешь наполовину в одном месте, а на другую половину — в другом?

Смотри, фишка в том, что _удаление_ информации с перемещающим сборщиком вообще не вызывает времени. Выделение - вызывает очень мало времени. Реальное время занимает компактификация - которая зависит от размера _достижимых_ данных. Другими словами, с ростом интенсивности выделения/освобождений памяти стоимость GC практически не растет. С другой стороны она растет с ростом текущей потребности памяти.

тебе просто не подходит ЭТОТ malloc(3). Используй другой, не вижу проблемы.

тебе просто не подходит ЭТОТ malloc(3). Используй другой, не вижу проблемы.

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

ОК, а что такого тормозного нужно сделать моему malloc'у?

В общем случае - это системный вызов, которому надо сделать очень много.

это как

Иди и гугли, как. Что гуглить я тебе указал, конкретные алгоритмы найдешь сам.

Иди и гугли, как. Что гуглить я тебе указал, конкретные алгоритмы найдешь сам.

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

Тебе вопрос на засыпку - сколько будет время занимать сборка перемещающего сборщика после выполнения задачи? Правильно - 0 (точнее время, слабо отличимое от нуля, сколько-то он работать все-таки будет). Сам догадаешься почему, или тебе объяснить?

нет, спасибо. Но меня никто не просит писать helloworld'ы, задача которых — напечатать helloworld и завершиться.

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

Теоремы не устарели. Я говорил о методах доказательства.

а я говорил о _доказанных_ теоремах.

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

именно по этому аллокатор и НЕ ВХОДИТ в спецификацию C/C++. Мало того, в эту спецификацю входит возможность его ЗАМЕНИТЬ. Т.е. использовать свой malloc, или перезагрузить class::new, или даже ::new. Так, как нужно в _этой_ задаче.

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

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

я всё равно не понимаю, в чём проблема-то? Не можешь реализовать? Исходники твоей ракеты закрыты?

Регистровые переменные в пул не вернуть? Не используй регистровые переменные. Не используй стек. Да, на сишечке с интами и глупыми указателями не очень удобно(оператор = и всякие +- не перезагрузить, и придётся делать функции), используй C++.

В общем случае - это системный вызов, которому надо сделать очень много.

ну запроси Over9000Mb, один раз, в начале программы, и не доставай больше систему.

это как, если у тебя скажем массив, с которым ты СЕЙЧАС работаешь наполовину в одном месте, а на другую половину — в другом?

Иди и гугли, как. Что гуглить я тебе указал, конкретные алгоритмы найдешь сам.

я их без тебя и твоего гугла знаю — всё затормозить, и начать двигать туда-суда. Что в php, что в javascript'е, который в FF/Opera/IE. Потому-то это дерьмо и тормозит, и жрёт память сотнями и тысячами метров. Об этом любой школьник знает. Про вашу ынтерпрайзную java я тоже в курсе, которой нужен отдельный сервер под какой-то сраный сайт на 1К юзеров.

Опциональный(полностью) сборщик в C++ может быть полезен, возможно, что он таки появится рано или поздно в стандарте.

будь мужиком, сделай СЕЙЧАС. У тебя есть для этого все возможности. Я уже делал, там нет ничего такого уж сложного.

При поддержке компилятора будет лучше. Можно сделать как плагинчик к clang'у.

ну запроси Over9000Mb, один раз, в начале программы, и не доставай больше систему.

9000мб в стандартной ФП-программе выделяется и освобождается за время порядка секунд, постоянно.

я их без тебя и твоего гугла знаю — всё затормозить

Нет. я же сказал - гугли. Алсо, в том же эрланге, например, сборщик в каждом процессе свой, независимый. СБорка во дном процессе не останавливает другие и кроме того проходит очень быстро за счет того, что памяти процесс потребляет мало и unidirectional heap.

И еще, современные GC плохо работают тогда, когда мало мусора и много объектов, которые реально нужны.

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

Ибо не смотря на название, они не делают то, что говоришь ты.

Да нет, как раз то.

Регистровые переменные в пул не вернуть?

Опять ты эту хуйню несешь? Какой пул? что и куда ты собрался возвращать, дубина?

сиё есть бред и мечта. Доказательство опубликовано Кнутом более 30 лет назад.

Дай ссылку. Мне действительно интересно, что конкретно Кнут доказал. Понятно же, что математический результат не может звучать как «GC сливает malloc/free»

Мне действительно интересно, что конкретно Кнут доказал. Понятно же, что математический результат не может звучать как «GC сливает malloc/free»

читай главу про менеджеры памяти. Она коротенькая.