Грязный флаг (Dirty Flag)
Last updated
Last updated
Избегать ненужной работы откладывая ее до тех пор, пока не потребуется результат.
"Флаг" и "бит" в программировании почти синонимы: они оба значат наименьшую порцию данных, могущую быть всего в двух состояниях. Эти состяния можно называть "правда" и "ложь" или "установлен" и "снят". Я буду использовать их во взаимозаменяемом смысле. "Грязный бит (Dirty bit)" - это еще одно название данного шаблона, но я лично привык к менее похотливо звучащему названию.
Во многих играх есть нечто, называемое графом сцены (scene graph). Это большая структура данных, хранящая все объекты в мире. Движок рендеринга использует его для определения кого и где на экране отрисовывать.
В самом простом виде граф сцены представляет из себя просто плоский список объектов. У каждого объекта есть модель или какой-то графический примитив и трансформация. Трансформация описывает позицию объекта, поворот и масштаб в мире. Чтобы переместить или повернуть объект вы просто изменяете трансформацию.
Механизм того, как хранится трансформация выходит за рамки нашего рассмотрения. Короче говоря это матрица 4х4. Вы можете создать трансформацию, которая будет объединять две других - например перенос и потом поворот объекта с помощью перемножения двух матриц.
Как и почему это работает я оставляю вам на самостоятельное изучение.
Когда рендер отрисовывает объект, он берет модель объекта, применяет трансформацию и затем рендерит его в мире. Если у нас будет просто мешок с объектами, а не граф сцены, то все так просто работать и будет.
Однако большая часть графов сцены представляет собой иерархию. Объект в графе может иметь родительский объект, к которому он привязан. В этом случае трансформация является относительной по отношению к позиции объекта, а не абсолютной позицией в мире.
Представьте себе для примера игру про пиратский корабль в море. Наверху мачты находится воронье гнездо. В этом гнезде сидит пират. На плече у пирата попугай. Локальная трансформация корабля определяет его положение в море. Позиция гнезда задается относительно корабля и т.д.
Образчик программистского искусства!
Таким образом когда родительский объект перемещается, его дочерние объекты перемещаются вместе с ним автоматически. Если мы изменяем локальную позицию корабля, воронье гнездо, пират и попугай будут изменяться вместе с ней. Если бы мы каждый раз пересчитывали позицию вручную чтобы ничего не сползало - это было бы настоящей проблемой.
Хотя честно говоря когда вы находитесь в море, вам нужно вручную корректировать свою позицию чтобы никуда не сползти. Наверное нужно было подобрать пример получше.
Но на самом деле для того чтобы отрисовать на экране попугая, нам нужно знать его абсолютную позицию в мире. Я бы назвал это трансформацией локальной трансформации объекта относительно его родителя. Чтобы отрендерить объект нам нужна его мировая трансформация.
Расчет мировой трансформации объекта довольно незамысловат: вам просто нужно обойти цепочку его родительских объектов, начиная с корня и заканчивая самим объектом, и объединить все их трансформации. Другими словами мировая трансформация попугая будет следующей:
В простейшем случае, когда у объекта нет родителей, его локальная и мировая трансформации совпадают.
Нам понадобится мировая трансформация для каждого объекта в мире на каждом кадре, так что несмотря на то, что это всего лишь несколько умножений матриц для каждой модели, этот код является горячим и критичным в плане производительности. Хранить их в актуальном состоянии проблематично, потому что каждое смещение родительского объекта, рекурсивно влияет на трансформации всех его детей.
Проще всего вычислять трансформации на лету во время рендеринга. На каждом кадре мы рекурсивно обходим граф сцена начиная с вершины иерархии. Для каждого объекта мы вычисляем мировую трансформацию и отрисовываем его.
Но при этом тратится куча драгоценного процессорного времени! Ведь многие объекты в мире не двигаются на каждом кадре. Подумайте о статической геометрии, образующей уровень. Пересчитывать ее мировые трансформации на каждом кадре иначе как пустой тратой ресурсов и не назовешь.
Очевидный ответ - нужно кэшировать данные. В каждом объекте мы будем хранить локальную трансформацию и вычисленную мировую трансформацию. Во время рендеринга мы будем использовать готовую мировую трансформацию. Если объект никогда не движется, кэшированная трансформация всегда будет корректной и все будут счастливы.
А вот когда объект движется, проще всего будет сразу обновить его мировую трансформацию. Только не забудьте об иерархии. Когда объект движется, нам нужно будет пересчитывать рекурсивно трансформацию всех его дочерних объектов.
Представьте себе довольно плотный геймплей. На одном кадре, корабль попадает в океан, воронье гнездо раскачивается от ветра, пират из него свешивается, а попугай перескакивает ему на голову. У нас изменилось четыре локальных трансформации. Если мы будем пересчитывать мировую трансформацию каждый раз, когда локальная трансформация изменилась, то что получится?
По строкам со звездочкой вы можете заметить, что мы пересчитываем мировую трансформацию попугая четыре раза, хотя результат нам нужен всего один.
Мы изменили всего четыре объекта, но выполнили десять пересчетов мировых трансформаций. Результаты шести бесполезных пересчетов придется выкинуть, потому что наш рендер их использовать не будет. Мы пересчитали мировую трансформацию попугая четыре раза, а рендерим его всего один раз.
Проблема здесь в том что мировая трансформация зависит от нескольких локальных трансформаций. Так как мы делаем пересчет всех как только изменится хотя бы одна из них, у нас получилось что мы пересчитываем одну и ту же трансформацию столько раз за кадр, сколько локальных трансформаций от которых она зависит изменяется.
Мы можем решить эту проблему с помощью снижения связности между локальной трансформацией и обновлением мировой трансформации. Это позволит нам изменять кучу локальных трансформаций за раз и затем пересчитывать результирующую мировую трансформацию всего один раз, после того как произойдут все эти изменения и прямо перед рендерингом.
Интересно в какое количество архитектур ПО умышленно добавлено небольшое проскальзывание.
Чтобы этого добиться, мы добавим флаг в каждый объект графа. Когда локальная трансформация будет изменяться, мы его установим. И когда нам понадобится мировая трансформация объекта, мы его будем проверять. Если флаг установлен, мы рассчитываем мировую трансформацию и очищаем флаг. Флаг отвечает на вопрос "Мировая трансформация устарела?" По неустановленной причине традиционно эта "устарелость" называется "грязью". Следовательно у нас появился грязный флаг.
Если мы применим этот шаблон и переместим объекты из предыдущего примера, у нас получится вот что:
На что мы можем надеяться в лучшем случае, так это на то, что мировая трансформация каждого затрагиваемого объекта вычисляется только один раз. С помощью всего одного бита, шаблон добился следующего:
Он разбивает изменения на множество локальных трансформаций по цепочке наследования, по одному вычислению на объект.
Мы избавились от вычислений для объектов, которые не двигались.
И еще маленький бонус: если объект был удален перед рендерингом, мировая трансформация для него вычисляться не будет.
Набор первичных данных изменяется со временем. Набор вторичных данных вычисляется на основе первичных с помощью ресурсоемкого процесса. "Грязный" флаг отслеживает рассинхронизацию вторичных данных с первичными. Он устанавливается когда первичные данные изменяются. Если флаг установлен когда нам понадобились вторичные данные, они вычисляются и флаг снимается. В противном случае используются уже вычисленные вторичные данные.
По сравнению с другим шаблонами в этой книге, данный шаблон решает весьма специфическую проблему. Как и в случае с другим оптимизациями, эту стоит применять только когда у вас есть реальная проблема с производительностью, ради решения которой имеет смысл заплатить увеличением сложности кода.
Грязный флаг применяется к двум типам работ: вычислениям и синхронизации. В обеих случаях процесс перехода от первичных данных к вторичным требует либо времени, либо дополнительных затрат.
В нашем примере с графом сцены, процесс замедляется из-за количества математических вычислений. С другой стороны когда этот шаблон используется для синхронизации, чаще всего вторичные данные находятся где-то еще - либо на диске, либо в сети - и даже простая передача данных из A в B будет затратной.
Есть и еще несколько требований:
Первичные данные должны изменяться чаще, чем используются вторичные данные. Этот шаблон избегает обработки вторичных данных, если последующее изменение первичных данных может сделать их неактуальными до того как они будут использованы. Если вы обнаружите что вам требуется пересчет вторичных данных после каждого изменения первичных, этот шаблон вам не поможет.
Их сложно обновлять постепенно. Скажем наш пиратский корабль может перевозить определенный вес. Поэтому нам нужен общий вес всего, что в него нагружено. Мы можем использовать этот шаблон и грязный флаг для общего веса. Каждый раз, когда мы будем загружать или выгружать добычу, мы будем устанавливать флаг. А когда нам потребуется общий вес, мы будем его вычислять и снимать флаг.
Но возможно проще будет просто поддерживать текущий общий вес. Когда мы добавляем или удаляем вещь, мы добавляем или вычитаем ее вес из общего веса. Если мы можем "платить на ходу" таким образом и поддерживать вторичные данные в актуальном состоянии, такой вариант может работать лучше чем наш шаблон и пересчитывать вторичные данные целиком не потребуется.
Звучит так как будто грязный флаг мало где нужен, но иногда он все таки полезен. Если поискать в любой кодовой базе слово "dirty", наверняка отыщется несколько мест, где используется этот шаблон.
По моим наблюдениям, таким образом можно найти и множество комментариев с извинениями за "грязные" хаки.
Даже когда вы убедили себя, что этот шаблон вам подходит, есть несколько мелочей, способных доставить вам дискомфорт.
Этот шаблон откладывает выполнение медленной работы до тех пор пока потребуется ее результат, но когда он нужен, он зачастую нужен прямо сейчас. Но ведь мы и применяли этот шаблон только потому что наше вычисление слишком медленное!
Для нашего примера это не проблема, потому что мировые координаты все равно вычисляются достаточно быстро для вычисления в кадре, но вы легко можете представить себе случай, когда придется выполнить значительно больше вычислений и это отнимет слишком много времени. И если игра не начнет такую работу раньше чем результат уже нужно демонстрировать игроку, у нас может образоваться весьма неприятная пауза в игре.
Это напоминает различные стратегии работы сборщика мусора, автоматически управляющего памятью. Подсчет ссылок (Reference counting) освобождает память сразу после того как она становится больше не нужной, но при этом тратит процессорное время на обновление счетчика каждый раз когда ссылки на объект изменяются.
Простой сборщик мусора откладывает освобождение памяти до тех пор, пока она снова понадобится, но расплатой за это является страшная "пауза сборщика мусора", способная заморозить всю вашу игру до тех пор пока сборщик закончит обработку кучи.
Между ними двумя находятся более сложные системы, такие как система отложенного подсчета ссылок и инкрементный сборщик мусора, которые освобождают память реже чем чистый подсчет ссылок, но чаще, чем останавливающие весь мир сборщики.
Еще одной проблемой отложенного выполнения является тот факт, что если что-то пойдет не так, вы можете вообще не суметь выполнить работу. Это может быть еще более проблематично, когда вы используете этот шаблон для сохранения некоего состояния в более устойчивой форме.
Например, текстовый редактор знает о том что в вашем документе есть "несохраненные данные". Эта маленькая пулька или звездочка в заголовке программы и является наглядной визуализацией грязного флага. Первичные данные - это открытый в памяти документ, а вторичные данные - это файл на диске.
Многие программы не выполняют сохранение на диск до тех пор, пока документ не будет закрыт или произойдет выход из приложения. В большинстве случаев это нормально, но если вы случайно выдерните сетевой кабель из розетки, вы потеряете свой шедевр.
Редакторы, в которых реализовано фоновое авто-сохранение пытаются таким образом компенсировать этот недостаток. Частота авто сохранения - это точки в континууме, между которыми мы не будем терять слишком много своей работы, если произойдет сбой и не будем напрягать файловую систему постоянным сохранением.
Вам нужно быть уверенным, что вы устанавливаете грязный флаг при каждом изменении состояния
Так как вторичные данные вычисляются на основе первичных, это по сути обычный кэш. Когда у вас есть кэшированные данные, самое сложное в работе с ними - это следить за актуальностью кэша (cache invalidation), т.е. за тем чтобы кэшированные данные были синхронизированы с исходными данными. В данном шаблоне это означает установку грязного флага когда любая часть первичных данных изменяется.
Фил Карлтон когда-то сказал "Есть только две сложные вещи в компьютерных науках: актуальность кэша и придумывание имен".
Упустите что-то и у вас в программе появятся некорректные вторичные данные. А это означает разочарованных игроков и крайне сложно отлавливаемые баги. Когда вы используете этот шаблон, вам нужно особенно заботиться о коде, который модифицирует первичное состояние и устанавливает грязный флаг.
Одним из способов этого добиться является инкапсуляция изменений первичных данных за каким-либо интерфейсом. Если все что может изменить состояние будет проходить через специальный API, вы можете устанавливать грязный флаг в этом интерфейсе и быть уверенным что вы ничего не упустите.
Когда вам понадобятся вторичные данные и грязный флаг не установлен, используются предыдущие вычисленные данные. Это очевидно, но это не подразумевает то, что вам нужно хранить старые вторичные данные где-то в памяти, на случай если они вам позже понадобятся.
Если вы используете шаблон для синхронизации первичного состояния с каким-либо другим местом - это не слишком большая проблема. В этом случае вторичные данные обычно вообще не находятся в памяти.
Если вы не используете этот шаблон, вам придется пересчитывать вторичные данные на лету по мере необходимости и сразу от них избавляться. При этом вам не придется хранить их кэшированными в памяти за счет необходимости их вычисления каждый раз, когда они будут нужны.
Как и другие методы оптимизации этот шаблон жертвует памятью ради скорости. В обмен на необходимость хранить ранее рассчитанные данные, вам не нужно будет пересчитывать их если они не менялись. Такие расходы имеют смысл когда вычисления медленные, а памятью можно пренебречь. Если у вас больше свободного времени, чем памяти, будет лучше рассчитывать их по мере необходимости.
Алгоритмы компрессии занимаются прямо противоположными вещами: они оптимизируют занимаемое пространство за счет времени, необходимого для распаковки данных.
Предположим что мы ознакомились с удивительно длинным списком требований и увидели как шаблон выглядит в коде. Как я говорил раньше, настоящая математика матриц трансформации выходит за рамки рассмотрения этой книги, так что я инкапсулировал ее в класс, внутри которого как мы будем предполагать и находится вся реализация:
Единственная нужная нам операция здесь - это combine(), с помощью которой вы можете получить мировую трансформацию, которая объединяет локальную трансформацию и всю цепочку предков. Также здесь есть метод для получения "начальной" трансформации - обычно единичной матрицы, вообще не содержащей переноса, поворота и масштабирования.
Теперь напишем набросок класса для объекта графа сцены. Это самый минимум того что нам понадобится до применения шаблона.
Каждый узел имеет локальную трансформацию, описывающую его позицию относительно родителя. Он содержит сетку, представляющую графическую часть объекта (мы позволим mesh_ принимать значение NULL для обработки невидимых узлов, используемых для группировки своих потомков.) И, наконец, каждый узел имеет коллекцию дочерних узлов, которая может быть и пустой.
Таким образом "граф сцены" - это всего лишь единственный корневой GraphNode, чьи дети (и внуки и т.д.) представляют все объекты в мире:
Для того чтобы отрендерить граф сцены, все что нам нужно, так это обойти все дерево узлов, начиная с корневого и вызвать следующую функцию для сетки каждого узла вместе с правильной мировой трансформацией:
Мы не будем ее здесь реализовывать, но если бы решились, она выполняла бы всю магию, необходимую для отрисовки сетки в нужной координате в мире. Если мы сможем корректно и эффективно вызвать ее для каждого узла в графе сцены, мы будем счастливы.
Чтобы запачкать руки, давайте напишем простейший обход графа сцены для рендеринга, подсчитывающий мировые координаты на лету. Он не будет оптимальным, но по крайней мере будет простым. Добавим в GraphNode новый метод:
Мы передаем сюда с помощью parentWorld трансформацию родителя узла. Таким образом все что нам остается для вычисления правильной мировой трансформации данного узла - это объединить ее с локальной трансформацией. Нам не нужно выполнять обход вверх по цепочке родителей для подсчета мировых трансформаций, потому что они уже будут вычислены по мере того как мы спускаемся вниз по цепочке.
Мы вычисляем мировую трансформацию узла и сохраняем ее в world, а затем рендерим сетку если она есть. И наконец, мы рекурсивно обходим дочерние узлы, передавая внутрь мировую трансформацию данного узла. В конце концов это простой рекурсивный метод.
Для отрисовки всего графа сцены, мы запускаем процесс начиная с корневого узла:
Итак данный код работает правильно - рендерит все сетки в нужных местах - но не слишком эффективно. Он вызывает local_.combine(parentWorld) для каждого узла в графе на каждом кадре. Давайте посмотрим как с этим сможет справиться шаблон. Для начала нам нужно добавить в GraphNode два поля:
Поле world_ кэширует ранее вычисленную мировую трансформацию, а dirty_ - это естественно грязный флаг. Обратите внимание что вначале он равен true. Когда мы создаем новый узел, у нас еще нет рассчитанной мировой трансформации и поэтому она еще не синхронизирована с локальной трансформацией.
Единственная причина, почему нам вообще нужен этот шаблон - это способность объектов двигаться, так что добавим соответствующую поддержку:
Главное здесь то что здесь снова устанавливается грязный флаг. Мы ничего не забыли? Ах да! Дочерние узлы!
Когда родительский узел двигается, мировые координаты всех дочерних становятся недействительными. Но здесь мы не будем устанавливать их грязный флаг. Мы могли бы это сделать, но такая рекурсия будет слишком медленной. Вместо этого мы поступим умнее, когда доберемся до рендера. Итак:
Здесь используется допущение что если проверка
ifработает быстрее чем умножение матриц. Интуитивно вам может таки показаться. Ведь логично что проверка одного бита быстрее чем куча операций с вещественными числами.Однако современные процессоры очень сложные штуки. Они нацелены на конвейерную обработку (pipelining ) - очереди из серии последовательных инструкций. Ветвление типа нашего
ifможет привести к ошибке предсказаний перехода (branch misprediction) и заставить процессор потерять циклы на повторное заполнение конвейера.Глава Локальность данных (Data Locality) рассказывает о том, как вы можете помочь современным процессорам работать быстрее и не попадать в такие неприятные ситуации.
Очень похоже на оригинальную наивную реализацию. Основное отличие заключается в том что мы проверяем грязность узла перед расчетом мировой трансформации и сохраняем результат в поле, а не в локальной переменной. Когда узел становится чистым, мы полностью пропускаем combine() и используем старое, но корректное значение world_.
Хитрость заключается в параметре dirty. Он будет равен true, если любой узел выше этого узла в цепочке иерархии был грязным. Примерно также, как parentWorld инкрементно обновляет мировую трансформацию во время спуска по иерархии, dirty отслеживает грязность дочерней цепочки.
Обратите внимание что этот трюк работает только благодаря тому что
render()- это единственная вещь вGraphNode, которой нужно обновлять мировую трансформацию. Если бы эта информация была бы нужна кому-то еще, нам пришлось бы выдумывать что-то другое.
Это позволяет нам избежать рекурсивной установки флага dirty_ для каждого ребенка в setTransform(). Вместо этого мы просто передаем родительский грязный флаг вниз его детям во время рендеринга и смотрим, нужно ли пересчитывать их мировую трансформацию.
В результате получается как раз то что мы и хотели - изменение локальной трансформации узла требует всего нескольких назначений, а рендеринг мира требует минимального количества вычислений мировых трансформаций, изменившихся со времени последнего кадра.
Этот шаблон довольно специфичен, так что настраивать здесь можно всего несколько вещей.
Когда нам потребуется результат:
Если результат нам не понадобится, вычисления вообще не будут выполняться. Для первичных данных, которые изменяются значительно чаще, чем выполняется доступ к вторичным, это даст заметный выигрыш.
Если вычисления требуют много времени, это может привести к возникновению заметной паузы. Откладывание работы на потом до тех пор пока игрок должен будет увидеть результат может испортить впечатление от игры. Обычно, если работа не занимает слишком много времени это незаметно, но в противном случае ее нужно выполнять все-таки раньше.
В жестко определенных контрольных точках:
Иногда в работе игры возникают моменты, где процесс выполнения отложенных вычислений смотрится органично. Например, мы можем захотеть выполнять сохранение когда наш пират заходит в порт. Или же точка синхронизации вообще может не быть частью игровой механики. Мы можем захотеть скрыть работу за загрузочным экраном или катсценой.
Выполнение работы не влияет на впечатление игрока от игрового процесса. В отличие от предыдущего варианта, у вас обычно есть чем отвлечь игрока, пока выполняется нужная вам обработка.
Когда возникает необходимость выполнить работу вы теряете управление. Это своего рода противоположность предыдущего пункта. Вы можете на микро-уровне управлять тем, когда выполнится работа и вы можете быть уверены что игра ее корректно выполнит.
А вот в чем вы не можете быть уверены - так это в том что игрок действительно доберется до контрольной точки или выполнит определенный вами критерий. Если он заблудится или игра поведет себя некорректно, работа отложится на более долгое время чем вы рассчитывали.
В фоне:
Обычно при первом изменении запускается таймер и затем обрабатываются все изменения, произошедшие между следующим тиком таймера и предыдущим состоянием.
В терминах человеко-компьютерного взаимодействия специальная задержка между получением программой пользовательских данных и их обработкой называется гистерезисом.
Вы можете настраивать частоту выполняемой работы. Настраивая интервал таймера вы можете задавать нужную вам частоту или нерегулярность.
Вы можете выполнять больше лишней работы. Если за время работы таймера первичное состояние изменилось незначительно, вы можете столкнуться с тем что будете обрабатывать большой объем почти неизменившихся данных.
Вам нужна поддержка для выполнения работы асинхронно. Обработка данных "в фоне" подразумевает, что игрок в то же время может продолжать делать что ему хочется. Это значит что вам придется воспользоваться потоками или другим методом поддержки конкурентной работы чтобы игра могла работать с вашими данными прямо во время своей работы.
Так как игрок может взаимодействовать с тем же первичным состоянием, которое вы обрабатываете, вам нужно позаботиться о том чтобы сделать его более безопасным в плане конкурентного изменения.
Допустим ваша игра про пиратов позволяет строить и модифицировать пиратский корабль. Корабли автоматически сохраняются в сети чтобы игроки могли потом продолжить с того места, на котором прервались. Мы используем грязный флаг для определения какая палуба у нас настроена и нуждается в отправке на сервер. Каждая порция данных, отсылаемая на сервер содержит часть модифицированных данных корабля и частичку метаданных, описывающих где на корабле произошло это изменение.
Если оно сильно детализированное:
Предположим что у вас есть грязный флаг для каждой отдельной доски на каждой палубе.
Вы будете обрабатывать только изменившиеся данные. Вы будете отсылать на сервер только ту часть состояния корабля, которая изменилась.
Менее детализированное:
В качестве альтернативного решения вы можете ассоциировать отдельный грязный флаг с каждой палубой. Изменение чего либо на палубе, делает грязной всю палубу.
Я хотел вставить сюда какую-нибудь шутку про швабру и мойку, но воздержусь.
Вы будете вынуждены обрабатывать неизменившиеся данные. Добавьте на палубу всего одну бочку и придется отправлять на сервер данные о содержимом всей палубы.
На хранение грязных флагов понадобится меньше памяти.
На постоянные накладные расходы получится тратить меньше времени. Когда мы обрабатываем некоторые измененные данные, для самой обработки этих данных чаще всего нужно выполнять какую-либо определенную работу. В нашем примере это метаданные, которые нужны для того, чтобы определить где на корабле были изменены данные. Чем больше обрабатываемый кусок данных, тем меньше этих метаданных и тем меньше накладные расходы на их обработку.
Этот шаблон очень часто можно встретить не в играх, а в браузерных фреймворках типа Angular. Они используют грязные флаги для отслеживания того какие данные были изменены в браузере и должны быть отправлены на сервер.
Физические движки следят как за движущимися объектами, так и за покоящимися. Так как покоящееся тело не двигается до тех пор, пока к нему не будет приложен импульс, их не нужно обрабатывать пока их кто-нибудь не тронет. Этот флаг "двигается ли" представляет из себя грязный флаг, обозначающий к каким объектам приложена сила и то что для них нужно применять физические вычисления.
