Альтернативные аллокаторы памяти

Автор оригинала: Steven Tovey
  • Перевод
Написал Стивен Тови в 2:29 утра по программированию (шутка юмора Google Translate)
Вступление от себя: эта заметка, прорекламированная Алёной C++, предназначена в основном разработчикам игр для консолей, но будет, наверное, полезна и всем, кому приходится сталкиваться с экстремальным аллоцированием динамической памяти. Возможно, любители посравнивать управление памятью в C++ и Java тоже найдут над чем задуматься.

Оригинал с небезынтересной дискуссией в комментариях: altdevblogaday.org/2011/02/12/alternatives-to-malloc-and-new


Обязательная вступительная басня

Мне очень нравятся суши. Это вкусно и удобно. Мне нравится, что можно с бухты-барахты, не тратя целый обеденный час, зайти в суши-ресторан с конвейером, занять место и взять что-то свежее и вкусное с ленты. Но при всём при этом, чего мне реально не хотелось бы, так это быть официантом в суши-ресторане, особенно если бы моей обязанностью было бы рассаживать посетителей по местам.



image

Заходит компания их трёх человек и просит показать им места. Довольный приходом посетителей, ты любезно их усаживаешь. Не успевают они присесть и положить себе немного вкусных Текка Маки, как дверь снова открывается, и заходят ещё четверо! Тебе сегодня везёт, как утопленнику, парень! Ресторан теперь выглядит так…

image

Так как время обеденное, ресторан быстро заполняется до отказа. Наконец, поглотив всё что смогла, и оплатив счёт, первая компашка (те которых трое) уходит, а взамен заходит парочка и ты предлагаешь новым посетителям вновь освободившиеся места. Так случается несколько раз и наконец ресторан выглядит так…

image

И тут приходят четыре человека и просят усадить их. Прагматичный по натуре, ты тщательно отслеживал, сколько осталось свободных мест, и смотри, сегодня твой день, четыре места есть! Есть одно «но»: эти четверо жутко социальные и ходят сидеть рядом. Ты отчаянно оглядываешься, но хоть у тебя и есть четыре свободных места, усадить эту компанию рядом ты не можешь! Просить уже имеющихся посетителей подвинуться посреди обеда было бы грубовато, поэтому, к сожалению, у тебя нет другого выбора, кроме как дать новым от ворот поворот, и они, возможно, никогда не вернутся. Всё это ужасно печально. Если вы там гадаете, как эта басня относится к разработке игр, читайте дальше. В наших программах мы должны управлять памятью. Память — это драгоценный ресурс, которым нужно тщательно управлять, как и местами в нашем метафорическом суши-ресторане. Каждый раз, когда мы динамически выделяем память, мы резервируем место в штуке, называемой «кучей». В C и C++, обычно это делается, соответственно, при помощи функции malloc и оператора new. Продолжая нашу тухловатую аналогию (больше не буду, обещаю!) это похоже на то, как наши бесстрашные компашки едоков просят показать им их места. Но вот что по-настоящему фигово, так это то, что наш гипотетический сценарий случается и при работе с памятью, и последствия его гораздо хуже, чем пара пустых животиков. Это называется фрагментацией, и это кошмар!

Что же не так с malloc и new?

К сожалению, на этом рыбацкие басни заканчиваются и дальнейший текст будет о malloc и new, и о том, почему они имеют очень ограниченное применение в контексте встроенных систем (таких как игровые консоли). Несмотря на то, что фрагментация является лишь одним аспектом проблем, связанных с динамическим выделением памяти, она является, пожалуй, самым серьезным. Но прежде, чем мы придумаем альтернативные варианты, мы должны взглянуть на все проблемы:

  1. malloc и new пытаются быть всем в одном флаконе для всех программистов...
    Они выделят вам несколько байтов ровно тем же способом, что и несколько мегабайтов. Они не имеют понятия о том, что это за данные, место для которых они вам выделяют и какой у данных будет цикл жизни. Иными словами, у них нет той более широкой картины, которая есть у программистов.
  2. Относительно плохая производительность...
    Выделение памяти при помощи стандартных библиотечных функций или операторов обычно требует звонков в ядро. Это может оказывать на производительность вашего приложения всякого рода неприятные побочные воздействия, включая очистку буферов ассоциативной трансляции, копирование блоков памяти, и т.д. Уже этой причины достаточно для того, чтоб использование динамического распределения памяти стало очень дорогим с точки зрения производительности. Стоимость операций free или delete в некоторых схемах выделения памяти также может быть высокой, так как во многих случаях делается много дополнительной работы для того, чтобы попытаться улучшить состояние кучи перед последующими размещениями. «Дополнительная работа» является довольно расплывчатым термином, но она может означать объединение блоков памяти, а в некоторых случаях может означать проход всего списка областей памяти, выделенной вашему приложению! Это точно не то, на что вы хотели бы быть тратить драгоценные циклы процессора, если есть возможность этого избежать!
  3. Они являются причиной фрагментации кучи...
    Если вы никогда не работали над проектом, страдающим от проблем, связанных с фрагментацией, то считайте что вам очень повезло, но остальные-то мужики знают, что фрагментация кучи может быть полным и абсолютным кошмаром.
  4. Отслеживание динамически выделенной памяти может быть непростой задачей...
    Вместе с динамическим выделением в подарок приходит неизбежный риск утечки памяти. Я уверен, что мы все знаем, что такое утечки памяти, но если нет, то почитайте тут. Большинство студий строят инфраструктуру поверх своих динамических размещений, чтобы отслеживать, какая память и где используется.
  5. Плохая локальность ссылок...
    В сущности, нет никакого способа узнать, где та память, которую вернёт вам malloc или new, будет находиться по отношению к другим областям памяти в вашем приложении. Это может привести к тому, что у нас будет больше дорогостоящих промахов в кеше, чем нам нужно, и мы в концов будем танцевать в памяти как на углях. Так какая же есть альтернатива? Цель этой заметки — дать вам информацию (и чуток кода!) о нескольких различных альтернативах, которые можно использовать вместо malloc и new, дабы побороться с только что оглашёнными проблемами.


Скромный линейный аллокатор

Название этого раздела как бы намекает, что этот аллокатор, безусловно, самый простой из всех тех, которые я собираюсь представить, хотя по правде говоря, все они простые (и это делает их прекрасными). Линейный аллокатор, по существу, предполагает отсутствие мелочного освобождения выделенных ресурсов памяти и линейным способом выделяет куски памяти один за другим из фиксированного пула. Смотрите на картинку.

image

