Существую две структуры данных, которые известны любому программисту и которые настолько считаются аксиомами, что никто не пытается даже проанализировать, а так ли они нужны, есть ли от них польза и не превышает ли вред от них эту самую пользу.
Очередь
В первую очередь обсудим очередь. В чём смысл очереди? Очередь — это буфер. А когда нам нужен буфер? Когда мы не успеваем обработать входящие события в темпе их поступления.
В связи с вышесказанным возникает один единственный вопрос: а зачем? Ответ в том, что мы надеемся, что что-то случится и вдруг система позволит нам обработать события.
Сначала разберемся с первым пунктом. Что должно случиться с системой, что она вдруг перестанет тормозить и начнет переваривать данные быстрее? Скорее всего, просто закончится какой-то ресурсоёмкий процесс и освободит ресурсы. А что, если этого не произойдет? Что делать с данными? Известно что: либо мы просто их сбрасываем, либо вся система просто виснет от нехватки ресурсов.
Дак вот, есть два вопроса:
- А почему нельзя отбрасывать данные сразу, если мы знаем, что у нас на их обработку нет ресурсов? То есть почему нельзя сделать очередь из одного элемента?
- Либо обратный вопрос. Почему мы питаем иллюзии и не снабжаем систему необходимым количеством ресурсов, чтобы обрабатывать данные в темпе поступления?
Ответы на эти вопросы, собственно, очевидны. Мы просто не умеем проектировать программно-аппаратные комплексы. Потому как если бы мы их умели проектировать, то мы бы знали сколько у нас входных данных, темп их поступления, сколько нам нужно на их обработку и, соответственно, могли бы высчитать реальную потребность в ресурсах. Но современное состояние средств и методологий разработки ИКТ, за исключением части технологических систем (и то далеко не всех), не позволяет нам сделать объективные расчеты потребности в ресурсах.
А закрываем мы эти недочёты всяческими буферами, в частности, в виде очередей. В результате, мы имеем бомбу, заложенную в основание здания ещё на уровне котлована, потому что эти костыли служат источником разнообразных презанятнейших и трудно уловимых проблем с надежностью, безопасностью и просто качеством работы.
Но, продолжим, впереди у нас моя самая "любимая" структура — стек!
Стек
Вот уж точно, как говорил в своё время Хоар про Null, что это ошибка на миллиард долларов, так то же самое можно сказать и про стек.
Более отвратительной и бессмысленной структуры я не могу себе припомнить. Она хуже Null, много хуже. В аду нужно предусмотреть отдельный круг для тех, кто придумал стеки и кто их ввел в широкий оборот.
Итак, что, собственно, за проблема со стеком? Да ровно та же, что и с очередью. Стеки принципиально невозможно упорядочить. Как только появится человек, который точно предскажет сколько памяти нужно стеку любой произвольной программы, я лично извинюсь и напишу огромную статью о том, что я был неправ и попрошу прощения.
Но что-то мне подсказывает, что вряд-ли это случится в обозримом будущем.
Проанализируем, зачем нам нужны стеки? Да ровно для того же, для чего и очереди. Это буфер. То есть это костыли для ленивого ума, который не хочет правильно проектировать программно-аппаратные комплексы.
Я выдвигаю теорему: любой стековый алгоритм может быть конвертирован в цикл, а те, которые не могут быть конвертированы — плохи.
В помойку должны быть выброшены вызовы подпрограмм с передачей параметров через стек, туда же должна пойти рекурсия, не раскрывающаяся в цикл и прочие ужасы.
То есть есть два кейса:
- Рекурсия, реализуемая в виде раскрытия стекового алгоритма в цикл с блоком данных, изменяемых в процессе выполнения цикла.
- Если же вам нужно передавать параметры, то вы организуете систему микропрограмм с обменом сообщениями. А про обмен сообщениями мы выходим на очереди, которые были описаны в первой части статьи.
BlockOut
В 1995-м году мною с моим одногруппником были сформулированы принципы построения операционной системы, которая исключала обе этих парадигмы.
Принципы были следующими:
- Программное обеспечение — сети взаимодействующих процессов.
- Взаимодействие процессов осуществляется путём обмена сообщениями.
- Сеть взаимодействующих процессов организована следующим образом: источниками первичных сообщений в такой сети являются только события от внешнего мира, поставляемые оборудованием, конечными потребителями сообщений являются только устройства, которые производят действия во внешнем мире. То есть сеть начинается в реальном мире и заканчивается в нем.
- Процессы не могут обладать приоритетами. Приоритетами могут обладать только сети процессов.
- Сеть никогда не буферизирует сообщения. Программно-аппаратный комплекс должен быть организован так, чтобы успевать обрабатывать сообщения в темпе их поступления из внешнего мира.
- Аппаратный комплекс представляет собой сеть вычислительных узлов, связанных каналами связи.
- Каждый узел имеет "стоимость", зависящую от его вычислительной мощности, объема памяти, загруженности и весового коэффициента, учитывающего затраты на его создание и поддержание.
- Каждый канал связи имеет "стоимость", зависящую от его пропускной способности, загруженности и весового коэффициента, учитывающего затраты на его создание и поддержание.
- Операционная система обеспечивает запуск процессов в ответ на поступающие сообщения и маршрутизацию сообщений.
- Операционная система обеспечивает распределение процессов и сообщений по вычислительным узлам, оптимизируя функцию f(cpu,mem) на сетевой топологии с учётом стоимости передачи кода процесса и сообщений на узел.
- С учётом построения системы, всегда можно точно вычислить необходимое количество памяти для процесса. Необходимое количество времени счёта можно точно вычислить на основе анализа алгоритма.
Процессор BIND
В рамках преподавательской деятельности, вместе со студентами в своё время принял участие в конкурсе IEEE эмуляторов CPU. Был разработан бесстековый процессор общего назначения гарвардской архитектуры по системе команд похожий на ранние ARMы. Так же в CPU была инкорпорирована забытая идея транспьютеров и процессор был оснащён 16 8-битными каналами приема-передачи.
Соответственно, в процессоре отсутствовали операции вызова/возврата. Возможен был только условный/безусловный переход. С учётом того, что на ассемблере сейчас практически никто не пишет, все вопросы по генерации программы в машинных кодах, предполагалось возложить на компилятор.
Основная цель данного процессора была в том, чтобы бесшовно поддержать принципы ОС Blockout на уровне аппаратуры, создав в локальном вычислительном узле сеть процессоров, соединенных каналами связи, по которым уже будут распределяться процессы.
Выводы
В тексте показаны неустранимые недостатки структур данных очередь и стек. Приведены принципы проектирования программных и аппаратных комплексов, позволяющих исключить данные структуры из практики применения.
Данный текст является, скорее, компиляцией мыслей, которые имели место быть на протяжении всей карьеры в ИТ, чтобы, так сказать, свести всё в одно место.
Комментарии (79)
VioletGiraffe
19.11.2018 14:06+6Не в обиду автору, но статья показалась смесью капитанства и д'Артаньянства. Идеи процессора и ОС интересные, но практическая польза и преимущества над традиционными парадигмами плохо освещены, на мой взгляд.
Sap_ru
19.11.2018 14:19+6Ну бред же. Отказываться от очередей только из-за боязни их переполнения?
"Как только появится человек, который точно предскажет сколько памяти нужно стеку любой произвольной программы, я лично извинюсь и напишу огромную статью о том, что я был неправ и попрошу прощения."
Ну, вот, я писал отказоустойчивые программы без использования динамической памяти, предсказуемым поведением по любым видам нагрузок и перегрузок и широким использованием стеков, и что? В том числе и работу с сетью, в которой всё через очереди и стеки было. Программа будет использовать ровно столько памяти, сколько предусмотрел до для этого программист. Существует с десяток способов ограничить глубину стека и очереди. Как минимум для очереди и сети:
0) Использовать стеки/очереди без динамической памяти. Это, как бы, аксиома. Если у тебя критическое применение, то динамическая память это зло. Да, и быстрее это. Но на стеки и очереди это не влияет.
1) В случае переполнения отбрасывать старые пакеты с другого конца очереди при добавлении новых.
2) Ввести упреждающий сигнал и начать «мягко» регулировать поступление новых данных при заполнении, например, 80% очереди, а по полному заполнению исполнять пункт 1.
3) По заполнении до критической отметки начинать отбрасывать данные с указанным рейтом. Например, на 90% начинаем терять 30% данных. Можно совмещать с 1 и 2.
4) Тупо отбрасывать новые данные по заполнению очереди.
Это только решения «в лоб», а дальше — и т.д. и т.п.
Лично на этом дважды писал полный TCP/IP Berkeley стек и множество раз использовал для других применений.
Очевидно, что испокон века все серьёзные отказоустойчивые системы используют статическое выделение памяти. Как по вашему весь космос работает и самолёты летают?! Более того, даже серьёзные промышленные контроллеры используют только статическое выделение памяти (либо, однократное динамическое)!
Процессы могут и ДОЛЖНЫ обладать приоритетами. Только так вы можете по настоящему гарантировать работоспособность системы под произвольной нагрузкой — вы искусственно локализуете все «бутылочные горлышки» и принимаете меры к тому, чтобы перегрузка по данным не влияла на стабильность работы, заодно можете строго ограничения процессорного времени по задачам, чтобы гарантировать реальное время с нужной дискретностью. В противном случае все гарантии ничего не стоят и базируются на предположении разработчика, что он учёл всё возможные варианты и распределения нагрузок. Не уверен, даже, что для сложных систем вообще возможно строгое доказательство и прогноз работоспособности, если не используются приоритеты, т.к. не всегда возможен полноценный анализ всей системы (например, в силу её размеров).
Ваш подход, возможно, тоже имеет право на жизнь, но есть мнение, что сложность его реализации, гибкость, предсказуемость поведения и т.п. проигрывают другим более простым подходам.
Вот это вообще смело: "… есть это костыли для ленивого ума, который не хочет правильно проектировать программно-аппаратные комплексы".
А мужики-то не знают!!! На этом месте хорошо бы узнать сколько отказоустойчивого ПО для ответственных применений, совершенно не использующего стеков и очередей, написал автор и сколько времени это ПО уже эксплуатируется.evocatus
19.11.2018 14:54Маргарет Гамильтон, главный программист Аполлона-11 в своё время спасла экипаж, который первым сел на Луну (Армстронг, Коллинз, Олдрин), реализовав принципы асинхронного программирования и приоретизации процессов. За три минуты до прилунения лунного модуля сработало несколько аварийных сигнальных устройств. Компьютер был перегружен входящими данными – в стыковочной радарной системе произошло непроизвольное обновление счетчика, что привело к запросу на выполнение компьютером большего числа операций, чем он был способен обработать.
Но они сели, а потом вернулись, потому что Маргарет (ей сейчас 82 года) очень умная и ответственная.
MaxxONE
19.11.2018 14:21+4Сеть никогда не буферизирует сообщения. Программно-аппаратный комплекс должен быть организован так, чтобы успевать обрабатывать сообщения в темпе их поступления из внешнего мира.
Я бы взглянул на это.Sap_ru
19.11.2018 14:26+2Именно. Особенно на пару с тем фактом, что сейчас пропускная способность каналов данных, как правило, однозначно превышает способность процессоров к обработке этих данных. И это справедливо и для микроконтроллеров со 100-мегабитным Ethernet, и для полноценных серверов в который воткнули 10G канал (а то и несколько) и забросали тяжёлыми запросами.
Sap_ru
19.11.2018 14:28+3Кстати, автор, похоже, вообще никогда с сетями не работал.
Т.к. от асинхронного, ориентированного на очереди и непредсказуемого по своей природе TCP от должен бежать без оглядки, но даже в этом случае есть серебряная пуля, которая его неизбежно догонит — «ARP».Alexeyslav
19.11.2018 14:53-2Сеть это не только компьютерная сеть, мне кажется в статье шла речь о сети как совокупности вычислительных ядер соединённых между собой, что-то вроде многоядерной архитектуры. и я не увидел в статье причин отказа от таких вещей как очередь и стек, там говорится что они не нужны на системном уровне, т.е. на уровне исполнения команд процессором. А в самих программах можно формировать всевозможные стеки и очереди, аппаратные для передачи во внешний мир и т.д. Только лишь исключить их использование самим процессором для выполнения программ.
Sap_ru
19.11.2018 15:47+1Прежде всего любой компьютер оперирует каким-то данными, которые в него откуда-то поступают. Во-вторых, компьютеры работают в реальном времени. Оно может быть жёстким, может быть крайне мягким (ну минуту-то выполним запрос). Если же мы говорим о ситуации, когда входные данные не поступают в реальном времени, например, они полностью известны до запуска программы, и речь о реальном времени не идёт (на важен факт обработки данных, а не время), то авторский текст становится ещё долее бессмысленным.
А если речь идёт о внутреннем устройстве, логическом, физическом, не важно, то ничего не меняется. Т.к. тот же TCP/IP стек на пару с физическим уровнем, это всегда набор отдельных подзадач, работающих асинхронно и связанных очередями данных. Такова сущность всех каналов связи. Даже глупо-аппаратный канал процессор-кэш-память уже давно является асинхронным и связан очередями.
Короче, данные в любом случае приходят асинхронно от процессора. И если вы хотите, чтобы система работала совершенно всегда, то вы должны гарантировать, что если данные по любой причине будут приходить быстрее, чем работает процессор, то поведение системы должно быть предсказуемым. И сделать того без стеков/очередей нельзя. Точнее, теоретически, можно, но производительность системы будет намного ниже максимальной, т.к. всё в конечном итоге будет сводиться к синхронной работе.
Если у вас есть программа, которая может справляться со средним потоком данных Q и кратковременным пиковым потоком, например, 8Q — типичные цифры — то автор зачем-то предлагает решение, которое, работая с той же вычислительной мощностью, будет справляться с потоком 0.25Q, без всяких возможностей по даже кратковременной работе с бОльшими потоками данных. Вопрос — на фига? Тогда уже нужно просто брать и писать полностью синхронную программу. Сильно проще получится, да, ещё работать будет сильно быстрее, чем то, что автор предлагает.Alexeyslav
19.11.2018 16:37Нет, он предлагает сделать систему которая справляется с потоком 8Q изначально. Причем справляется как: каждое ядро может обработать поток в 0.25Q но в «процессоре» 40 таких ядер. Приходит событие, и попадает в свободное ядро где выполняется со скоростью 0.25, если ядро не успело а пришла новая порция данных-событие оно попадает на второе ядро и никуда не пропадает. Буфера нет, с задачей даже под пиковой нагрузкой справляемся.
Та же кеш-память она на выполнение программы не влияет, только на среднюю скорость исполнения инструкций, и то для процессоров привычных нам. А если тот самый «процессор» работает с быстрой памятью изначально? Если у него кроме кеша ничего и не нужно? Напоминает чем-то видеокарты с сотнями ядер…Sap_ru
19.11.2018 18:20+1Он предлагает синхронную обработку. По нынешней терминологии — параллельный масштабируемый конвейер с глубиной в один уровень. Что очень старая технология.
Кэш память непосредственно влияет на скорость выполнения программы. Именно на среднюю, через пиковую.
Есдли у вас есть канал данных (физическй или логический — не важно) и вы его синхронного принимаете и синхронно обрабатываете, то вы получаете жутко неэффективное решение. Вы выгоднее сначала асинхронно принять данные, а потом так же асинхронно обрабатывать на дальнейших стадиях. В этом случае вы успешно справляетесь с пиковыми нагрузками, получаете бОльший средний темп обработки и при всём при этом гарантируете стабильность работы системы при избытке данных.
Конкретно у него, если не будет приоритетов задач, то средняя производительность будет равна пиковой.
В этот момент времени у вас пять ядер занимается приёмом. А в следующий момент у вас одновременно и приём и обработка. А потом только обработка, а новый данный нет. Без приоритетов и очередей всё это упрётся в среднюю производительность сразу же. А с приоритетами и очередями вы можете балансировать ресурсы в зависимости от текущей нагрузки, достигая бОльшей пропускной способности. А если он в свою идеологию добавить приоритеты и буфера, то она станет окончательно бессмысленной, т.к. он всё это придумал только из-за того, что боялся приоритетов и очередей.
evocatus
19.11.2018 14:29+6Мне кажется, вы неправы.
Если система не способна обрабатывать все сообщения даже с очередью, значит действительно кто-то очень серьёзно ошибся на ранних этапах разработки — не рассчитал скорость. Но имеется в виду средняя скорость. Очередь нужна не для того, чтобы устранить разрыв в средней скорости (это невозможно), а чтобы нейтрализовать колебания вокруг этого среднего значения (а они случаются везде и всюду по множеству причин, физических и программных). А ещё она может помочь устранить фрагментацию по времени.
П. 3 в списке мне непонятен. А как же служебные задачи? Допустим реакцию на перегрев процессора вы отправите в категорию внешних событий. А как же чисто программные вещи? Планировщик задач? Файловая система? Они являются источниками множества событий, нужных и полезных, которые должна совершаться.
Маленький пример: данные посылаются из FPGA в компьютер на MAC-уровне протокола Ethernet. Но эти данные должны упаковываться в пакеты Ethernet и когда данные поступили, я должен начать формировать пакет (т.е. потратить несколько тактов шины AXI Stream IP-ядра Ethernet MAC на передачу заголовка пакета). А где будут храниться данные пока я посылаю заголовок пакета? В буфере FIFO! Вот у нас уже очередь. И таких мест в современных программно-аппаратных комплексах тысячи и тысячи. Как вы собираетесь от них избавиться сохранив совместимость с существующими протоколами передачи данных?
Вся эта идея напоминает мне попытки создать троичный компьютер, потому что теоретически доказано, что самая эффективная система счисления для вычислителя имеет основание e = 2.718281828.
Пункт 5. «Сеть никогда не буферизует сообщения». У вас многозадачная ОС с разделением времени? Если да, то я не знаю как вы собираетесь избавиться от буферизации — я не верю, что это возможно. Даже допустим, что вы уничтожили кэш у процессора (а это вообще хорошая штука, во всяком случае сейчас, когда время доступа к оперативной памяти на 2 порядка медленнее времени доступа к регистру CPU) и на оставшееся место наплодили кучу вычислительных ядер и продвинутую систему обмена сообщениями — эффективность их использования будет очень низкой, потому что вместо того, чтобы работать асинхронно (положили данные в буфер и забыли) они будут блокировать друг друга и вы получите IO-bound систему на уровне архитектуры процессора.
И вообще, что такое буфер?
Если я пишу x = x + 1, то я уже буферизую.
Я уже не говорю о том что каждая задача требует разного количества времени (вычисления и обмен данными), предсказать это время невозможно и в итоге именно неравенство и некратность этих времён в разных частях системы создаст жуткую фрагментацию, наподобие той, от которой страдал Python до версии 3.2.4 при многопоточном программировании. Если вы отказываетесь от буферизации, то скорость работы всей цепочки задач будет равна скорости работы самого медленного звена + накладные расходы, а процессор большую часть времени будет простаивать.
Вы возложите эту задачу на суперскалярную архитектуру? На компилятор? В таком случае программирование превратится в что-то типа разработки на HDL, а сложность компиляции возрастёт в разы, превратившись в подобие той же разводки прошивки для ПЛИС. И к тому же это не поможет — внешний мир, реальный мир, асинхронен по своей природе. Даже свет распространяется с конечной скоростью а весь путь распространения световой волны и есть большой буфер.
Пункт 11. «всегда можно точно вычислить необходимое количество памяти для процесса. Необходимое количество времени счёта можно точно вычислить на основе анализа алгоритма.». А как же ветвление? Время выполнения в этом случае невозможно предсказать. Особенно если ваша программа взаимодействует с внешним миром (сеть, накопители). А если она всё время считает одно и то же, то её нужно запустить один раз, записать результат и положить на полку.
Я уже не говорю о всяких вещах типа проблемы остановки.Alexeyslav
19.11.2018 15:03Кеш у процессора это ни стек ни очередь, он служит лишь для отображения реальных участков внешней памяти. С точки зрения программы выполняющейся на процессоре не существует никакого процессорного кеша — он полностью прозрачен для программы(за редким исключением в виде неизбежных дыр в абстракциях). Возможно, в статье имеется в виду что очередь и стек не нужны процессору как таковому чтобы эффективно выполнять программы.
В статье упоминается что был выполнен такой процессор в виде модели, но нет никаких примеров его работы с конкретными задачами. Хотябы тестовыми и в сравнении с нынешними процессорами.evocatus
19.11.2018 15:12Вы описываете идеальный кэш, который так никогда и не был сделан и вряд ли когда-нибудь будет. Реальный кэш реальных процессоров это именно стэк (который управляется самим процессором и подгружает часто не то, что нужно) и это его главный минус. Попробуйте просмотреть двумерный массив по строкам, а затем по столбцам и расскажите мне как он отображает реальные участки внешней памяти. Отображать отображает, только вот скорость отличается слишком сильно. (В некоторых современных компиляторах даже дошли до того, что меняют проход массива по столбцам на проход по строкам автоматически). Я тоже не большой сторонник той модели, в которой сейчас все действуют — всё усложнять и усложнять процессоры. Мне тоже симпатизирует подход с умным компилятором (только это должен быть не компилятор C, а LLVM, JVM, CLR или другая виртуальная машина, чтобы написав несложный компилятор целевого языка в байт-код мы могли бы его выполнять — подход, реализованный ещё Никлаусом Виртом в Pascal с его P-кодами). Мне тоже симпатизируют суперскалярные архитектуры.
Но то, что описано в статье, мягко говоря, вызывает скепсис.Alexeyslav
19.11.2018 16:46-1Программу скорость выборок из памяти не волнует вообще, это нам, программистам важно чтобы всё работало как можно быстро. Пока двумерный массив имеет размер меньше размера кеша процессора особых проблем со скоростью не будет, а когда одна строка будет больше размера кеша тогда кеширование на уровне процессора будет практически бесполезным при последовательном чтении массива по столбцам.
Возможно, то что описано в статье пока её слишком теоретическое и нуждается в доработке чтобы сравнится с современными процессорами с их многочисленными костылями-ухищрениями чтобы добиться высокой скорости, но и с неизбежными дырами в абстракциях позволяющих работать таким уязвимостям как spectre и meltdown.Sap_ru
19.11.2018 18:25+1Нет. Вы можете успешно использовать кэш только потому, что он выполняет упреждающую выборку (а там очередь на очереди). На всех стадиях и во все времена. Даже самые первые процессоры имели блоки работающие параллельно.
По вашей логике никакая программа, размером больше кэша не может получить преимущество от его наличия. Что мягко говоря и очевидно и не так. Кэш успешно работает на данных практически любого размера именно потому, что там параллельная обработка везде, связанная очередями. Что приближает средний темп обработки данных к максимальному. Пока процессор обрабатывает данные, кэш уже наполняет буфера следующей порцией, а шина одновременно (пульзуясь приоритетами) сбрасывает результаты предыдущей обработки в кэш и/или память. И даже в случае промахов это даёт значительный прирост производительности. И всё это крайне богомерзко, вредно и не имеет права на существование, если если верить автору поста.evocatus
19.11.2018 19:18Но было бы здорово, если бы предвыборщик был программируемый (в дополнение к автоматическому режиму).
Sap_ru
19.11.2018 22:34Есть команды для управления предвыборкой, но самое главное — нужно просто правильно писать и компилировать программы. Никакой магии в предвыборке нет и поведение её весьма предсказуемо. А общие принципы даже не зависят от конкретной модели процессора. Современные компиляторы вполне это используют — и прогрев кэша и даже команды управления предвыборкой.
Alexeyslav
19.11.2018 20:10Линейная программа — не сможет. И если данные обрабатываются в процессоре только один раз и размер массива больше размера кеша(он же на инструкции и данные раздельный) то эффективность кеширования стремится к нулю. Но в реальных программах так не бывает, многочисленные циклы, короткие процедурки очень хорошо кешируются и эффект от этого есть. Но и любой процессор можно задачами нагнуть так что кеш вынужден будет разделиться на все процессы и каждому достанется маленький кусочек, так что уже на большие линейные участки хватать не будет(когда наступит очередь выполнить код он уже будет вытеснен другими процессами) и тогда наступит коллапс, но ИМХО с современным размером кеша сложно придумать такую реальную нагрузку которая вызовет этот эффект, на чем всё и держится.
Например, простая программа подсчитывающая сколько ячеек в памяти имеет значение меньше 127 и компилятор естественно счетчик расположит в регистре. К каждой ячейке она обратится ровно один раз. Эффекта от кеширования в процессоре на этой задаче не будет, поможет только кэш L2 и контроллер памяти, который идти в память будет не побайтно а считывать сразу одну кеш-линию используя BURST-режим чтения из памяти. Начинаем обращаться к ячейкам памяти рандомно с разбросом больше одной кеш-линии то и эти технологии сдадутся, и будет даже чуть медленней из-за накладных расходов.mayorovp
19.11.2018 22:43На самом деле эффект от кеширования все равно будет: ведь кроме данных процессору нужен еще и исполняемый код. А он-то как раз на этой задаче в кеш влезет…
phantom-code
19.11.2018 14:35+2Самолеты наверно тоже относятся к плохим вещам. Если их загрузить выше грузоподъемности, они же не взлетят.
ledocool
19.11.2018 14:43+2Ну да. Веб-кодерку ни стек ни очередь не пригодятся. Интересно, а каково с программистов?
Escalibur Автор
19.11.2018 15:05-4Попробую ответить.
1. Разумеется, я ожидал, что мне тут накидают вистов в гору. Ибо очередь и стек — это святое. То, что их когда-то не было — все забыли.
2. Любимые деревья — цикл. Как я говорил, рекурсия должна раскладываться в цикл. Если она не раскладывается в цикл, то это плохой алгоритм. Соответственно, есть алгоритмы обхода, которые обходятся без рекурсии. Кстати, с учётом последних увлечений распараллеливанием, рекурсия и очереди становятся особенно токсичными.
3. По поводу проблем с отсутствием буферизации. Единственный приемлемый сценарий буферизации — это конкатенация или сплит сообщений. При этом, это не очередь, а именно буфер.
4. Но самое моё любимое — это клаустрофобия на тему, а что же мы будем делать, если у нас будет узкое место? Ну, для начала, у вас ВСЕГДА будет хотя бы одно узкое место. Это аксиома. А, во-вторых, нужно смотреть не на программно-аппаратный комплекс, а на ЗАДАЧУ. Вы пишете ПО и устанавливаете железо не для того, чтобы у вас не было боттлнеков или чтобы вам сделать красиво. Вы делаете задачу, решая ПРОБЛЕМЫ ЗАКАЗЧИКА. Дак вот ему тормоза при обработке или ещё того круче сброс данных в результате затыка в очереди точно не нужны. Он это вам НЕ ЗАКАЗАЫВАЛ. В результате вот таких вот религиозных верований мы и имеем сейчас ситуацию, когда на дико мощном железе идут тормоза хуже, чем на на старых компьютерых со старыми ОС.
5. Ну и насчёт ресурсов. Если вы поглядели на описание операционной системы, то там всегда есть возможность ДИНАМИЧЕСКИ распределить сеть вычислительных процессов по ВСЕМ ДОСТУПНЫМ вычислительным узлам. Так что проблем простоя НЕ СУЩЕСТВУЕТ. Потому что если унифицировать системы, то всегда можно будет динамически распределять нагрузку.
А, вообще, вместо агрессии, просто попробуйте представить себе как бы можно было бы написать софт БЕЗ очередей и стеков. Хотя бы в качестве упражнения.
И да, я писал программы. У меня есть опыт и в контроллерах и в высокоуровневом программировании. И на проектах поработал.
Тем не менее, признателен всем, кто ответил. Я внимательно изучу ваши аргументы и постараюсь подобрать, по мере возможности, контраргументы.Escalibur Автор
19.11.2018 15:25-8Заминусовали! ) Остаётся утешаться тем, что Эйнштейна тоже, поначалу, считали мягко скажем странноватым.
staticlab
19.11.2018 15:35+4Я выдвигаю теорему: любой стековый алгоритм может быть конвертирован в цикл, а те, которые не могут быть конвертированы — плохи.
А эту теорему кто будет доказывать? Эйнштейн?
gbg
19.11.2018 15:43+5Теорема сводится к задаче останова, поэтому и доказать ее не получится. При конвертации алгоритма нужно будет на основании его текста (не выполняя его) извлечь условие цикла, что фактически является переформулировкой задачи об останове.
0xd34df00d
19.11.2018 21:27-1Нет, теорема в том виде, в котором она сформулирована, не сводится к задаче останова. Если бы было написано, что любой стековый алгоритм может быть эффективно (в смысле вот как раз того decidability, о котором вы пишете) преобразован в цикл, то тогда да. Я же скорее читаю это как «для любого стекового алгоритма существует эквивалентный на циклах», а доказательство этого утверждения вполне может быть неконструктивным.
Akuma
19.11.2018 18:30Я наверное буду единственным, кто вас поддержит :) Правда, не полностью.
Мне кажется проблема статьи в том, что вы слишком уж отвергаете стек и очереди.
Я бы сказал по другому: и стек и очереди нужно использовать там, где им место. Сейчас их (и много другое) пихают куда угодно, пытаясь спрятаться за оправданиями типа «это долгая операция, тут нужна очередь».
Но по факту сейчас можно про что угодно так сказать.
Например, я делаю демоны на PHP. Извращение? Да, это БДСМ, но я «умею их готовить» и вот уже больше года ни единой проблемы с памятью или каких-то багов из-за «злостного» PHP.
Так и с очередями. Думаю очень многие, кто вас минусует использует их адекватно, отсюда и минусы.
KevlarBeaver
20.11.2018 01:51Остаётся утешаться тем, что Эйнштейна тоже, поначалу, считали мягко скажем странноватым.
А я гляжу, Вы манией величия не страдаете, а наслаждаетесь…
MasteR_GeliOS
19.11.2018 15:33+3Попробую ответить по пунктам.
1. Всех алгоритмов когда-то не было. Если есть удобный для многих задач алгоритм решения, то зачем от него отказываться?
2. Да, можно разложить в цикл. Но не надо упускать наглядность реализаций алгоритмов для обхода. Читаемость кода никто не отменял.
3. Разные прикладные применения могут потребовать разных стратегий обработки буффера. Будь то FILO (first in — last out) или FIFO (first in — first out) как пример.
4. С моей точки зрения затыки и тормоза в приложениях в большей степени возникают из-за поддрежания обратной совместимости и возмно несовершентва итеративного развития программного продукта в целом. Буфер лишь повышает отказоустойчивость в пассивном режиме.
5. Вы же сами пишете что разрабатывали для микроконтроллеров. Разве там не существует проблемы ограниченных ресурсов и отсутствия арбитра в виде ОС?Escalibur Автор
19.11.2018 15:52-35. В качестве чего-то похожего на ту ОС я могу привести QNX. Они попытались создать систему с микроядром и возможностью автоматического маршрутизирования и перераспределения процессов по сети узлов. Система может обойтись и без очередей, если очередь будет в 1 элемент, как я уже говорил.
4. Безусловно, обратная совместимость — это отдельная тема. Я совершенно с вами согласен. Буфер сам по себе, как накопитель, как я уже говорил имеет право на жизнь, как структура, которая формирует пакет данных. А вот с очередями и стеком, увы, постоянно какие-то трудности.
3. Стратегия FIFO — это и есть обработка поступающих событий в темпе их поступления.
2. Читаемость кода — это отдельный разговор. То, что мы до сих пор вынуждены писать ПО в императивном стиле, как-то не очень хорошо, по моему. Но это нужно отдельно обсуждать.
1. Я не предлагаю отказаться наобум. Я просто хотел привлечь внимание, что есть проблемные структуры, которые, как показала практика, служат источником весьма немалых проблем. И, я думаю, что стоит рассмотреть альтернативные подходы.
staticlab
19.11.2018 15:33+3Стек придуман в 1946 году Аланом Тьюрингом. Раньше он был как-то и не нужен, потому что компьютеров не было. Но стопки документов были и раньше.
Так как бороться с узким местом? Вы говорите, что нужно динамически распределять нагрузку по вычислительным узлам. Кто и как будет управлять этим распределением? Сейчас этим внезапно занимаются менеджеры очередей. Далее, что делать, если всех доступных узлом всё-таки не хватает? Заставлять заказчика допокупать новые? Предположим, ему нужно конвертировать видео. В среднем нагрузка не очень большая порядка одного видео в пару часов, и даже один небольшой сервер справится. Но периодически в очередь на обработку он может поставить 5-6. Зачем ему 5 серверов, потому что какой-то программист не умеет писать очереди?
Escalibur Автор
19.11.2018 15:58-3Тьюринг изобел стек для того, чтобы решить некие математические задачи. В математике вообще много чего наизбретали. Только используется далеко не все.
Про ОС. ОС не управляет очередями. Она управляет ресурсами. А как организованы структуры ОС — это второй вопрос. Кстати, насчёт очереди процессов, если вы её имели в виду, то это, скорее, список, а не очередь. Равно, как и список блоков памяти. Процессы, как и блоки в памяти имеют принципиально другую природу. Они условно статичны, в отличие от динамических данных, которые они обрабатывают и хранят.
Про видео. Представьте себе лучше облачный сервис типа, к примеру AWS. Как вы думаете, у них как там это всё организовано? Тенденция такова, что вычислительная среда уходит в облака. И это естественным образом как раз и реализует ту парадигму, которая мною описана. Единственно, что пока ещё облачные сервисы плоховато балансируют нагрузку, перемещая процессы. Приходится программистам с админами «закатывать солнце вручную».staticlab
19.11.2018 16:23+1Тенденция такова, что вычислительная среда уходит в облака. И это естественным образом как раз и реализует ту парадигму, которая мною описана.
Это каша из топора. Вы пытаетесь решить проблему очереди, просто утопив её в якобы бесконечном облаке. Во-первых, это дороже для заказчика. Во-вторых, это облако кто-то программирует, причём на стеках и очередях. В-третьих, вы пытаетесь решить не проблему заказчика, а свою. "Вы пишете ПО и устанавливаете железо не для того, чтобы у вас не было боттлнеков или чтобы вам сделать красиво. Вы делаете задачу, решая ПРОБЛЕМЫ ЗАКАЗЧИКА. Дак вот ему тормоза при обработке или ещё того круче сброс данных в результате затыка в очереди точно не нужны." И вот следуя вашим же словам очередной говнокодер скажет, что ему для решения проблемы заказчика нужен компьютер с 64 Гб памяти, он же не заказывал тормоза.
Alexeyslav
19.11.2018 16:56-1Точно так же как бороться с переполнением буфера. Или он у нас автоматически становится бесконечным? Переполнить буфер тоже не так уж сложно, и в этом случае ТОЖЕ придётся какие-то данные отбросить.
mayorovp
19.11.2018 16:59Если размер буфера рассчитан правильно — то он не переполнится. Если он рассчитан с ошибкой — ну да, придется что-то отбросить, тут уже ничего не поделать.
staticlab
19.11.2018 17:07+1То есть если сервер занят обработкой, то отклонять все остальные запросы, не помещая в очередь?
FGV
19.11.2018 15:28+2Теоретики забавные. То стек/очереди им не угодили, то двоичная арифметика.
- Разумеется, я ожидал, что мне тут накидают вистов в гору. Ибо очередь и стек — это святое. То, что их когда-то не было — все забыли.
Мну помню, кодил на таком чуде-юде, без стека, без плавающей точки. Вспоминаю как тихий ужас.
Escalibur Автор
19.11.2018 16:05-2Это у вас был тулчейн плохой. Вы можете использовать на верхнем уровне любые абстракции. Но на нижнем уровне железо и ОС должны оперировать другим набором объектов. А тулчейн должен преобразовывать высокоуровневые объекты в низкоуровневые.
gbg
19.11.2018 16:11Такому контроллеру часто эмулятор арифметики с плавающей точкой просто в память программ не влезет, так как ее там может быть и килобайт.
oam2oam
19.11.2018 15:30+5на самом деле статья с точки зрения теории вычислений утверждает, что любая задача может быть решена на машине Тьюринга с ограниченной (по длине) лентой — ну то есть в пределе с одной ячейкой… смело. но неверно. Но, как не странно, часть задач решается — только вот насколько это практично?
Escalibur Автор
19.11.2018 16:10-3Я не могу сказать, что я математик и силен в теории алгоритмов. Поэтому, был бы признателен за какие-то варианты альтернатив стековым машинам в тьюринговом стиле.
AlexTheLost
19.11.2018 15:35+1Хм… Не понял автора, очередь и стэк это структуры данных, и из заголовка и тезиса видится что об этом и идет речь. Но потом неожиданный переход на на элементы ОС которые основаны на этих структурах.
Очередь — это буфер
Нет буфер — это очередь.)
1) Программное обеспечение — сети взаимодействующих процессов.
2) Взаимодействие процессов осуществляется путём обмена сообщениями.Думаю что для реализации как минимум этих двух абстракций без структур: очередь и стек будет тяжело обойтись.
FIFO и LIFO это два фундамента.)
gbg
19.11.2018 15:38+3В ваших так называемых принципах есть две дыры размером с Титаник, на которые легко предъявить контрпример — это номер 3
Сеть взаимодействующих процессов организована следующим образом: источниками первичных сообщений в такой сети являются только события от внешнего мира, поставляемые оборудованием, конечными потребителями сообщений являются только устройства, которые производят действия во внешнем мире. То есть сеть начинается в реальном мире и заканчивается в нем.
Здесь проблема в том, что источником сообщения может быть программа, причем количество и частота продуцируемых ею сообщений может быть произвольной и наперед неизвестной. Например, программа, которая решает систему уравнений итерационно — в зависимости от системы, она может двигаться быстро и выдавать сообщения о прогрессе каждую секунду, а может ползти в час по проценту — как решать будем? Заложим уберкомпьютер на максимальную частоту? За чей счет банкет?
Номер 5
Сеть никогда не буферизирует сообщения. Программно-аппаратный комплекс должен быть организован так, чтобы успевать обрабатывать сообщения в темпе их поступления из внешнего мира.
Написал нам человек через буферизованную сеть пакетной передачи данных интернет. Если на каждый чих формировать сетевой пакет, некоторые виды коммуникаций станут просто нереальными, например — интернетик по спутнику — да, долго, да, пинг по секунде, но качать можно что угодно (если деньги есть). Если же зафлудить передатчик однобайтовыми пакетами (у нас IoT-сервис телеметрии на процессоре Автора раз в секунду шлет температуру воды в санузле) — будет аллес. Да и электричества никакого не хватит постоянно канал держать.
Так что все эти ужасные приоритеты, стеки, очереди — они не от хорошей жизни, а для того, чтобы натянуть теорию на реальность за минимальный прайс.
lain8dono
19.11.2018 15:41-3А что можно почитать на эту тему? Пишу в качестве toy-проекта протокол поверх UDP. Работает, но медленно. Надо как-то по другому обслуживать соединения. Сейчас там тупо хештаблица, но это выглядит как не самая хорошая идея.
Edit: ответ на #comment_19388792, мобильное приложение хабра работает контринтуитивно.
mkshma
19.11.2018 15:47+1Что должно случиться с системой, что она вдруг перестанет тормозить и начнет переваривать данные быстрее?
Ну представьте, что вы обрабатываете трафик. Интернет, мобильный — пофиг. Трафика нереально много в часы высокой нагрузки, в остальное время он проседает до удобоваримых значений. Да, это не «вдруг», но сохранять все это надо.
Дак вот, есть два вопроса:
1. А почему нельзя отбрасывать данные сразу, если мы знаем, что у нас на их обработку нет ресурсов? То есть почему нельзя сделать очередь из одного элемента?
2. Либо обратный вопрос. Почему мы питаем иллюзии и не снабжаем систему необходимым количеством ресурсов, чтобы обрабатывать данные в темпе поступления?
1. Потому что нам необходимо весь этот трафик обработать. И пока мы можем хранить все в оперативке и не дергать диск — надо хранить все в оперативке и не дергать диск.
2. Потому что большую часть времени ресурсы избыточны. Отставание в 5-10 минут в ЧВН не страшно, а все остальное время железо будет простаивать. Так зачем платить больше?
И это только один пример. В общем оторвитесь от своей предметной области и вы поймете, что применений вагон и маленькая тележка.Escalibur Автор
19.11.2018 16:33-1Спасибо за отзыв. Но хотел бы отметить, что я в связи тоже поработать успел )
Вот смотрите, как только в каком-то месте собирается толпа, там сразу начинает просаживаться сотовая связь. Сначала идет деградация, а потом всё просто отстегивается. Что и получаем: в результате никакие очереди нам не помогут, все просто заканчивается сбросом трафика.
Если же вы попытаетесь буферизировать трафик в очередях, то память-то у вас тоже не бесконечна. Это просто оттягивание неизбежного. Рано или поздно — переполнение и то, что я описал в статье.
То есть, по факту, у вас есть некая статистическая модель, которая построена исходя из баланса между качеством обслуживания и стоимостью. Вот и нужно так строить системы.
suharik
19.11.2018 16:21+1Автор, спасибо вам за вдохновение! Немедля сажусь писать новую статью в продолжение и для развития темы вашей. Начинается она так:
«Существуют два устройства, которые известны любому программисту и которые настолько считаются аксиомами, что никто не пытается даже проанализировать, а так ли они нужны, есть ли от них польза и не превышает ли вред от них эту самую пользу. Клавиатура и мышь»
.
Далее планирую разобрать ситуации, подтверждающие мои слова. Одним из аргументов будет наличие статьи что вы написали, используя мышь и клавиатуру.
VaalKIA
19.11.2018 17:03+1Э.., а как базы данных вписываются в эту парадигму: написал запрос — смени железо?!
michael_vostrikov
19.11.2018 17:18Как вы без стека будете хранить адреса возврата?
Допустим, программа выглядит так.
main() { init(); do_work(); cleanup(); } do_work() { log('start'); whie (!need_exit()) { do_step(); } log('stop'); } do_step() { log('step'); ... ... }
Как вы из do_step() вернетесь в do_work(), и потом в main()?
staticlab
19.11.2018 17:56В данном-то случае стек вызовов в принципе не нужен. Код линейный.
michael_vostrikov
19.11.2018 18:14Заинлайнить предлагаете? Я подразумевал, что функции обособленные и независимые. Что если часть из них в сторонней библиотеке? А в do_step() вызываются функции из третьей библиотеки, math например, не копипастить же тело sin() в каждый вызов.
geher
19.11.2018 18:13Легко. Достаточно передать адрес возврата через специально выделенный регистр, а в функции сохранить его в глобальной переменной из специально выделенных для каждой функции. Поскольку данная программа не предусматривает повторного вызова функции до возврата из нее (прощай, рекурсия), то вполне сработает.
michael_vostrikov
19.11.2018 18:22А если скажем не держать их разбросанными по памяти, а собрать в одном месте, и читать не абсолютный константный адрес, а относительный (всегда нулевой элемент с конца), то получим… стек)
geher
19.11.2018 18:22За стек не скажу. Разве только придется отказаться в процессоре от команды вызова функции (все делать только на переходах). Без рекурсии, конечно, прожить сложно, но можно.
А вот очередь попрошу не трогать.
Есть системы с предсказуемой изменяемой нагрузкой и совершенно не требующие обработки в реальном времени. В них есть периоды, когда нагрузка максимальна, и периоды, когда система простаивает. Логично не тратить деньги на высокопроизводительный простой, а накопить очередь при максимальной нагрузке и разобрать ее при отсутствии входных данных. Тогда можно позволить себе сэкономить, снизив производительность системы до уровня, когда в простое она успевает разгрести данные за период высокой нагрузки.
wladyspb
19.11.2018 19:17+1Самый яркий пример очереди у меня сейчас перед глазами. Даже два.
1) — ClickHouse не рекомендует делать инсерты чаще чем раз в секунду(желательно — реже), но спокойно относится к массовым вставкам N полей одним запросом. Особенности архитектуры. При этом, у меня на входе держится нагрузка в районе 500 рпс, в пике до 4к рпс. Что же мне делать? Я просто кладу на каждый запрос данные в очередь, и с некоторой периодичностью сбрасываю их в ClickHouse. Вы мне советуете, видимо, отправлять туда не более одного запроса каждую секунду, выбрасывая остальные 499 наборов данных. Очередь же зло)
2) Один из проектов, который создаёт нагрузку в сторону моего апи — тоже хранит данные в очереди. Просто потому, что он их сначала генерирует в большом количестве, а потом в N потоков шлёт в мою сторону. Видимо, там тоже нужно взять, и выбросить очередь, или даже вообще её не создавать, а генерировать не больше данных, чем можно отправить за один раз.
Обе очереди косвенно несут в себе финансовый поток, и выбрасывать данные из них — крайне плохая идея.
impwx
Расскажите пожалуйста, как обойти произвольное дерево в ширину без очереди и в глубину без стека?
MasteR_GeliOS
Поддерживаю. К тому же навешивание ярлыка на буфер как на ошибку проектирования весьма неоднозначно. Не редок класс задач, когда нам нужно гарантировать обработку запросов, а ресурс вычислительной мощности ограничен. Как в целом обходится с пиками нагрузок в таких условиях?
Alexeyslav
Мне кажется, что речь в статье идёт не про вычислительные системы широкого применения а именно вычислители работающие с постоянной нагрузкой. Иначе сразу же получается так что система должна обладать производительностью рассчитанной под максимальный темп поступления данных на вход, а такое бывает далеко не всегда и стоимость такой системы просто будет не оправдана, хотя в теории это конечно же лучшее решение. Но всякого рода вычислительные кластеры которые работают неделями над одной задачей — это именно тот вариант где и стек и очередь в основе вычислительной системы только будут мешать(если верить статье). Майнинг биткоинов, например.
KevlarBeaver
Боюсь, что автор сейчас скажет, что деревья тоже не нужны.
ledocool
Нужны. Вот вы зимой чем печку топить будете?
KennyGin
Насколько я понял, автор не против стеков вообще, он против стеков неограниченного размера. То проблема стеков в том, что они могут выжрать всю память (stack overflow), и мы понятия не имеем, сколько выделять, чтоб хватило.
С обходом дерьевев ситуация другая. Мы сразу знаем, сколько памяти понадобится под стек — не более, чем число вершин. Если дерево слишком большое, то обход даже не начинаем. Хотя, если мы не знаем про дерево вообще ничего, то такую оценку мы сделать не сможем.
impwx
Даже если мы знаем общее число нод в дереве, то максимальный размер стека или очереди, требуемый для его обхода, обычно сильно меньше общего числа узлов. Закладывать такой запас памяти расточительно, а определить его точно можно только обойдя дерево…