Комментарии 52
Типичный вопрос — что лучше — плохое, но стабильное и предсказуемое быстродействие (потребление памяти) или вариант, реализованный в нынешнем ширпотребом софте и железе — основные кейсы вроде быстрые, но есть граничные случае, которые регулярно "стреляют"
Уверен, что Вы правы. Но можно популяризировать более стабильные алгоритмы, что приведет к тому, что стоимость их внедрения уменьшиться, как следствие — разработка в целом станет более предсказуемая.
Условно — такая же история как с эджайл и девопс. Эти методики, культуры удорожают разработку, но при этом успокаивают поток непрерывной доставки ценности, делают его более предсказуемым. Это явно лучше, чем классическая схема с водопадом, когда мы либо что-то делаем и все ок (но дорого), либо теряем все и не получаем продукта
простите новичка… что такое "девопс"?
Уже даже вон команда PHP занялась вопросом аллокаторов и сразу получила двукратный бонус производительности. А потом, после полировки внутренних структур, постепенно ещё почти такой же.
Все чаще и чаще подобного рода статьи обделены вниманием со стороны аудитории хабра. Плюсов меньше, нежели у соседних "новостей". Как результат — еще меньше шансов на просмотр.
При этом когда ставишь минус соседям — есть выбор между вариантами причин. Низкий технический уровень материала, как по мне, один из самых востребованных. Есть ли резон добавить подобный опрос при плюсовании? Я бы нажал "Действительно полезно" или "The piece of habracake".
На хабре то?
А почему нет?
Ведь по сути людей занимающихся системами реального времени не так много, ещё часть может заинтересоваться "для общего развития" да и то после первого абзаца может передумать. Ведь это нормально для текущего момента истории, программирование выходит в массы, основная занятость в решении повседневных задач, "популярное на слуху" это bigdata, контейнеры js это всё очень далеко от систем реального времени.
А какие недостатки данного подхода? Почему все менажеры динамической памяти не использует этот алгоритм?
И вообще, главный недостаток статьи, это то, что не объяснено как все это работает. Конечно, код (при этом небольшой!) это прекрасно, но объяснение как это работает и почему сделано так, а не по другому многим понравится и повысит читаемость статьи.
Вы правы, я немного перешагнул через практическую сторону. Это отчасти умышленно, ведь смысл публикации не в предложении новых технических методов, а в информировании коллег о том, что популярные представления о методах работы с памятью в системах реального времени зачастую ошибочны.
Рассматриваемые методы не новы и описаны в диссертации по ссылке и других гуглимых ресурсах. В моей библиотеке реализован алгоритм Half-Fit — один из трёх основных, наряду с более простым buddy allocator и более сложным TLSF. Детальное описание есть на странице 27-28, плюс комментарии к моей реализации есть прямо в README моей библиотеки. Buddy allocator я исключил из-за его более высокой (но детерминированной!) вычислительной сложности в сравнении с half-fit (который был предложен позже и более совершенен), TLSF же имеет более тяжёлый худший случай фрагментации за исключением одного вырожденного случая, где его поведение эквивалентно half-fit. Я мог бы набросать аналогичную заметку по этой теме, но зачем повторяться, ведь в источниках по ссылкам вопрос рассмотрен достаточно детально.
Обычные, классические приложения (не (жёсткого) реального времени) не используют рассмотренные подходы потому что их средний случай сильно уступает среднему случаю популярных сегодня алгоритмов (например, dlmalloc). C худшим случаем всё наоборот! Как я отметил в тексте, анализ систем реального времени рассматривает прежде всего именно худший случай, в отличие от обычных приложений.
Об обосновании различий в подходах я ещё только что вот написал ответом к первому комментарию выше, посмотрите.
Вот я хз, что такое «традиционный» и что такое «блочный» аллокатор, что понимается под «катастрофической фрагментацией», хотя и знаком с основами и проблемами. А что скажет «традиционный» читатель хабра?
А тот факт, что Вам не разжевали и в рот не положили объясняется просто: это НЕ учебная статья, а заметка от профессионала для профессионалов.
которая несёт гораздо больше пользы, чем бОльшая часть публикаций за день вместе взятых.
С этим нельзя не согласится. Поэтому я и плюсанул и статью и карму автора.
А тот факт, что Вам не разжевали и в рот не положили объясняется просто: это НЕ учебная статья, а заметка от профессионала для профессионалов.
А с этим согласится уже нельзя. Для заметки есть твитер и редит. На Хабре пишут именно статьи где объясняют. Такую статью тоже можно написать "для профессионалов". А можно написать и для школьников. Это как раз зависит от автора.
Рассматриваемые методы не новы и описаны в диссертации по ссылке и других гуглимых ресурсах.
Диссертация это содержит 183 страниц текста на академическом английском. И вы предлагаете нам прочитать ее, чтобы понять как работает 500 строк кода на C.
Нет, я понимаю, что это будет очень полезно для моего роста как программиста, но доступное и простое объяснение принципов (а не высокого академичного стиля) думаю будет очень полезно для аудитории хабра.
потому что их средний случай сильно уступает среднему случаю популярных сегодня алгоритмов (например, dlmalloc)
А насколько сильно? Хотя бы приблизительно на глаз? Делались ли некие тесты и измерения?
Диссертация это содержит 183 страниц текста на академическом английском. И вы предлагаете нам прочитать ее, чтобы понять как работает 500 строк кода на C.
Я предлагаю вам прочитать только две; как я написал выше, "детальное описание есть на странице 27-28".
А насколько сильно? Хотя бы приблизительно на глаз? Делались ли некие тесты и измерения?
Я не делал практических замеров, потому что меня интересует доказуемый худший случай. Однако, я согласен с вами, что в целом это вопрос интересный.
Доводилось даже встречать системы РВ, в которых пользовательский интерпретатор и сетевой стек «кормятся» из одной кучи (хотя аллокатор был нетривиальный).
А в целом, спасибо, интересно, еще раз хорошо показывает, что нет «серебряной пули» и что нужно правильно выбирать аллокатор и настраивать его под конкретную специфику даже если говорить про обычные приложения, у того же популярного jemalloc, очень много опций при сборке, которые стоит подкрутить, чтобы получить результаты получше.
Обратите внимание, что если вы работаете над системой реального времени, средний случай вас обычно не интересует. Практические замеры позволяют оценить именно его (исключая, возможно, какие-то очень особые подходы, специально предназначенные для поиска граничных случаев, не берусь обобщать). Для обычных (не реального времени) систем, конечно, сравнить было бы интересно. Я не готов браться за это самостоятельно, но мог бы посодействовать, если найдутся желающие.
влияют ли некоторые детали реализации RTOS на эффективность применения?
у некоторых процессоров для RTOS должны быть свои особенности, которые позволили бы оптимизировать некоторые аспекты работы с памятью.
Не могли бы вы раскрыть тему подробнее, пожалуйста? О каких особенностях тут идёт речь?
Не могли бы вы раскрыть тему подробнее, пожалуйста? О каких особенностях тут идёт речь?
Это старая как мир притча. Несколько десятилетий назад отдельные группы исследователей продвигали идею закладывания в архитектуру отдельных RTOS идей. От MMU до конвейеров и логики работы кэшей. Поддержки у вендоров хитрый план по ускоспециализированному железу не нашел и достаточно быстро сдулся. Но эхо в академической среде все еще витает.
Или, например, даже в аллокаторах общего назначения, пытаются использовать некоторые сведения из спецификации процессоров и реализации ОС, чтобы улучшить производительность, например, читают напрямую из регистра идентификатор потока github.com/microsoft/mimalloc/blob/6a744a8549263696ef8d620006a0de2249e59b46/include/mimalloc-internal.h#L618
Просто, мне казалось, что в RTOS сфере вообще должны активно использовать различные уловки, чтобы выжать максимум из производительности.
Просто, мне казалось, что в RTOS сфере вообще должны активно использовать различные уловки, чтобы выжать максимум из производительности.
RT к производительности никакого отношения не имеет. Real-time не значит быстро, но с гарантией своевременности. Тут можно с некоторым допущением противопоставить интерактивность и предсказуемость. Первое к ОС общего назначения, второе к ОСРВ.
Мотивированные коллеги есть. :)
Тема очень интересная! Но в полной мере заняться данным вопросом, также как и Вам, не позволяет наличие свободного времени.
Поясню, казалось бы ОСРВ должно именно об худшем случае выделения ресурсов и заботится. однако в современной системе решение данной проблемы похоже для всех случаев не возможно. Поэтому и появляются описываемые Вами трюки как в lwIP. Мы пришли к похожему подходу, то есть какая то подсистема требует выделения специфической памяти, предположим тот же IP стек. Но тогда ведь можно выделить пул на максимальное количество объектов максимального размера и выделять за гарантированное время, не взирая на накладные расходы которых требует отдельный аллокатор.
Но повторюсь, тема очень интересная и близкая нам! Я бы предложил поставить issue. Как минимум попробуем студентов подключить, чтобы дополнительно свойства исследовать на тех или иных задачах.
Но тогда ведь можно выделить пул на максимальное количество объектов максимального размера и выделять за гарантированное время, не взирая на накладные расходы которых требует отдельный аллокатор.
Тут проблема в том, что если максимальный размер достаточно велик (это часто так в моих задачах, например), то подход с блочной аллокацией как вы его описали окажется менее эффективным по памяти, чем выделение фрагментов произвольного размера. И то, и другое можно делать за гарантированное время.
Но повторюсь, тема очень интересная и близкая нам! Я бы предложил поставить issue. Как минимум попробуем студентов подключить, чтобы дополнительно свойства исследовать на тех или иных задачах.
С нетерпением буду ждать ваших студентов.
Безусловно, за все нужно платить. Я просто имел в виду, что в разных подсистемах могут быть свои специализированные аллокаторы, и это зачастую эффективнее (или проще) чем делать один универсальный аллокатор для системы.
> С нетерпением буду ждать ваших студентов.
ну студенты не мои (и не наши). Их тоже сначала нужно заинтерисовать. :)
(спустя месяц) готово: https://github.com/UAVCAN/libcanard/pull/142
Не являюсь сторонником динамического выделения памяти в системах жёсткого реального времени. Вообще.
Поэтому вопрос по "Работая над реализацией встраиваемого сетевого стека для одного протокола реального времени" — что же это за протокол такой, для которого не получилось сделать сетевой стек без динамического выделения памяти? Ведь протоколы реального времени по идее как раз и разрабатываются, чтобы не требовать динамической памяти у процесса, который бы с ними работал.
Не являюсь сторонником динамического выделения памяти в системах жёсткого реального времени. Вообще.
Динамическое выделение и предсказуемость временных характеристик не связаны, как я показал в статье. Чем обсусловлена ваша позиция?
что же это за протокол такой, для которого не получилось сделать сетевой стек без динамического выделения памяти?
Если выйти за рамки тривиальных сигнальных протоколов, то отказ от динамической памяти не позволит сделать реализацию для общего случая, не делающую предположений о функциях и поведении приложения. Я работаю как раз над такой общей реализацией.
Если конкретные временные и поведенческие характеристики приложения хорошо известны, то, конечно, можно насрезать углов и свести реализацию к работе со статически предвыделенными буферами и т.п. Выбор оптимального подхода определяется главным образом требованиями к валидации и верификации ПО и доступными ресурсами на разработку.
Динамическое выделение и предсказуемость временных характеристик не связаны, как я показал в статье. Чем обсусловлена ваша позиция?
Да хотя бы тем, что предсказывай, не предсказывай временные характеристики, но если malloc вернет null и этим скажет "Все чувак, сегодня на Луну не летим чайник не включится", то это не жесткое реальное время, а черт знает что.
Если выйти за рамки тривиальных сигнальных протоколов, то отказ от динамической памяти не позволит сделать реализацию для общего случая, не делающую предположений о функциях и поведении приложения. Я работаю как раз над такой общей реализацией.
Проектируя систему жесткого реального времени вы уже делаете предположения. Например о максимальном времени оклика, дедлайнах, джиттере. То есть вы сразу же себе ставите рамки, что система "в таких условиях будет работать, а в таких — нет".
но если malloc вернет null и этим скажет "Все чувак, сегодня на Луну не летим чайник не включится", то это не жесткое реальное время, а черт знает что.
Для исключения этого существует модель худшего случая фрагментации. Вы можете статически доказать, что чайник всегда включится, если известна потребность приложения в памяти. Можно провести аналогии с определением размера стека, если угодно.
Может, вы сможете развеять мои сомнения?
Я не развею ваши сомнения. Точное прогнозирование выполняется в одних случаях легко, в других нет; ваш пример из второго. Если развивать пример дальше, то предсказание временных/ресурсных характеристик системы с SQLite потребует анализа не только движка БД, но и логики, что работает поверх и формирует запросы.
Вы можете статически доказать, что чайник всегда включится, если известна потребность приложения в памяти.
Так если потребность в памяти известна, зачем динамически ее выделять? Взял, выделил себе нужное количество памяти перед стартом исходя из худшего случая и работаешь с ней статически. И никаких расходов на дефрагментацию.
Что вы сэкономите, выделяя меньшее количество памяти, чем нужно в худшем случае для корректной работы приложения?
Так если потребность в памяти известна, зачем динамически ее выделять?
Что вы сэкономите, выделяя меньшее количество памяти, чем нужно в худшем случае для корректной работы приложения?
Вы сэкономите память и затраты когнитивных ресурсов на реализацию логики вашего приложения. Динамическое выделение позволяет удовлетворить потребность приложения в памяти при меньшем её общем размере благодаря разнесению перекрывающихся в адресном пространстве аллокаций во времени. Упрощение логики же достигается обобщением задач управления памятью в аллокаторе. Об этом пишет и Хертер:
While often yielding better structured source code, another, more important advantage of dynamic memory allocation is to alleviate the programmer from finding ways to cope with a small amount of memory. I.e., alleviating him or her from assigning memory addresses such that objects not allocated contemporaneously can share memory locations to reduce overall memory consumption.
Например, если ваш чайник требует 100 кб под нужды системы управления во время полёта на Луну, и ещё столько же во время движения по её поверхности, вы можете сэкономить половину, зная, что эти режимы взаимоисключающи и не могут быть активны единовременно. Вместо того, чтобы делать оверлеи на буфере вручную, вы просто делегируете это дело аллокатору.
Однако, от моего внимания, разумеется, не ускользает то факт, что снижение ресурсоёмкости и упрощение логики, которое даёт динамическое размещение, даётся ценою более сложной модели поведения программы. Я согласен с вашей подразумеваемой позицией, что динамическое размещение не является серебряной пулей, что его цена высока, и во многих случаях не является оправданной. В следующей цитате из поста ключевым словом является "разумное":
Для меня было очевидным, что множество задач реального времени, где разумное применение хорошо охарактеризованных (предсказуемых) алгоритмов выделения памяти является оправданным, не исчерпывается моим стеком.
Например, если ваш чайник требует 100 кб под нужды системы управления во время полёта на Луну, и ещё столько же во время движения по её поверхности, вы можете сэкономить половину, зная, что эти режимы взаимоисключающи и не могут быть активны единовременно. Вместо того, чтобы делать оверлеи на буфере вручную, вы просто делегируете это дело аллокатору.
Подождите. Выделение памяти под определенную реалтаймовую задачу до того, как она начала исполняться и возврат памяти обратно при ее завершении — это одно и в принципе это не мешает следовать принципам жесткого реального времени. Вы можете вполне в одном МК иметь задачи "взлет" и "посадка", которые никогда не исполняются одновременно, и динамически выделять под них память перед первым запуском одной из этих задач. И для этого не нужен специальный реалтаймовый аллокатор.
Но это совсем не то же самое, что выделять память динамически, во время работы реалтаймовой задачи. Вот эту проблему я обсуждаю и надеюсь, вы меня понимаете. Здесь нет разнесения во времени — все внешние сигналы могут вдруг объявиться одновременно и на них придется ответить в течении гарантированного времени. При этом и возникает вопрос — что мы экономим, динамически выделяя память на данном этапе работы приложения, когда каждый программный цикл на счету?
Ресурсы логики приложения? Да нет. Приложению по сути пофиг куда указывает поинтер на переменную — в статически размеченную область или динамически. Главное, чтобы это было место именно под эту переменную.
Экономия памяти? Опять же как, если мы знаем, что нам может понадобиться Х килобайт в худшем случае? Будем рассчитывать, что этот случай не наступит?
Мне кажется, что вы излишне углубляетесь в конкретику моего примера. Можно сконструировать другой пример, где вместо памяти под нужды системы управления межпланетным чайником мы будем выделять буферы под сообщения, что он принимает из ЦУП. Чайнику неизвестно, какие придут сообщения, в какой момент, и как они будут упорядочены во времени. В конечном итоге, потребный ресурс памяти будет ограничен сверху пропускной способностью линии связи и способностью чайника к обработке сообщений по мере их поступления. Если вас интересуют более конкретные примеры, посмотрите, например, на организацию работы с памятью в lwIP. Конечно, к системам жёсткого реального времени его можно отнести с натяжкой, но родственные сетевые технологии используются, например, в аэронавтике (AFDX, ARINC 664) и другом транспорте (SOME/IP, DDS/RTPS). Если пойти дальше, федеральное агентство аэронавтики США вполне всерьёз обсуждает тонкости реализаций буферизации и управления памятью в публикации Safety and Certification Approaches for Ethernet-Based Databuses. Вообще, современные и зарождающиеся сетевые протоколы на транспорте отличаются от предшественников существенно более высокой сложностью и предлагаемыми абстракциями, которые часто требуют более сложных подходов к реализации. Я не хотел бы сейчас погружаться в тонкости сетевых протоколов реального времени для отказоустойчивых систем, потому что тема крайне обширная и выведет нас далеко за рамки текущего вопроса.
Ресурсы логики приложения?
В моём сообщении выше речь шла о мыслительных ресурсах программиста, простите, если выразился неясно. Именно об их экономии рассуждает и Хертер. Они ценны не только с точки зрения человекочасов, затраченных на проектирование и реализацию ПО, но и с позиции вероятности появления непредусмотренных поведений в программе. Вы не хуже меня знаете, что человеческий мозг слаб, и наши возможности по удержанию в голове сложных абстракций ограничены.
Можно сконструировать другой пример, где вместо памяти под нужды системы управления межпланетным чайником мы будем выделять буферы под сообщения, что он принимает из ЦУП. Чайнику неизвестно, какие придут сообщения, в какой момент, и как они будут упорядочены во времени. В конечном итоге, потребный ресурс памяти будет ограничен сверху пропускной способностью линии связи и способностью чайника к обработке сообщений по мере их поступления.
Не забываем что есть лимит времени на обработку. Т.е. есть макс количество сообщений которое способен обработать чайник оставаясь системой реального времени. Если приход сообщений превышает их обработку/количество сообщений в очереди превысило какой то на перед заданный предел, то все уже поломалось, независимо от возможности расширить буфер, поелику это уже не система реального времени.
но собственно, статья не отвечает и на более простые вопросы
так чайник как РТ и не обязан обрабатывать все сообщения. вполне имеет право ответить: — «вы кто такие, подождите»Ну это уже в зависимости от зависимости кто там че — ЦУП будет кипятильник юзать пока он раздуплится или чайник окирпичится от того что он нереалтаймовым стал — не суть важно. Главное что ни в том ни в другом случае в динамическом буфере смысла нет. Обычный кольцевой и все ОК.
но собственно, статья не отвечает и на более простые вопросы
И самое главное на вопрос — а какой смысл вообще динамического перераспределения буферов в реалтаймовой софтине?
При этом и возникает вопрос — что мы экономим, динамически выделяя память на данном этапе работы приложения, когда каждый программный цикл на счету?Запас вычислительной мощности это вопрос отдела оборудования. При этом накладные расходы на распределения памяти слишеом незначительны и происходит оно в любом случае редко чтобы могло на что то особо повлиять. Тут есть другой гораздо более важный аспект. А именно — гарантировать наличие нужной памяти можно только имея ее предварительно распределенной. Т.е. если оно все одновременно произойдет то просто вылетет bad_alloc и все упадет — динамически то распределяют только для того чтобы впихнуть невпихуемое — т.е. поюзать память по очереди если ее не хватает на все сразу. И собственно вот с этим бороться окромя четкого разделения по времени способов нет.
Можно сконструировать другой пример, где вместо памяти под нужды системы управления межпланетным чайником мы будем выделять буферы под сообщения, что он принимает из ЦУП. Чайнику неизвестно, какие придут сообщения, в какой момент, и как они будут упорядочены во времени. В конечном итоге, потребный ресурс памяти будет ограничен сверху пропускной способностью линии связи и способностью чайника к обработке сообщений по мере их поступления.
Не забываем что есть лимит времени на обработку. Т.е. есть макс количество сообщений которое способен обработать чайник оставаясь системой реального времени. Если приход сообщений превышает их обработку/количество сообщений в очереди превысило какой то на перед заданный предел, то все уже поломалось, независимо от возможности расширить буфер, поелику это уже не система реального времени.
(ошибся веткой)
Динамическая память в системах жёсткого реального времени