Хороший пример, где линейный аллокатор оказывается чрезвычайно полезным, можно найти практически везде при программировании синергетического процессора. Постоянность локальных данных за рамками текущей выполняемой задачи не важна, и во многих случаях количество данных, приходящих в локальное хранилище (по крайней мере данных, несколько варьирующихся в размерах) является достаточно ограниченным. Однако, не обманывайтесь, это далеко единственное его применение. Вот пример того, как можно было бы реализовать простой линейный аллокатор в С.

/** Header structure for linear buffer. */
typedef struct _LinearBuffer {


uint8_t *mem;       /*!< Pointer to buffer memory. */
uint32_t totalSize; /*!< Total size in bytes. */
uint32_t offset;    /*!< Offset. */
} LinearBuffer;

/* non-aligned allocation from linear buffer. */
void* linearBufferAlloc(LinearBuffer* buf, uint32_t size) {


if(!buf || !size)
return NULL;


uint32_t newOffset = buf->offset + size;
if(newOffset <= buf->totalSize) {
void* ptr = buf->mem + buf->offset;
buf->offset = newOffset;
return ptr;
}
return NULL; /* out of memory */
}


Применяя битовые операции к значению смещения во время выделения памяти можно поддержать выровненное аллоцирование. Оно может быть очень полезным, но знайте, что в зависимости от размера данных, которые вы размещаете в вашем буфере (а в некоторых случаях от порядка, в котором сделаны размещения), вы можете заполучить неиспользуемое пространство между выделенной памятью в буфере. Для выравниваний разумного размера это, как правило, приемлемо, но может стать чрезмерно расточительным, если вы выделяете память, с гораздо большим выравниванием, например по 1 Мб. В таких ситуациях порядок размещения объектов в линейном аллокаторе может оказать радикальное влияние на количество неиспользуемой памяти. Всё, что нужно сделать для сброса аллокатора (возможно, в конце уровня), это установить значение смещения в ноль. Как и всегда при работе с динамической памятью, клиенты аллокатора должны быть уверены в том, что у них нет указателей на память, которую вы таким способом деаллоцируете, иначе вы рискуете аллокатор сломать. У всех C++ объектов, которые вы разместили в буфере, нужно будет вручную вызвать деструктор.

Стек

Несколько оговорок прежде чем начать рассказывать об этом аллокаторе. Когда я говорю о «стековом аллокаторе» в данном конкретном случае, я не говорю о стеке вызовов, однако, как мы увидим позже, тот стек играет важную роль в избавлении от динамического выделения памяти из кучи. Так о чем тогда я говорю? Описанный выше линейный аллокатор является отличным решением для многих задач выделения памяти, но что, если вы хотите немного больше контроля над тем, как вы освобождаете свои ресурсы? Его вам даст стековый аллокатор. Ближе к концу описания линейного аллокатора я отметил, что для его сброса вы можете просто установить смещение в ноль, что освободит все ресурсы аллокатора. Принцип установки конкретного значения смещения является базовым, используемым в реализации стекового аллокатора. Если вы не знакомы с понятием стека, как структуры данных, то, вероятно, сейчас самое время, чтобы это сделать, например здесь. Сделали? Прекрасно. С каждым куском памяти, выделенным нашим стековым аллокатором будет опционально проассоциирован указатель на состояние стекового аллокатора непосредственно перед аллоцированием. Это означает, что если мы восстановим это состояние аллокатора (путем изменения его смещения) мы фактически 'освободим' память, которую можно будет повторно использовать. Это показано на диаграмме ниже.

image

Это может быть очень полезно, если вы хотите временно выделить память для данных с ограниченным временем жизни. Например, ограниченным временем жизни конкретной функции или подсистемы. Эта стратегия может быть также полезна для таких вещей как ресурсы уровня, у которых чётко определен порядок освобождения (обратный порядку размещения). Вот небольшой пример на C, иллюстрирующий только что сказанное

typedef uint32_t StackHandle;


void* stackBufferAlloc(StackBuffer* buf, uint32_t size, StackHandle* handle) {

if(!buf || !size)
return NULL;


const uint32_t currOffset = buf->offset;
if(currOffset + size <= buf->totalSize) {


uint8_t* ptr = buf->mem + currOffset;
buf->offset += size;

if(handle)
*handle = currOffset; /* set the handle to old offset */
return (void*)ptr;
}

return NULL;
}

void stackBufferSet(StackBuffer* buf, StackHandle handle) {

buf->offset = handle;
return;
}


Двусторонний стек

Если вы осилили описанную выше концепцию стека, то мы можем перейти к двустороннему стеку. Он похож на стековый аллокатор, за исключением того, что в нём два стека, из которых один растёт из нижней части буфера вверх, а другой растёт из верхней части буфера вниз. Смотрите картинку:

image

Где это можно использовать? Хорошим примером была бы любая ситуация, где у вас есть данные схожего типа, но с совершенно разным временем жизни, или если бы у вас были данные, которые были бы тесно связаны и должны быть размещены в одной и той же области памяти, но имеют разный размер. Следует отметить, что место, где встретятся смещения двух стеков, не фиксировано. В частности, стеки не должны обязательно занимать половину буфера каждый. Нижний стек может вырастать до очень больших размеров, а верхний быть меньше, и наоборот. Для того, чтоб использовать буфер памяти наилучшим образом, эта дополнительная гибкость может быть иногда необходима. Думаю, вы не нуждаетесь в советах Капитана О., и не буду приводить тут примеры кода для аллокатора с двусторонним стеком, так как он, естественно, похож на уже обсуждённый односторонний стековый аллокатор.

Пул

Мы сейчас немного сместим фокус с семьи описанных выше аллокаторов, основанных на линейных перемещениях указателей или смещений и перейдём к несколько иным вещам. Пуловый аллокатор, про который я сейчас буду рассказывать, предназначен для работы с данными одинакового типа или размера. Он делит подконтрольный ему буфер памяти на сегменты одинакового размера, а затем позволяет клиенту по его желанию выделять и освобождать эти куски (см. диаграмму ниже). Для этого он должен постоянно отслеживать свободные сегменты, и мне известны несколько способов реализации этого. Я лично избегаю реализаций, использующих стек индексов (или указателей) на свободные сегменты, из-за того что им нужно дополнительное место, что часто может быть непозволительно, но они вообще есть. Реализация, про которую я здесь расскажу, не требует дополнительного места для управления свободными сегментами в пуле. На самом деле, в служебной структуре данных этого аллокатора есть всего два поля, что делает его самым маленьким из всех аллокаторов, описанных в этой заметке.

image

