>> Неразрешимость сводится к тому, что нет fool-proof способа менеджить память, которого хватит всем.
> Что значить "fool-proof" ? это что за определение? В переводе - "надежный"
> - что есть надежный? Мне нужны конкретные строгие определения "надежного способа",
> во-первых, во-вторых, определение "менеджить (управлять) память". А про "которого хватит
> всем" - промолчу, несерьезное высказывание.Это значит, который позволяет промышленным образом получать гарантированный результат. Это значит, что ты можешь пойти на рынок труда, нанять пяток программистов, и они гарантированно дадут тебе результат без mm, без необходимости с твоей стороны изучать их код под микроскопом и тратя на это количество человекочасов того же порядка, как и потраченное на написание кода.
>> Я в каком-то соседнем комменте задал наводящие вопросы: как ты доказываешь про
>> свой код, что там нет проблем с mm? Ты не доказываешь
>> это заказчику? Ну ок, а себе ты это доказываешь как-то? В
>> какой момент ты удовлетворённо откидываешься на спинку стула, и говоришь "ну
>> вот, теперь код безбажен"? Что ты делаешь для этого?
> проблемы с mm могут возникнуть если ты пишешь сам алгоритм mm.
Если ты делаешь malloc/free то уже могут возникнуть проблемы. Ты мог выделить память, и не освободить её после того, как она пекратила быть нужной. Даже если ты не делаешь malloc/free проблемы могут возникнуть: скажем ты можешь вернуть из функции указатель на локальную память, и получить use-after-free. Как ты доказываешь, что этого нет?
> Как доказываю? - выше в коменте ответил - оценкой "пространственной" сложности, это
> оценка необходимого и достаточного объема памяти и её зависимость. Я же
> могу посчитать сколько раз я запросил память для работы алгоритма. А
> вдруг мой алгоритм оказался избыточен, это разве "бажный" алгоритм? В прошлых
> дискуссиях про "течки" памяти мы так и не пришли к определению,
> что же это такое.
Это бажный алгоритм. В "прошлые" разы -- это в смысле когда мы обсуждали rust'овые гарантии safety? Безопасность -- это не то же самое, что и безбажность. Если я в расте разворачиваю Result'ы при помощи unwrap, то при любой ошибке я получаю панику и принудительное завершение программы. Если я собрал растовый код с проверкой на выход за границы, то у меня гарантированно не будет buffer-overflow, но программа может выпадать в панику, когда индекс за границы выходит. Это тоже всё баги программы. Но "безопасные" баги.
Там я приводил примеры, когда mem-leak'и могут оказываться опасными. Для большинства приложений они имеют пониженную опасность, потому как первый приоритет у багов, позволяющих злоумышленнику запустить произвольный код на системе и захватить полный контроль над системой. Но хапануть злоумышленного кода -- это не для всех программ актуально, а для некоторых ООМ означает полный провал.
>> Вот когда тебе надо доказать асимптотическую сложность алгоритма, ты берёшь и доказываешь
>> это.
> Хмммм, сложность оценивается, а не доказывается.
Это игра словами. О-большое -- это вполне себе математическая концепция. Из матана позаимствованная. Эйлер придумал о-маленькие и о-большие, для того чтобы пределы считать (кстати меня на первом курсе очень позабавил препод, который гордо рассказывал о том, что эти о-маленькие/большие/красивые -- это кириллические о, потому что Эйлер был "русским" математиком). CS, будучи, если по-хорошему, прикладной математикой, позаимствовала концепцию. Когда ты выводишь для своего алгоритма оценку O(n*log(n)), то ты делаешь это методами математики. Ты строишь в голове конструктивное доказательство. Даже если ты делаешь это в уме и очень неформально: суть в том, что ты делаешь это таким образом, что ежели я скажу тебе "докажи свою оценку", ты легко сможешь выкатить строгое доказательство её.
> """
> Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма
> приводят к понятию асимптотической сложности алгоритма.
> """
Эмм... Чо? О-большое от f(x) -- это класс функций ограниченных f(x), то есть такие g(x), то существует такие a и x0 из R, что для любого x>x0 будет выполняться неравенство a*f(x) > g(x). Наверное, это можно сформулировать как "рассмотрение входных данных большого размера", но... Но это википедия, не надо относиться к ней излишне серьёзно. Кстати я вот не помню: то что я написал -- это если по-хорошму "О-большое при x→∞", но можно же таким же образом определить О-большое при x→0, например. По-идее, матан должен так делать, поскольку пределы бывают разные, и соответственно О-большое без указания предельной точки -- бессмыслица, а значит остаётся теоретическая возможность оценки асимптотической сложности программы, при x→π, и тогда эти разговоры о "большом размере" пойдут лесом. Хотя это может быть лишь теоретической возможностью (и таким образом формалистской придиркой), мне никогда вроде не приходилось оценивать сложность алгоритма не на бесконечности.
>> Про алгоритмы не всё можно доказать, что
>> хочется -- проблема останова, например, неразрешима в общем случае. Но про
>> mm что ты можешь доказать?
> Как по мне, проблема останова это порочный круг, алгоритм который пройдется по
> всем алгоритмам по списку и должен будет остановится на том алгоритме,
> который не останавливается, - не остановится никогда. Такие же приколы бывают
> с рекурсиями при определенных условиях, когда нет условия ограничивающее глубину рекурсии.
Бывает. Но попробуй какой-нибудь нетривиальный синтаксис парсить, и доказать, что время работы парсера не будет убегать в бесконечность. В смысле, что нет способа генерить последовательности из N символов, которые будут требовать O(e^N) ресурсов для парсинга. Вон на расте можно писать такие программы -- я видел пример генераторов парсеров, то есть синтаксис кодируется в системе типов, и на основании этого генерится программа-парсер, и на этапе компиляции 200 строк кода rustc выжирает гигабайты кода, и думает минут десять. С C++ можно то же самое вытворять легко. С C сложнее, может быть невозможно. Я ссылку найти не могу, на stackoverflow было обсуждение, как в разных языках можно одной строчкой кода получить бинарь на 20Tb. Как доказать что такое невозможно или ещё интереснее, что это возможно только таким-то и таким-то образом, которые мы считаем законными, а иначе такого не случится.
>> Ты знаешь алгоритм как детерминированно показать про любую программу наличие/отсутствие
>> проблем с mm?
> Алгоритм оценки "пространственной" сложность прост, банальные пошаговые замеры памяти
> (занимаемого пространства).
Это может работать если ты предположишь, что у тебя нет проблем с mm, типа mem-leak'ов. То есть если ты исходно заложишь предположение о том, что у тебя программа безбажна, то ты докажешь, что она безбажна. Нет ничего удивительного в этом, а? А теперь попробуй доказать, что ни при каком входе программа не течёт памятью.
>> Или ты просто _веришь_ в то, что ты
>> можешь любую программу избавить от багов с mm за конечное время?
> Не вижу проблемы. У любого детерминированного алгоритма есть оценка.
У тебя есть детерминированный алгоритм поиска багов в программах? И какова асимптотическая сложность этого алгоритма от SLOC? Я утверждаю, что у тебя нет детерминированного алгоритма не только для поиска всех багов, но даже для поиска багов относящихся к mm, таких как use-after-free, double-free и memory-leak. То что у тебя есть, либо не ловит всего, либо предмет той самой проблемы останова: ты не сможешь доказать, что твой алгоритм остановится когда-нибудь.
>> На чём эта вера основана? На "мамой клянус"? Может у тебя
>> хоть статистика есть, типа ты написал 100k строк кода, они широко
>> используются 10+ лет, и там до сих пор не нашли ни
>> одного бага с mm? На чём основана твоя вера?
> Заставь дурака Богу молиться - сами знаете что... это про статистику и
> веру.
Ты не ответил на вопрос: на чём основана твоя вера? Ты просто веришь? Или как-то доказываешь? Я уверен, что ты доказываешь. Пускай неформально, пускай ты не пишешь на листочке сложных доказательств непонятными математическими значками. Но доказываешь. Ты проделываешь в своей голове рассуждения вида: вот тут мы выделяем память Q, и сохраняем указатель на неё в структуре A... Больше отсюда указатель мы никуда не копируем, и структура A освобождает Q либо в деструкторе, либо раньше. Значит, если мы докажем, что память структуры A освобождается законным для языка путём (то есть так, чтобы деструктор отработал), то мы можем забыть про Q, с ней тоже всё будет ок.
Ты гоняешь в своей голове рассуждения по типу этого. Ну, точнее, тут одно из двух: либо гоняешь, либо быдлокодер. Я ставлю на первое. Но есть ли у тебя способ взяв код, выстроить достаточное количество таких рассуждений, чтобы утверждать что в программе нет проблем с mm (то есть нет use-after-free, double-free и memory-leak, я не включаю сюда buffer-overflow, потому что про него как раз можно выстроить конечной протяжённости рассуждения, которые докажут наличие или отсутствие).
