Вот пример решения: Запустить и посмотреть.
Те программы, которые достаточно быстро завершатся, выдадут решения, и являются нашим «частным случаем».
Тут просто проблема в том что такая утилита, которая работает лишь для тривиальных программ, имеет мало пользы (потому что тривиальные программы обычно тривиально и проанализировать)
Которая доказательно не имеет решения для тьюринг-полных языков.
Если язык не является тьюринг-полным (например, в нем нет рекурсии и любой цикл может выполняться только некоторое, известное до начала цикла, число раз) то тогда это возможно.
Примером таких языков являются некоторые (несовременные) языки шейдеров.
При счетчике ссылок «платится» за каждую передачу объекта (присваивание, передачу аргументом, и т.п.), тогда как при GC «платится» когда объект переживает сборку мусора (плата, правда, побольше, и зависит от того сколько внутри объекта указателей)
Объекты присваиваются и передаются аргументом намного чаще чем переживают GC.
Плюс, счетчик ссылок очень медленный в случае наличия больше чем одного потока.
Кыштымская авария это не авария на гражданской электростанции
Если под «серьезной аварией» подразумевать «у нас была электростанция, а теперь ее нет, и вместо нее что-то не предусмотренное проектом» то как раз эти три и получаются.
(Нужно обновлять комментарии перед отправкой)
В одноядерной системе нет понятия «неблокирующее многопоточное программирование»
Коллизии легко избегаются потому что есть специальная атомарная инструкция en.wikipedia.org/wiki/Compare-and-swap (я именно это имел в виду под «в cpu есть атомарные инструкции по работе с ними»)
Порядок действий если надо вставить элемент между a и b (a->b):
— Создаем новый элемент c (никто о нем не знает, так что синхронизироваться не нужно)
— Выставляем указатель c -> b
— если a все еще a->b то меняем указатель a->c (через compare-and-swap), иначе кто-то влез перед нами и надо что-то передумать или просто повторить
Есть одна область в которой односвязные списки критически необходимы — неблокирующая многопоточность
связный список это единственная структура данных динамического размера, операции с которой требуют изменение лишь одного указателя (т.е. и до и после изменения указателя структура в корректном состоянии), а в cpu есть атомарные инструкции по работе с ними
Если в задаче используется только сложение, вычитание и умножение — то да.
Но тогда можно просто использовать fixed-point, будет больше бит чем мантисса, и быстрее.
Лично мне кажется более интересным третий подход, когда тип (указатель на табличку с методами) хранится прямо в указателе.
Если мы говорим о языке, то где хранятся типы объектов не должно влиять на язык.
Если же мы говорим о деталях реализации, то у такого подхода есть проблемы. Во-первых, указателей на объект больше чем объектов. Во-вторых, указатели на объекты гораздо чаще перемещаются в памяти, а это означает всякие сопутствующие проблемы вроде того что передача указателей в функцию занимает больше регистров и меньше параметров можно передать через регистры и т.п.
Но самая концептуальная проблема в том, что такие указатели (являющиеся по сути структурами) становятся неатомарными в смысле многопоточного доступа. Что фактически ставит крест на «низкоуровневой» многопоточности.
(Или нужна система как упаковать 2 указателя в одно машинное слово, это в принципе можно сделать в 64 битной системе, но тогда это означает что указатель придется «распаковывать» при каждом доступе)
Если будет «приемник-передатчик на халявной энергии» то можно будет на его основе двигатели получше керосинки сделать т.к. закон сохранения энергии не соблюдается
А если будет соблюдаться то т.к. на Венере потенциальной энергии гравитационного поля Солнца меньше, то атмосфера потечет в обратном направлении (Марс->Венера) т.к. эта разница больше чем давление
Лично мне иногда не хватает чего-то типа mixin-ов — небольшого кусочка класса, с полями, методами, свойствами и указанием реализуемых интерфейсов, который можно «примешать» к любому классу (но только один раз)
На первом графике мало того что шкала начинается не от 0, так она еще и начинается в разных местах для двух линий (один колеблется на более чем 50%, второй менее чем на 10%)
Нарисовать нормально — и уже не так драматично выглядит.
Lockstep означает «У всех игроков есть полное игровое состояние и оно изменяется у всех одинаковым образом». Немного похоже на блокчейн.
Оно не означает что все игроки равноправны (Главное чтобы все знали кто из игроков «равнее»), не означает что нет центрального сервера (Эталонная симуляция, все кто с ней несогласны дисконнектятся)
У lockstep есть проблема принципиальной невозможности скрытия информации.
И есть плюс в виде что количество передаваемых по сети данных — это О(количество игроков), тогда как у несинхронных систем — О(количество объектов).
Если в игре количество игроков и объектов сравнимо (например шутеры) — в нем нет смысла. А если несравнимо — есть.
Еще lockstep позволяет бесплатно получить реплеи.
Starcraft 2 и warcraft 3 точно используют lockstep но без P2P.
Lockstep и P2P это не связанные понятия.
В статье говорится про lockstep но рассказываются минусы как lockstep так и P2P.
В «примерах» про Starcraft написано что Starcraft 2 не использует lockstep, но в пруф статье написано что Starcraft 2 не использует P2P и ничего не написано про Lockstep.
Игра «Heroes of the storm» основана на движке SC2 и использует Lockstep.
Вот пример решения: Запустить и посмотреть.
Те программы, которые достаточно быстро завершатся, выдадут решения, и являются нашим «частным случаем».
Тут просто проблема в том что такая утилита, которая работает лишь для тривиальных программ, имеет мало пользы (потому что тривиальные программы обычно тривиально и проанализировать)
ru.wikipedia.org/wiki/Проблема_остановки
Которая доказательно не имеет решения для тьюринг-полных языков.
Если язык не является тьюринг-полным (например, в нем нет рекурсии и любой цикл может выполняться только некоторое, известное до начала цикла, число раз) то тогда это возможно.
Примером таких языков являются некоторые (несовременные) языки шейдеров.
При счетчике ссылок «платится» за каждую передачу объекта (присваивание, передачу аргументом, и т.п.), тогда как при GC «платится» когда объект переживает сборку мусора (плата, правда, побольше, и зависит от того сколько внутри объекта указателей)
Объекты присваиваются и передаются аргументом намного чаще чем переживают GC.
Плюс, счетчик ссылок очень медленный в случае наличия больше чем одного потока.
Ассоциативность:
(1e-200*1e200)*1e200 => 1e+200
1e-200*(1e200*1e200) => Infinity
Дистрибутивность:
1e200*(1e200-1e200) => 0
(1e200*1e200)-(1e200*1e200) => NaN
Если под «серьезной аварией» подразумевать «у нас была электростанция, а теперь ее нет, и вместо нее что-то не предусмотренное проектом» то как раз эти три и получаются.
(Нужно обновлять комментарии перед отправкой)
Коллизии легко избегаются потому что есть специальная атомарная инструкция en.wikipedia.org/wiki/Compare-and-swap (я именно это имел в виду под «в cpu есть атомарные инструкции по работе с ними»)
Порядок действий если надо вставить элемент между a и b (a->b):
— Создаем новый элемент c (никто о нем не знает, так что синхронизироваться не нужно)
— Выставляем указатель c -> b
— если a все еще a->b то меняем указатель a->c (через compare-and-swap), иначе кто-то влез перед нами и надо что-то передумать или просто повторить
связный список это единственная структура данных динамического размера, операции с которой требуют изменение лишь одного указателя (т.е. и до и после изменения указателя структура в корректном состоянии), а в cpu есть атомарные инструкции по работе с ними
Но тогда можно просто использовать fixed-point, будет больше бит чем мантисса, и быстрее.
Если мы говорим о языке, то где хранятся типы объектов не должно влиять на язык.
Если же мы говорим о деталях реализации, то у такого подхода есть проблемы. Во-первых, указателей на объект больше чем объектов. Во-вторых, указатели на объекты гораздо чаще перемещаются в памяти, а это означает всякие сопутствующие проблемы вроде того что передача указателей в функцию занимает больше регистров и меньше параметров можно передать через регистры и т.п.
Но самая концептуальная проблема в том, что такие указатели (являющиеся по сути структурами) становятся неатомарными в смысле многопоточного доступа. Что фактически ставит крест на «низкоуровневой» многопоточности.
(Или нужна система как упаковать 2 указателя в одно машинное слово, это в принципе можно сделать в 64 битной системе, но тогда это означает что указатель придется «распаковывать» при каждом доступе)
А если будет соблюдаться то т.к. на Венере потенциальной энергии гравитационного поля Солнца меньше, то атмосфера потечет в обратном направлении (Марс->Венера) т.к. эта разница больше чем давление
А для человека (непрофессионала), который просто делает скан имеющейся у него книги альтернатива — PDF картинками или архив с jpg/tiff
Нарисовать нормально — и уже не так драматично выглядит.
Оно не означает что все игроки равноправны (Главное чтобы все знали кто из игроков «равнее»), не означает что нет центрального сервера (Эталонная симуляция, все кто с ней несогласны дисконнектятся)
У lockstep есть проблема принципиальной невозможности скрытия информации.
И есть плюс в виде что количество передаваемых по сети данных — это О(количество игроков), тогда как у несинхронных систем — О(количество объектов).
Если в игре количество игроков и объектов сравнимо (например шутеры) — в нем нет смысла. А если несравнимо — есть.
Еще lockstep позволяет бесплатно получить реплеи.
Starcraft 2 и warcraft 3 точно используют lockstep но без P2P.
В статье говорится про lockstep но рассказываются минусы как lockstep так и P2P.
В «примерах» про Starcraft написано что Starcraft 2 не использует lockstep, но в пруф статье написано что Starcraft 2 не использует P2P и ничего не написано про Lockstep.
Игра «Heroes of the storm» основана на движке SC2 и использует Lockstep.