Так как же это работает? Для управления свободными сегментами мы будем использовать структуру данных, известную как связанный список. Опять же, если вы с этой структурой данных не знакомы, то попробуйте прочитать это. Имея опыт с PlayStation3 и Xbox360, где доступ к памяти дорог я в общем считаю структуры данных, основанные на узлах (например, связанный список) довольно мрачными, но я думаю, что это, пожалуй, одно из тех их применений, которые я одобряю. По сути в служебной структуре аллокатора будет находиться указатель на связанный список. Сам же связанный список размазан по всему пулу, занимая то же пространство, что и свободные сегменты в буфере памяти. Когда мы инициализируем аллокатор, мы проходим через сегменты буфера и записываем в первых четырёх (или восьми) байтах каждого сегмента указатель с адресом следующего свободного сегмента. Заголовок же указывает на первый элемент в этом списке. Некоторым ограничением, накладываемым хранением указателей в свободных сегментах пула является то, что размер сегмента должен быть не меньше размера указателя на целевом железе. См. диаграмму ниже.

image

При выделении памяти из пула нужно просто передвинуть указатель на голову связанного списка в заголовке на второй элемент списка, а затем вернуть указатель на первый элемент. Это очень просто, при выделении памяти мы всегда возвращаем первый элемент в связанном списке. Аналогичным образом, когда мы освобождаем сегмент и возвращаем его в пул, мы просто вставляем его в голову связанного списка. Вставка освобождаемого сегмента в голову, а не в хвост, имеет несколько преимуществ: в первую очередь мы не должны проходить связанный список (или хранить дополнительный указатель на хвост в заголовке) и во-вторых (и это более важно), у узла, только что освобождённого, больше шансов остаться в кеше при последующих размещениях. После нескольких выделений и освобождений памяти ваш пул может стать похожим на такой:
image

Вот чуток кода на C для инициализации аллокатора и операций выделения и освобождения памяти.

/* allocate a chunk from the pool. */
void* poolAlloc(Pool* buf) {


if(!buf)
return NULL;


if(!buf->head)
return NULL; /* out of memory */


uint8_t* currPtr = buf->head;
buf->head = (*((uint8_t**)(buf->head)));
return currPtr;
}


/* return a chunk to the pool. */
void poolFree(Pool* buf, void* ptr) {


if(!buf || !ptr)
return;

*((uint8_t**)ptr) = buf->head;
buf->head = (uint8_t*)ptr;
return;
}


/* initialise the pool header structure, and set all chunks in the pool as empty. */
void poolInit(Pool* buf, uint8_t* mem, uint32_t size, uint32_t chunkSize) {

if(!buf || !mem || !size || !chunkSize)
return;


const uint32_t chunkCount = (size / chunkSize) - 1;
for(uint32_t chunkIndex=0; chunkIndex<chunkCount; ++chunkIndex) {

uint8_t* currChunk = mem + (chunkIndex * chunkSize);
*((uint8_t**)currChunk) = currChunk + chunkSize;
}


*((uint8_t**)&mem[chunkCount * chunkSize]) = NULL; /* terminating NULL */
buf->mem = buf->head = mem;
return;
}



Пара слов о стековых размещениях (alloca вам в помощь)

Если вы помните, ранее я сказал, что упомяну о стековых размещениях в контексте стека вызовов. Я уверен, что вы видели код, который концептуально выглядит примерно так:

myFunction() {

myTemporaryMemoryBuffer = malloc(myMemorySize);
/* обработка, не выходящая за пределы этой функции */
free (myTemporaryMemoryBuffer);
}


Большинство компиляторов C поддерживает функцию, которая должна означать (в зависимости от размера выделяемой памяти), что вам не придется прибегать к выделениям памяти в куче на временные буферы такого рода. Эта функция alloca. Внутреннее устройство alloca зависит от архитектуры, но по сути она выполняет выделение памяти путем настройки стекового кадра вашей функции, что позволяет вам записывать данные в область стека вызовов. Это может быть просто перемещение указателя стека (совсем как в линейном аллокаторе, упомянутом в начале). Память, выделенная вам функцией alloca, освобождается при выходе из функции. Есть, однако, несколько подводных камней, о которых надо знать при использовании alloca. Не забывайте проверять размер запрашиваемой памяти, чтоб быть уверенным в том, что вы не просите стек сумасшедшего размера. Если ваш стек переполнится, последствия будут неприятными. По этой же причине, если вы думаете над тем, чтоб выделить большой кусок памяти при помощи alloca, лучше знать все места, откуда ваша функция будет вызываться в контексте общего потока программы. Использование alloca может повлиять на переносимость в некоторых ограниченных случаях (очевидно), но я еще не сталкивался с компилятором, который бы её не поддерживал.

Дальнейшие подробности вы можете найти в вашем любимом поисковике.

И напоследок...

Часто память, выделяемая в ходе выполнения задачи является временной и сохраняется только на время жизни одного кадра. Для борьбы с неприятными последствиями фрагментации в системах с ограниченной памятью важно использовать эту информацию и размещать память такого рода в отдельных буферах. Сработает любая из вышеперечисленных схем аллоцирования, но я бы, наверное, предложил попробовать одну из линейных, так как их гораздо легче сбрасывать, чем пул. Noel Llopis рассказал больше подробностей на эту тему в этой отличной заметке. То, какой аллокатор лучше всего подходит именно вам, зависит от многих факторов, и от того, что требует та задача, которую вы пытаетесь решить. Я бы посоветовал тщательно подумать о шаблонах выделения и освобождения памяти, которые вы планируете делать в вашей системе, подумать о размерах и времени жизни выделяемой памяти и попытаться управлять ею аллокаторами, имеющими смысл в заданном контексте. Иногда помогает нарисовать распределение памяти на бумаге (да, карандашом и всё такое) или набросать график того, какую зависимость использования памяти от времени вы ожидаете. Хотите верите, хотите нет, но это действительно может помочь вам понять, как система производит и получает данные. Если вы это сделаете, то вам будет легче понять, как разделить выделения памяти так, чтоб сделать управление памятью настолько легким, быстрым и нефрагментированным, насколько возможно.

Учтите, что я рассказал тут о всего лишь небольшой подборке простейших стратегий, которые я, как правило, предпочитаю при программировании игр для консольных приставок. Надеюсь, что если вы дочитали аж до сюда и до сих пор такими вещами не занимались, то ваш мозг живёт теперь идеями о написанном в прошлом коде, который мог бы использовать эти методы для смягчения существенных недостатков, связанных с динамическим распределением памяти, или о других стратегиях, которые вы могли бы использовать для решения задач управления ограниченной памятью без динамического распределения.

