Comments 72
Анапасик, и тут ты.
Проджектайлы — снаряды, которые фигак-фигак и в продакшн!
(можно не исправлять — хорошая "описка по Фрейду")
А так спасибо за статью! Интересно, но маловато
я уже читал это недавно, как так? перепубликация?
Поскольку список является закольцованным,… всегда будете знать, когда дошли до конца.
Это блин как, одно следует из другого? Вообще этот пункт какая-то дичь.
В оригинале было "always know when you iterated to the end".
"Because the list is circular the 'end' is always the list itself which means you can add and remove while iterating and always know when you iterated to the end. "
Хз как у них это работает, вероятно надо смотреть имплементацию этого списка https://www.boost.org/doc/libs/1_67_0/doc/html/intrusive/list.html
я так понял, список - это ссылка на первый элемент. И когда при обходе ссылка на следующий элемент равна самому списку (=первому элементу), значит, все, конец.
Не понимаю как фразу "the 'end' is always the list itself" можно понять иначе чем то, что сам список является своим последним элементом (так называемый список с заголовком).
указатель на хвост/конец списка является списком. Если следующий хвост пустой - то мы закончили пробег. Ну то есть это происходит из свойств односвязного списка.
Указатель на список есть указатель на первый элемент. Ты идешь по связному списку и когда выясняешь что указатель на текущий элемент равен указателю на список, ты прошел круг.
Это закольцованный двусвязный список: последний элемент ссылается next’ом на самый первый, а первый - prev’ом на самый последний. Так же было сделано в первых Думах.
Объект "список" также как и все остальные объекты, имеет ссылку на следующий/предыдущий. Когда список пуст, этот объект ссылается на сам себя в обе стороны. Когда список не пуст, этот объект там лежит в качестве начала и конца.
Я так понял, список сам себя итерирует. И вот когда элемент в списке стал равен this — дошли до конца.
Я думаю, что начав обход из ноды А - придя в ноду А опять будет очевидно, что весь список обошли до конца.
Не очевидно, если мы произвольно вставляем/удаляем ноды во время обхода. Т.е. мы могли сначала удалить эту ноду А, а затем её вставить где-то в середине.
А что на счёт современных ECS с архитипами? Просто это на самом деле звучит, как некое подобие, но без сахара и с использованием двусвязанных списков без какой либо причины. Полагаю, многопоточность тоже требует некоторого ручного труда. По крайней мере нет возможности получить некоторую многопоточность в комплекте с ECS.
Про архетипы сложно что-то сказать, а многопоток для ECS для параллельных систем кажется вообще не проблема. А списки нужны для того чтобы быстро переносить энтити между системами и фильтровать объекты, которые сами находятся где-то в сплошном массиве в другом месте и не тратить время на ветвления, потому что предиктору процессора такое не очень нравится. Подход filter -> map -> filter -> map получается более производительным в таком случае.
Про архетипы сложно что-то сказать
Архетипы позволяют избавиться от цепочек filter-map. Это о том, чтоб НЕ хранить все компоненты сущностей в едином массиве. Для каждого сочетания компонентов своя хранилка. Профит в линейном доступе для части случаев. Улучшает производительность за счёт лучшего попадания в кеши процессора. Это помимо очевидного отсутствия необходимости итерировать по тем частям памяти, которые не содержат нужных компонентов.
а многопоток для ECS для параллельных систем кажется вообще не проблема
Не кажется. Две системы, которые не имеют зависимостей друг от друга, могут работать параллельно. Более того. Это делается автоматически при грамотно сделанном API. Плюс разумеется внутри системы итерирование тоже может быть параллельным.
Для каждого сочетания компонентов своя хранилка
Если речь про СОЧЕТАНИЯ компонентов, то звучит несколько подозрительно. В классической ECS каждый вид компонента хранится в отдельном массиве. Хотя возможно для случая, когда нужно делать поиск по компонентам (как Query у Bevy), то возможно это как раз про это.
Да, именно про сочетания. И bevy_ecs вполне неплохой пример такого (если смотреть на эргономику, то как минимум один из лучших). Как впрочем и ещё штук пять ECS на Rust (много их наклепали со времён specs). Хотя в bevy_ecs есть ещё хранение компонентов в HashMap (случай для редких компонентов).
В том же Unity их ECS как раз на архетипах.
Как Factorio умудряется работать без лагов с таким числом элементов на экране
А вот у меня обратный вопрос. Как Factorio умудряется тормозить на gt1030? В каком-нибудь старкрафте объектов на экране было ненамного меньше, так он на 80486 превосходно шёл.
Потому что тормозит большей частью не на отрисовке, а на симуляции мира. Это на карточку не особо перекинешь.
Ну не знаю, у меня "мир" был с гулькин нос, по крайней мере по сравнению с тем, что папашки на ютубе показывают. Процессор xeon x3470.
Проблема, впрочем, не уникальная. В Satisfactory у хоста в мультиплеере тоже к концу игры FPS проседает до <20. В X4 Foundations на станциях вообще не часто бывает больше 30 FPS… На 5950Х и 4090. Загрузка процессора при этом — 1%. То самое одно ядро.
Основные расчёты в факторио идут на процессоре и за пределами экрана, поэтому мощность видеокарты имеет малое значение. Да и единиц расчёта на порядки больше, чем в старкрафте.
что вы называете тормозами?
у меня конфиг 9100f+gt1030(ddr5)+16GB RAM - сейчас провел тест в базе с 20к логистических и 60к строительных роботов (2к и 13к сейчас активны), перерабатывается по 30к железа и меди в минуту. это для понимания размеров базы. настройки максимальные, экран 1080р. при этом игра выдает 140+ фпс.
возможно, на слабых ноутбуках со встроенными интеловскими видеокартами будут лаги в поздней стадии игры на огромных базах, но не на десктопах.
и да, игра больше зависит от процессора, ГПУ там почти не нужен, поэтому и 1030 отлично смотрится тут.
Так я нуб несчастный, сейчас посмотрел сохранение — роботов меньше трёх тысяч. Процессор xeon x3470. Соответственно, pci-e 2.0.
при этом игра выдает 140+ фпс.
У меня фпс больше 60 не поднимается. И когда тормозило, то опускалась либо цифра фпс, либо фпс и упс одновременно.
возможно, на слабых ноутбуках со встроенными интеловскими видеокартами
Вот у меня сейчас ровно такой (i3-1115G4), на нём не тормозит. Хотя я и не играю, быть может, ежели буду активно играть, то снова станет тормозить. Ну или попросту в новых обновлениях исправили.
Проверьте доступную память, не закончилась ли она. Если играете на винде, учитывайте не только занятую память, но и зарезервированную — несмотря на описание, винда не очень охотно избавляется от этих страниц.
Пока у меня было мало памяти, мне приходилось держать RAMMap -Et на хоткее во время игры в факторию.
ноутбук на старом 6200u, в 1080p на низких настройках графики (чтобы в ГПУ не упиралось все же), выдает 30фпс, что плюс-минус играбельно, учитывая стадию игры.
вы может играли много лет назад - тогда да, в игре было куда меньше оптимизировано и требовалось железо мощнее. ну и да, чем больше ОЗУ, тем лучше.
А я вот на свитче играл последний раз. Размер карты точный не помню, но ракеты запускались примерно за минуту (+ я сделал супер глупость шину на которой было вообще все, что производилось), но Нинтендо свитч свой собственный Nintendo store без лагов отобразить не может, а факторио бегало довольно бодро, в общем -- производительность впечатлила для того, что, по сути, является не самым производительным телефоном.
Эмм, вообще-то как раз в те времена можно было четко заметить разницу в скорости производительности, когда играешь один против 7 компов в начале игры и в середине, когда уже дошло до лимита юнитов у каждого противника.
А если играть по сети - так вообще тормоза.
У меня на Pentium J3710 всё хорошо работает, а у вас на нормальном железе проблемы, лол
(Играю узкие миры смерти в основном)
Текст статьи вообще не отвечает на вопрос заголовка. Не сказано почему конкретно ECS не подходит, ни что взамен используется.
Для отрисовки логика прогоняет видимую область экрана в несколько потоков, находя, что нужно отобразить, и собирая информацию, которая позже отправляется на GPU.
Как они это делают? используют квадтри или ещё какие оптимизации
Уменьшение работы с кусками оперативки, которые необходимо тыкать каждый тик.
Как они этого добились?
Про список вообще ничего не понятно, абсолютно бесполезная статья.
Читая последние дни Хабр, закрадывается ощущение, что статьи пишутся способом типа "ChatGPT, напиши статью для хабра на основе вот этой статьи"
+100500
Я вроде и клеточные автоматы много раз писал, и моды к крафт играм схожим с Factorio, и с компонентными системами работал.
А из статьи не понял почти ничего.
Где тут диз ставить статье?
У factorio много лет выходит их dev blog по пятницам и там они в деталях рассказывают какими усилиями и как они делают незамерзающую сетевую игру, как добились оптимизации по интерфейсу, как хитрят со спрайтами - на каждое разрешение - свои, как сделали production pipe line от серверов исходников к серверам сборки до тестирующих серверов (да-да, там есть внутриигровые тесты, например рай перфекционист-разработчика - смотреть какие дрова пришлось поломать чтобы наладить семафоры и маршрут путей поездов) и до серверов выгрузки (один на сайт, один в стим, и еще добавились для выгрузки для ps4 и др платформ).
Без описания всего этого - как именно они добились такой скорости в производительности - статья ни о чем!
Если речь про офф блог, то уже давно постов нет.
Потому что разработка игры завершена, она релизнулась
Я про то, что разборы обычно делаю недавних постов/статей/видео. В принципе, если что-то из старого ещё в нашем сегменте никто не публиковал, то можно и что-то из старого перевести ?
Диз можно статье поставить сразу под ней: там есть строка со стрелочками вниз и вверх. Чуть ниже плашка с автором, там можно проголосовать в карму, не перепутайте.
Но если у вас 5-10 переменных связаны со сменой позиции, то толку от ECS не будет
Почему? Берем связанные переменные и меняем их в System
ECS отлично подходит, когда нужно применить некоторое преобразование к набору данных независимо от каких-либо других переменных.
ECS предназначен для эффективной работы с множеством сущностей, причем они определяются наборами компонентов. Внутри самой системы это хорошо паралелится за счет однородности данных (все, что меняем берем вместе и спокойно меняем, а все остально еще проще обработать)
ИМХО, автор игры не справился с ECS или решил просто не использовать ее. Это превосходное, но сложное решение, которое стоит попробовать каждому игроделу
Двусторонние списки использовали еще в прошлом веке.
Я вот не понимаю какие проблемы с обработкой тысячи объектов в нормальной десктопной игре могут быть.
Точнее не понимаю почему в статье перформанс связывают именно с двухсторонним списком.
Я вот не понимаю какие проблемы с обработкой тысячи объектов в нормальной десктопной игре могут быть.
Тысяча конвееров это где то самое-самое начало игры.
Точнее не понимаю почему в статье перформанс связывают именно с двухсторонним списком.
В статье, даже вот в этом переводе, двухсторонний список связывают с пробуждением/засыпанием этих объектов за o(1) время и без аллокаций памяти. А само наличие пробуждения/засыпания объектов уже связывают с перфомансом.
Я к тому и говорю - двухсторонний список єто не какая-то киллерфича. Это тип данных, которому уже десятилетия.
Вот уже пробуждение/засыпание - другой вопрос. Но тысяча объектов - ну не знаю.
В древнем мморпг тысяча объектов за секунду обрабатывалась на 486
Мне все-таки кажется, что проблема перформанса связана не отработкой большого количества объектов, а с отрисовкой большого количества объектов. О чем я в статье не особо понял.
Я вот не понимаю какие проблемы с обработкой тысячи объектов
Надо обработать всю физику за время одного кадра, ведь надо новые координаты отобразить.
Если хотя бы в 60 кадров метиться, а все-все связанное с графикой происходит параллельно на соседнем ядре, то надо в 16мс все запихнуть. 4ггц — это 4 миллиарда тактов в секунду, или 64 миллиона тактов на кадр. Современные процессоры более одной операции за такт выполняют, но и операции занимают более одного такта. В среднем можно считать 1 такт = одна операция. 64 миллиона операций — это не так уж и много. Если где-то есть O(n^2) — то 8000 объектов уже их все съедят только по одной операции на пару.
Даже без квадратичных алгоритмов, у вас всего-то 10000 операций на каждый объект. Ясно, что какая-нибудь сборочная машина считается быстро, а вот на ленте могут быть тысячи объектов. Жуки должны рассчитывать путь по карте, и вообще AI — сложная штука. Инсертеру надо понять, есть ли свободное место в конце — это надо знать какая там лента, надо ее опрашивать. Семафоры должны уведомить всех соседей о статусе жд полотна.
Понятно, что можно распараллелить что-то, но тут возникают задержки на синхронизацию потоков, да и ускорение это даст в 2-4 раза максимум. Т.е. сможете вы не тысячи, а 20 тысяч объектов в 60фпс уложить. Не на порядки ускорение.
Инсёртер же смотрит наличие свободного места только рядом с собой, принцип близкодействия в действии!
Ну так это место — это какое-то место на ленте. Но ленту нельзя же хранить, как массив — она может разбиваться на куски, могут добавлятся новые клетки. А если ленту хранить как список, то перекладка объектов между ними не оптимизируется никак.
Да даже если там хеш-мапа, говорящая, что вот эта клетка — это вот та лента, то далеко не 1 операциия хеш посчитать да по коллизиям пройтись.
Так что не так элементарно просто взять "место рядом с собой".
"Тестирование показало, что итерация связанного списка не медленнее, чем итерация вектора указателей"
Итерация нет, но доступ к памяти за указателем увеличивает время работы, потому что ухудшает локальность памяти
Учитывая, что с моей 3070 Factorio работает в 60 ФПС, а Cyberpunk в 100 - я бы не сказал что она отлично работает. Да, это из-за лимита ФПС, но кого волнуют причины?
Учитывая, что большая часть нагрузки на CPU, а не GPU, комментарий выглядит слегка странным ?
Кому вообще нужны 100 ФПС в игре не на реакцию?
Ну, если монитор работает на 144 Гц, то почему бы и нет, например.
Бесполезная трата электроэнергии.
Потому что нет смысла поднимать FPS выше UPS. А второй показатель напрямую влияет на скорость игры, если поставить максимальный UPS в 144, то на 144 придётся играть всем.
А это невозможно, на мегабазах UPS запросто проседает до 30 (и это ещё нормальная скорость). Падение UPS с 60 до 30 — то замедление игры всего в два раза, но падение UPS с 144 до 30 — это капец.
Вот именно, я как раз это и имел ввиду. Из-за использования фиксированного UPS невозможно сделать больше 60 фпс (ну или кадры просто повторяться будут). Можно поднять его до 120, но что тогда делать мониторам 144 и 240 Гц? А почему бы лучше не сделать UPS динамическим? Понятно, сейчас уже ничего не исправить, но использование фиксированного кол-ва обновлений в секунду выглядит как-то странно. А вот в Factorio 2, уверен, это будет реализовано.
Тому же, кому 120 Гц в смартфонах. Всем. Никогда большая плавность не была лишней.
Как Factorio умудряется работать без лагов с таким числом элементов на экране