Заканчивая, я считаю, что программисты должны учитывать последствия динамического выделения памяти, особенно в консольных играх и дважды обдумать использование функции malloc или оператора new. Легко убедить себя, что вы не делаете так уж много аллокаций, а значит большого значения это не имеет, но такой тип мышления распространяется лавиной по всей команде, и приводит к медленной мучительной смерти. Фрагментация и потери в производительности, связанные с использованием динамической памяти, не будучи пресечёнными в зародыше, могут иметь катастрофические трудноразрешаемые последствия в вашем дальнейшем цикле разработки. Проекты, где управление и распределение памяти не продумано надлежащим образом, часто страдают от случайных сбоев после длительной игровой сессии из-за нехватки памяти (которые, кстати, практически невозможно воспроизвести) и стоят сотни часов работы программистов, пытающихся освободить память и реорганизовать её выделение.

Помните: никогда не рано начать задумываться о памяти и когда бы вы ни начали это делать, вы будете жалеть о том что не сделали этого ещё раньше!

Дополнительная информация...

Вот несколько ссылок на схожие темы, или на темы, которые я не смог охватить:

gamesfromwithin.com/start-pre-allocating-and-stop-worrying
en.wikipedia.org/wiki/Circular_buffer
en.wikipedia.org/wiki/Buddy_memory_allocation
www.memorymanagement.org/articles/alloc.html

Спасибо Саре, Джеймин, Ричарду и Дат за вычитку этой бредятины.

Ещё от переводчика: я не разработчик игр, поэтому переводы специфических терминов могут быть не очень правильными. Например, я понятия не имею, что такое синергетический процессор :) Переводить игру английских слов тоже было непросто, но надеюсь, что получился не самый плохой вариант.
Поделиться публикацией

Похожие публикации

Комментарии 59

    +3
    SPU — Synergistic Processing Unit, это SIMD ядро процессора Cell. (В контексте статьи упоминается из за того, что имеет свою «бортовую» RAM)
    • НЛО прилетело и опубликовало эту надпись здесь
        +17
        Аллё? Ядро у аппарата.
          0
          И это не приколы translate.google.com :)
          В оригинале: "...typical require descending into the kernel to service the allocation requests..."
            +3
            вызовов ядра. Оригинала не вижу, но там были kernel calls :-)
              0
              Да, лучше было написать «требует системных вызовов» или перевести близко к тексту: «требует переходов на уровень ядра для обработки запросов выделения памяти».
                +2
                А по-моему, неплохо получилось. Этакий недо-сленг :-)
                  +2
                  Как многие, возможно, догадались, мне нравятся переводы, не засушенные книжным языком, особенно если оригинальный автор тоже использует неформальный стиль. Отсюда и «аллокатор», который ничем не хуже «менеджера» или «контроллера» и который наверняка все в разговоре предпочтут «механизму выделения динамической памяти» и «звонок» который является прямым заимствованием из лексикона сидящего за соседним столом коллеги и который мы широко используем в смысле 'kernel call' или 'RPC call'.
                  • НЛО прилетело и опубликовало эту надпись здесь
                  +1
                  аллоцированием? ну есть же хорошие русские слова… не?
                    0
                    Это какие? «Выделением»? Или может «распределением»? И название статьи будет «Альтернативные распределяторы памяти» :)
                      0
                      ну… «аллоцированием» я бы наверное заменил на «выделением», а «Альтернативные аллокаторы памяти» или оставил или применил бы «Альтернативные методы/способы/алгоритмы выделения/распределения памяти» в зависимости от ситуации…

                      и да, выделение и распределение памяти вполне себе благозвучные термины…
                        0
                        Вы наверняка заметили, что слово «аллоцирование» встречается в переводе всего 4 раза, а «выделение» и «размещение» — больше тридцати?
                          0
                          наверняка заметил :) но уж больно это четыре аллоцирования слух режут…
                          и да, за статью спасибо большое…
                        0
                        Менеджер памяти это называется. Тоже не слишком русское слово, но привычное по крайней мере
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            «выделение памяти» всю жизнь было. Менеджер памяти занимается выделением памяти.
                      +1
                      Прочитал до «аж до сюда». Спасибо за пост. Полез гуглить «оценка фрагментации памяти».
                        0
                        Хорошая статья.
                        Специфические аллокаторы полезны не только для разработчиков игр. Часто очень полезны в счетных алгоритмах с генерацией большого количества данных (типа поиска оптимальных решений). Например, можно просто быстро освободить все данные без деструкторов после вычисления, если они не нужны. Или быстро выделять много данных аллокатором типа пул, если все объекты одинаковые.
                          +1
                          по своему опыту могу порекомендовать использовать в пулах не связные списки, которые непонятно зачем там нужны, а маски. В одном int можно сохранить до 32 флагов «занятости» пула. Поиск места под размещения нужного количества блоков прост и удобен.
                          Также удобны каскадные пулы — когда создается пул с чанками по 4кб-4mb(а все равно кратно надо), часть которых хранит в себе пулы с чанками по Nбайт.

                          А всем кто на Cях, но все же не в теме — рекомендую просто поставить nedmalloc или мой любимый Winnie::alloc(ну и в этой ветке форума много чего еще написано)
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Спасибо за наводку (nedmalloc), я даже и не знал, что такое существует — пропатчить аллокатором уже существующие бинарники о_0 (цитата с сайта: nedmalloc can patch itself into existing binaries to replace the system allocator on Windows — for example, Microsoft Word on Windows XP is noticeably quicker for very large documents after the nedmalloc DLL has been injected into it!) Надо будет потестить.
                              0
                              Небольшая шибка перевода:
                              Часто память, выделяемая в ходе выполнения задачи является временной и сохраняется только на время жизни одного кадра. (В оригинале — lifetime of a single frame)

                              А вообще статья хорошая. Вот только предложенный «до кучи» двусторонний стек, кажется, ни для чего не нужен.
                                0
                                >> Вот только предложенный «до кучи» двусторонний стек, кажется, ни для чего не нужен.

                                Очень полезная штука. Часто на геймбое его использовал, для того чтобы совместить аллокации с разным временем жизни. сверху живут временные данные, а снизу добавляются более долгоживущие.
                                  0
                                  А чем в Вашем случае это было лучше двух стеков?
                                    0
                                    Под два стека нужно делать два буфера размером N. А тут место пересечения не фиксировано, и можно меньше памяти использовать, например, 1.5N
                                      0
                                      Ну это только в случае, если суммарный объём памяти мы можем предсказать лучше, чем отдельные слагаемые.
                                      0
                                      Экономия памяти + большая гибкость =)
                                      В конкретный момент, например, временные данные могут занимать много а долгоживущие — мало. В другое время — наоборот.
                                      Каждый стек — это некий фиксированный блок памяти, который нужно определить и следить чтобы всё влезало. Два стека нужно будет делать большими, что уменьшает смысл в динамическом выделении памяти.

                                        0
                                        Это ведь ситуация, когда мы наплодили толпу короткоживущих объектов, а потом их постепенно уничтожаем, создавая долгоживущие? Забавное решение, да.
                                    +1
                                    А в чём ошибка? Вы считаете что вместо «кадр» нужно было использовать слово «фрейм» ;)?
                                    Википедия о стековом кадре
                                      0
                                      Думаю, да.
                                      Словосочетание «стековый кадр» впервые вижу.
                                        0
                                        Звучит несколько противоречиво с озвученными в соседних тредиках пожеланиями видеть хорошие русские слова вместо заморских «аллоцирований», не?
                                          +1
                                          Возможно.
                                          Лично мне было бы более понятно «фрейм». И не коробило бы.
                                          Но не факт, что я типичный читатель :)
                                            0
                                            Реально, чтобы понять, что имелось в виду мне пришлось смотреть на оригинал. И я написал как и подумал — что там ошибка перевода.
                                      –1
                                      Для тех, кто пишет под Windows имеет смысл помнить о стандартных вещах, таких как:
                                      1) Low Fragmentation Heap — только для версий старших, чем Windows 2000 (с каким-то специфичным апдейтом)
                                      2) Small block heap — более старый вариант, по умолчанию отключенный начиная с Windows 2000, в компиляторе из VS2010 вообще выпилен, так что к использованию не рекомендуется.
                                        0
                                        LFH напомнила схему выделения памяти в memcached.
                                        0
                                        А вообще…

                                        1. Странно. Разве на SPU приходится гонять код, который память динамически выделяет? Зачем там это?

                                        2. Вроде же приставочные процессоры вполне себе поддерживают виртуальную память, так почему бы не использовать процессы для борьбы с дефрагментацией?

                                        3. malloc не обязательно часто делает syscall'ы. Он вполне способен организовывать пулы из запрошенных у ОС страниц.

                                        4. Где обещанное сравнение с Java?: )
                                          0
                                          Ничего не буду говорить про 1-3, а 4 никто не обещал. Обещалось что любители делать сравнения могут покормиться найти пищу для размышлений.
                                            0
                                            И 2) поясните может быть? Каким образом процессы помогут бороться с фрагментацией?
                                            0
                                            >> Странно. Разве на SPU приходится гонять код, который память динамически выделяет? Зачем там это?
                                            Не все задачи ограничиваются c[i] = a[i]+b[i]
                                            Иногда приходится гулять по движковым структурками, закачивая тоннами всякую мелочевку разного помола. И без стекового аллокатора тут нечего делать.
                                            Данные могут иметь разную структуру — фиксированными массивами не всегда можно отделаться.
                                            Да и просто память в пределах одного джоба может неаднократно переаллоцироваться.

                                            На памяти SPU может одновременно находиться (2-3 job-а) чтобы скрыть латентность обмена с памятью.
                                            Т.е. в пределах фрейма происходят тысячи best-fit аллокаций в любом случае в самой job-системе.

                                            >>Вроде же приставочные процессоры вполне себе поддерживают виртуальную память, так почему бы не использовать процессы для борьбы с дефрагментацией?
                                            Скорее разница в идеологии чем технические проблемы.
                                            Но виртуальная память не избавляет от фрагментации, хотя и смягчает её.
                                            Аллоцируем по N*(1кб + 2кб) блоков до упора (пока _некоммиченая память_ не закончится).
                                            Потом освобождаем все 1-килобайтные. Что дальше? Ни одного блока 3кб уже будет не выделить.

                                              0
                                              1. А можно конкретнее пример насчёт прогулок по движковым структурам — интересно.

                                              2. Про приставочные процессоры. Я имел в виду виртуальную память вместе с процессами. Если мы для какой-нибудь работы от-fork'али процесс, то он не будет своими служебными malloc/free вносить фрагментацию, скажем так, в корневое адресное пространство. Всё-равно же в приставках SMT-процессоры с выделенными под каждую нить TLB. Почему бы не воспользоваться?
                                                0
                                                А в приставках так дёшево создаются процессы? И есть какие-то гарантии насчёт того, когда он запустится?
                                                  0
                                                  Ну. Ничего не мешает создавать процессы очень дёшево. В Linux, например, они создаются очень быстро, не медленней, чем нити. Гарантии насчёт запуска тоже можно обеспечить — это не сложно. Но вопрос: а зачем? Игрушки неплохо себя чувствуют на стандартных планировщиках Windows/Linux.
                                                  +1
                                                  1) Движковый это было сказано к слову. Данные могут быть чьи угодно.
                                                  Например когда нужно выполнить обход по иерархической структуре, содержащей в своих узлах множество неких обьектов. Весь бардак написан на C++ и каждый обьект содержит всё в себе.
                                                  Прыгаем по спискам, где возможно асинхронно, но обычно синхронно — всё равно получается быстро. Где получается медленно — оптимизируем данные для группового доступа.

                                                  2) Эээ… тогда я не понял сути вопроса.
                                                  Я говорил про то что можно выделить виртуальное адресное пространство без коммита страниц и коммитить их по необходимости. Тогда можно освободившиеся страницы отдавать обратно в систему.

                                                  В приставках никаких форков нет и не будет =) Это бесполезный жир.
                                                  Процесс (если он вообще есть), владеющий всеми ресурсами консоли — один. Возможны бекграунд процессы обеспечивающие функциональность системы — фоновая закачка, музыка и т.п.
                                                  На консолях тонкие RTOS, которые позволяют быть уверенными что ни одного потеряного фрейма не будет. Разве что только по собственной лени и глупости.

                                                  >>Игрушки неплохо себя чувствуют на стандартных планировщиках Windows/Linux.
                                                  Ценой кучи затраченных ресурсов и отсутствия каких-либо гарантий по производительности и латентности. Работает на самом деле «абы как».

                                                    0
                                                    ЭЭэ… Почему бесполезный жир? Оба слова в сочетании не корректны. Во-первых, полезный, потому что упрощает управление ресурсами, используя TLB, как ускоритель для системы управления памятью, помогающим и давление дефрагментации снизить, и мусор собирать очень легко и просто. Во-вторых, не жир: накладные расходы на создание процесса не такие уж и большие.

                                                    Откуда у Вас информация про кучу затраченных ресурсов? Я тут недавно писал, так вот, тот же Dead Space 2 в Windows 7 у двухъядерного Athlon II X2 255 отъедает всего по 40 процентов процессорного времени на каждом из ядер. Fallout 2 забирает по 60. Игры, в общем-то, современные и сложные. То есть, там существует большой запас ещё на управление системными всякими вещами… Но и этот запас не нужен, потому что всё и так укладывается в 40-60%.

                                                    Кроме того, ну есть же исходники доступные игр (в том числе и таких, как Enemy Territory). И посмотреть на 'борьбу разработчиков с операционной системой' можно посмотреть самостоятельно. Ну нет там никакой такой героической войны, огромных усилий, грязных хаков и всего такого прочего. Всё вполне себе стандартно.
                                                      0
                                                      >>Во-первых, полезный, потому что упрощает управление ресурсами

                                                      2 процесса не могут упрощать управление ресурсами по сравнению с одним =)

                                                      >> используя TLB, как ускоритель для системы управления памятью, помогающим и давление дефрагментации снизить, и мусор собирать очень легко и просто.

                                                      Я всё ещё не понимаю как вы хотите бороться с фрагментацией с помощью процессов(!).
                                                      TLB эта такая штука, которую лучше на консолях не трогать — это вызов гипервизора + TLB miss очень дорог сам по себе.

                                                      >>Игры, в общем-то, современные и сложные.
                                                      С чего вы взяли что они должны упираться в CPU?
                                                      На консоли можно использовать CPU на 95% и не бояться, что кто-то встрянет на 1 мс и всё сломает.

                                                      >> Ну нет там никакой такой героической войны, огромных усилий, грязных хаков и всего такого прочего. Всё вполне себе стандартно
                                                      Я имел в виду процессорные ресурсы. При идентичном железе на консоли можно себе позволить гораздо больше. Бич PC — латентности. Везде длинные-длинные буферы чтобы бороться неравномерностью выполнения кода — на случай что кто-то вытеснит игру на значительное время. D3D буфферизирует на несколько кадров вперёд чтобы загрузить GPU.
                                                      Из-за этого обратный канал (всякие occlusion query и т.п.) мало полезен.
                                                      Звук тоже имеет высокую латентность ~40-50ms. На консоли я могу иметь латентность звука / управления в 16ms и меньше.
                                                      С рендером ещё более шоколадно — могу запустить DIP и сразу же получить его данные.
                                                      На PS3 можно рендерить на GPU/SPU. Некоторые вещи быстрее делать на SPU, чем на RSX — вертекс процессинг / блюры и т.д. — SPU подключается в нужный момент и выполняет свою часть работы. Всё работает чётко и без задержек. На PC такое в принципе невозможно.

                                                      >>А по поводу хождения по структурам на SPU — это сильно странно. Они же для другого предназначены.
                                                      Для чего? Это ядра общего назначения. Из-за SIMD ориентированности скалярный код выполняется медленней чем векторизированный, но это не значит что медленно.

                                                      >> Разве для проходов по всяким деревьям не предназначены CPU-ядра, которые к этому хорошо приспособлены: автоматические кэши, скалярные операции, всё такое?

                                                      SPU много. Если они могут делать работу быстрее чем PPU, зачем нужен PPU?
                                                      Можно заготовить данные

                                                        0
                                                        продолжаем… (могу постить только раз в час)
                                                        Можно заготовить часть данных на PPU, положить их в job (логически завершенный кусок кода, для которого определены входные и выходные данные) и отправить на SPU.
                                                        Если job-ов не много, можно не париться. А вот если обход по большой структуре (что уже само тормозит на PPU) и джобы придётся мелко-мелко нарезать (сотни тысяч во фрейм), то лучше и на порядок быстрее это сделать на SPU. Код по большей части останется тем же.
                                                        PPU запустит 1 или несколько job-ов, и всё — можно работать дальше.

                                                          0
                                                          2 процесса не могут упрощать управление ресурсами по сравнению с одним =)

                                                          Я всё ещё не понимаю как вы хотите бороться с фрагментацией с помощью процессов(!).
                                                          TLB эта такая штука, которую лучше на консолях не трогать — это вызов гипервизора + TLB miss очень дорог сам по себе.


                                                          Эмс… Почему не могут-то? Сценарий очень простой: вот надо нам выполнить некую работу, которая требует выделения динамической памяти. Запускаем её в отдельном процессе, который своей работой не вносит фрагментацию в важную для нас память, в которой мы будем ещё выделять место под важные, долгоживущие в вычислении объекты. Вроде как, чего в этом сложного и не понятного?

                                                          TLB miss не так уж и дорог, то есть, конечно, если преднамеренно и регулярно промахиваться, писать код с плохой локальностью, то будет, конечно, дорого. Но если всё написано аккуратно, чем, собственно, промах при работе процесса A будет отличаться от промаха при работе процесса B? Плюс в приставочных процессорах есть возможность разделять TLB между разными процессами: VSID — Virtual Space ID аж целых 37 битов в Cell — вполне достаточно.

                                                          SPU много. Если они могут делать работу быстрее чем PPU, зачем нужен PPU?
                                                          Можно заготовить данные


                                                          Может, как бы, за тем, что SPU хоть и много, но работу их согласовывать надо? А вообще, я вот лично совсем не представляю, как можно эффективно, скажем, поиск в глубину по графу организовать при помощи этих самых SPU. Не все же алгоритмы параллелятся хорошо. А последовательный код SPU не так хорошо выполняет — кэш нужно искусственно поддерживать, накладные расходы на это всё в виде лишних инструкций. Так что… Не понятны мне Ваши заявления.

                                                          Про большой кусок насчёт задержек: Но, ведь, люди как-то пишут для PC и вполне качественно выходит. Вот, наприме, а зачем вам управлять звуком точнее, чем 50ms? Даже если m значит тут микро, это всё-равно точность 1/20 секунды, человек этого не воспринимает… И все эти 16ms, или там ещё какие ms… Напоминают погоню некоторых фанатов за скоростью рендеринга в 200fps на мониторах, которые показывают только 60 кадров в секунду.
                                                            0
                                                            >> Сценарий очень простой: вот надо нам выполнить некую работу, которая требует выделения динамической памяти. Запускаем её в отдельном процессе, который своей работой не вносит фрагментацию в важную для нас память

                                                            Это полный привет с точки зрения производительности. «Работа» которая может выделять память в пределах фрейма, измеряется микросекундами.
                                                            Тут сама по себе аллокация памяти тормозит, а вы говорите запустить процесс, переворошить TLB, выделить память, передать данные, обработать данные, передать обратно.

                                                            Обьясните мне зачем вообще запускать какой-то процесс? Давайте ещё к формуле 1 цеплять башенный кран.
                                                            Гораздо проще работать в виртуальном адресном пространстве.

                                                            >>Может, как бы, за тем, что SPU хоть и много, но работу их согласовывать надо? А вообще, я вот лично совсем не представляю, как можно эффективно, скажем, поиск в глубину по графу организовать при помощи этих самых SPU
                                                            Тут суперэффективность и не нужна. Нужно чтобы всё вместе уложилось в отведённое время.

                                                            Так же как и на любом другом многоядерном процессоре.
                                                            Очевидно, имеются свои тараканы с доступом к памяти, но это решается врапперами.
                                                            Можно зацепить эмулятор кеша, можно ручками всё делать.

                                                            >> А последовательный код SPU не так хорошо выполняет —
                                                            С чего бы? В большинстве случаев любой код на SPU быстрее чем PPU.

                                                            >> кэш нужно искусственно поддерживать,
                                                            накладные расходы на это всё в виде лишних инструкций.

                                                            По сравнению с латентностью памяти, несколько инструкций вообще ничего не значат. Читать несколько раз одно и тоже — бессмысленно. Посему от кеша «а-ля CPU» толку мало.
                                                            Кешировать нужно не raw-данные, а например стек возврата по дереву и т.п.

                                                            >> Вот, наприме, а зачем вам управлять звуком точнее, чем 50ms? Даже если m значит тут микро, это всё-равно точность 1/20 секунды, человек этого не воспринимает

                                                            Также как и больше 24 кадров в секунду =)
                                                            Игры с войс чатом имеют неприятную задержку при прослушивании своего голоса.
                                                            Почитайте про ASIO и кому нужна маленькая латентность.

                                                            >>Напоминают погоню некоторых фанатов за скоростью рендеринга в 200fps на мониторах, которые показывают только 60 кадров в секунду.
                                                            Причём тут монитор? Всё дело в латентности управления. Например 30fps в Counter-strike это уже за гранью играбельности. К 100 fps там стремятся неспроста.
                                                              0
                                                              Это полный привет с точки зрения производительности. «Работа» которая может выделять память в пределах фрейма, измеряется микросекундами.
                                                              Тут сама по себе аллокация памяти тормозит, а вы говорите запустить процесс, переворошить TLB, выделить память, передать данные, обработать данные, передать обратно.


                                                              Так. Мы же говорим о проблеме фрагментации. Это, во-первых. Во-вторых, да нет там никакого привета с созданием процесса. fork, даже в Linux, где надо ещё заниматься всяким housekeeping'ом для оформления процесса занимает чуть более 2000 тактов (тактов — не микросекунд).

                                                              TLB ворошить совершенно не нужно при этом, нужно лишь создать новый VSID, и в нём размещать процесс. В архитектуре Power это всё замечательно предусмотрено. Плюс возможность использовать страницы размером 16MiB. А TLB в тех же Cell'ах держит 1024 вхождения (повторюсь) для разных процессов.

                                                              Я не знаю, как там насчёт качества операционной системы, но весь потенциал сделать быстрые процессы есть.

                                                              Выделение же памяти выделению — рознь. Если память дефрагментирована, то поиск нужного блока, может занять существенное время. А мы же обсуждаем проблему борьбы с ней.

                                                              По сравнению с латентностью памяти, несколько инструкций вообще ничего не значат. Читать несколько раз одно и тоже — бессмысленно. Посему от кеша «а-ля CPU» толку мало. Кешировать нужно не raw-данные, а например стек возврата по дереву и т.п.

                                                              Эмс… Странное рассуждение. Когда мы, например, обходим граф, то нам без чтения одного и того же просто не обойтись. Когда мы обходим дерево, то же самое. Наверное, это только самый ярый фанат избегания повторных чтений будет указатели на потомков размещать в разных линиях кэша.

                                                              Вообще, важная задача кэша в том виде, в котором он есть на CPU — это ещё и поддержка многозадачности. С программно управляемым кэшем ничего бы не вышло. Но в виде плюшки он даёт возможность, кроме прочего, сберегать объём кода, необходимый для всякого ручного кэширования. А это может быть и не такой уж тривиальный код. Не всегда можно обойтись стэком (алгоритмы на графовых структурах, ray casting, etc).

                                                              Причём тут монитор? Всё дело в латентности управления. Например 30fps в Counter-strike это уже за гранью играбельности. К 100 fps там стремятся неспроста

                                                              Хм. А как fps связаны с латентностью управления? Вот вы боретесь за все эти такты и микросекунды, а при этом в итоге говорите: ну, впустую нарендерить 40 кадров в секунду — это вполне нормально. Может быть, тут проблема просто в неадекватной структуре движка, у которого латентность управления, почему-то, привязана к fps?
                                                                0
                                                                >>Так. Мы же говорим о проблеме фрагментации.
                                                                Так вот а причем тут процессы?
                                                                Ну запустили вы процесс и что дальше? Что вы там собрались делать?
                                                                Мне нужно выделить память чтобы сделать «Hello» + «World».
                                                                Вы собираетесь процесс для этого выделять?
                                                                Проблему подобных случайных аллокаций решает dlmalloc и делает он это весьма быстро.

                                                                Создания второго процесса на консолях может и не быть вообще. Т.к. непонятно как быть с аппаратными ресурсами, некоторые из которые доступны напрямую.

                                                                Оригинальная статья рассказывает не об абстрактной фрагментации в вакууме, а об аллокациях в контексте игровых движков, где кроме отсутствия фрагментации нужна ещё и приличная скорость. Опять же на PC с фрагментацией особо не паряться, потому что есть своп — ну лагнёт фрейм, ну и ничего, там все привыкшие.

                                                                >> для оформления процесса занимает чуть более 2000 тактов
                                                                Т.е. вы хотите сказать, что выделение памяти через CRT будет медленнее чем
                                                                если выделить вирт. память в системе, построить новый pagetable создать процесс, запустить его на следующем таймслайсе, сделать тасксвитч, запустить CRT, почистить Bss, АЛЛОЦИРОВАТЬ ПАМЯТЬ ЧЕРЕЗ CRT и т.д.

                                                                И уж выделить память из пула, затратив дюжину инструкций в любом случае быстрее в совершенно недостижимое количество раз.

                                                                >> Когда мы, например, обходим граф, то нам без чтения одного и того же просто не обойтись.
                                                                И? Сделаю полно-ассоциативный кеш, на сколько_нужно кешстрок.

                                                                >> Наверное, это только самый ярый фанат избегания повторных чтений будет указатели на потомков размещать в разных линиях кэша.
                                                                Если эта структура интрузивна, то распределение поинтеров по кешстрокам будет довольно рыхлым, поэтому держать их в таком виде в кеше — бессмысленная трата памяти.

                                                                >>Вообще, важная задача кэша в том виде, в котором он есть на CPU — это ещё и поддержка многозадачности. С программно управляемым кэшем ничего бы не вышло.

                                                                А в чём проблема?
                                                                Кстати ни в одной игре я пока что ни разу не использовал программный кеш — просто не нужно было. Быстрее и проще загрузить нужные обьекты целиком.

                                                                >>Хм. А как fps связаны с латентностью управления?
                                                                Очень просто.

                                                                Человек нажимает кнопку. Опрос

                                                                  0
                                                                  1. Нет, конечно. Речь не идёт о том, чтобы на каждое hello + world было в отдельном процессе. Ибо тут накладные расходы будут на межпроцессное взаимодействие неприемлемыми. Но если надо, например, построить DAWG по словарю, процесс чего потребует многих аллокаций, перед тем как выдать линейную табличку, то почему нет?

                                                                  Хотя, наверное, это всё не игровые задачи, а в играх это всё действительно может быть не нужно.

                                                                  А описанная выше политика вполне себе оправдана, в таких задачах. Потому что выгода от уменьшения дефрагментации может быть выше, чем пара тысячь тактов на создание нового процесса. Чистить же bss тут совершенно не нужно, а создание нового pagetable — это вообще стоимостью два значения в память записать.

                                                                  2. Очень интересно узнать, а как Вы сделаете ассоциативный кэш эффективно? Со всеми LRU, эвакуацией линий, ранней загрузкой нужного значения и тому подобным. Нет, Вы, конечно, можете сообщить сейчас, что это и не нужно ни разу… Но тратить на каждый доступ в память дополнительно десяток инструкций — не слишком ли это дорого?

                                                                  3. Проблема с многозадачностью очень простая: а как контекст переключать, если он здоровый и занимает, скажем, 128KiB, потому что без аппаратного кэша, контекстом будет являться вся локальная память. Опять же, Вы можете заявить, что это ни разу не нужно…

                                                                  4. А что мешает делать опросы в отдельной от графики нити?
                                                                    0
                                                                    >> пара тысячь тактов на создание нового процесса.

                                                                    Откуда вы это взяли?

                                                                    >> а создание нового pagetable — это вообще стоимостью два
                                                                    значения в память записать
                                                                    2? Как минимум 1024 в page directory и 1024 в как минимум 1 pagetable, а на самом деле гораздо больше.

                                                                    >> ранней загрузкой нужного значения

                                                                    Ранней загрузкой откуда? Если адрес ещё не известен?
                                                                    Если же чтение линейное, то кеш не нужен.

                                                                    >> Но тратить на каждый доступ в память дополнительно десяток инструкций — не слишком ли это дорого?

                                                                    Нет. потому что беготня по поинтерам — 100-пудово рано или поздно вызовет чтение из памяти, и десяток инструкций тут не помеха.

                                                                    >> Проблема с многозадачностью очень простая: а как контекст переключать, если он здоровый и занимает, скажем, 128KiB

                                                                    Это не так работает как вы думаете. SPU контекст обычно переключается когда заканчивается таймслайс процесса, либо если имеется SPU задача, которая засыпает (например ждёт какого-то события). Сохранение контекста довольно быстрое. ПСП 25GB/s
                                                                    + Имеются оптимизации по минимизации обьёма данных — не нужно сохранять весь local store, а только стейт конкретной задачи.
                                                                    В реальных играх сохранение SPU контекста вообще обычно не происходит.

                                                                    >> А кто сказал, что возможна только одна истинная организация взаимодействия с игроком и она реализована в CS?

                                                                    Придумайте лучше =)

                                                                    >>Почему нельзя разбить рендеринг, физику и взаимодействие с игроком по разным нитям?

                                                                    Потому что это зависимые операции. Разбитие только увеличит латентность. Опрос контроллеров ничего не занимает, поэтому его нет смысла выносить. Но вы не можете отправлять на рендер сцену, которая ещё не готова.
                                                                    Если в 1 поточном варианте всё это делается за 1 фрейм, то тут понадобится уже 2.
                                                                    Добавляем прочие латентности и плачем в подушку.

                                                                    >>Тем более, что даже на приставках CPU многоядерные, и даже более того, многопоточные

                                                                    Какая разница? Многоядерность используется на другом уровне — на уровне параллелизма данных и задач.
                                                                  0
                                                                  продолжаем =)
                                                                  >> А как fps связаны с латентностью управления?
                                                                  Человек нажимает кнопку. Опрос устройств ввода совершается обычно 1 раз за фрейм.

                                                                  for each frame {
                                                                  process_input()
                                                                  update_scene()
                                                                  render_scene()
                                                                  }

                                                                  Поступившие данные влияют на апдейт игровых объектов. Потом происходит отрисовка. Команды складываются в коммандный буфер GPU,
                                                                  спустя кадр (с точки зрения CPU) GPU начинает рисовать. На PC, из-за глубокой буферизации уже здесь может быть большая латентность.
                                                                  Когда кадр отрисован, изображение оказывается на экране на следующем обновлении дисплея. Т.е. если игра работает в 30fps, реальная латентность составляет 83-100мс, а то и больше.

                                                                  >> Вот вы боретесь за все эти такты и микросекунды, а при этом в итоге

                                                                  Я борюсь за то, чтобы был стабильный fps на конкретной консоли.
                                                                  Часто получается, иногда нет. Тут не прокатывает «купи видяху побыстрее».
                                                                  Микросекунды сами по себе ничего не значат.

                                                                  >> говорите: ну, впустую нарендерить 40 кадров в секунду — это вполне нормально

                                                                  Не в пустую =) fps лишним не бывает. В указанном мною CS это определяет уровень играбельности.

                                                                  Впрочем это уже глубокий оффтоп =)
                                                                    0
                                                                    Нет. А кто сказал, что возможна только одна истинная организация взаимодействия с игроком и она реализована в CS? Почему нельзя разбить рендеринг, физику и взаимодействие с игроком по разным нитям? Тем более, что даже на приставках CPU многоядерные, и даже более того, многопоточные.
                                                          0
                                                          А по поводу хождения по структурам на SPU — это сильно странно. Они же для другого предназначены. Разве для проходов по всяким деревьям не предназначены CPU-ядра, которые к этому хорошо приспособлены: автоматические кэши, скалярные операции, всё такое?
                                                    0
                                                    спасибо за статью, скорость выросла больше чем в 10 раз!!! но это муторно немного продумывать всю память )) ну иу меня фигня какая-то, с виртуальными методами не работает! точнее при вызове виртуального метода вываливаетм segmentation fault :(
                                                      0
                                                      Отличная статья. Кто бы ещё сказал, что она делает на Geektimes вместо центрального хабра?

                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                      Самое читаемое