четверг, июня 30, 2005

Выделение памяти под vector

В описании контейнера vector можно встретить такие функции как size и resize, capacity и reserve. С первого взгляда кажется, что половина явно лишняя, ведь размер у вектора может быть только один.
Почему так? Потому что память для вектора выделяется "про запас"(подробнее ниже), и надо уметь управлять и количеством элементов вектора, и количеством памяти, которое он занимает. size и resize - нужны для работы с реальным числом элементов вектора, capacity и reserve - для работы с памятью.
size - выдает количество элементов в векторе
resize - изменяет количество элементов в векторе
capacity - выдает под сколько элементов выделена память
reserve - резервиует память

Вот что сделает код, скомпиленный Visual C++ 6.0:

vector <int> v;
v.push_back(1); //size==1, capacity==1
v.push_back(17); //size==2, capacity==2
v.push_back(23); //size==3, capacity==4


Зачем нужен этот запас?
Допустим, у нас есть вектор из n элементов. Что происходит, когда программист добавляет еще один? Когда есть запасная память, элемент пишется туда. Когда ее нет, выделяется непрерывный кусок памяти достаточный для n*K элементов, где K - коэффицент. В него копируются предыдущие n, добавляется наш новый элемент, старый кусок размером n освобождается. Если бы запаса не было, то память бы выделялась каждый раз при добавлении нового элемента, что страшно неэффективно.
Зачем нужен reserve, если все и без участия программиста так хорошо работает? Это может быть полезно в некоторых ситуациях. Например, знание того, как выделяется память под вектор, можно использовать и в начале, при его задании. Допустим, я точно знаю, что в векторе будет где-то 100-110 элементов. Я сразу же создам вектор размером 110, это поможет избежать перевыделений памяти, положительно скажется на производительности.

vector <int> v;
v.reserve(110);

Это вовсе не означает, что зарезервировано место для 110-ти элементов ровно. Зарезервировано место как минимум для 110 элементов, возможно больше.

Почему обязательно нужно выделять непрерывный кусок памяти, почему при увеличении размера вектора нельзя выделить кусочек где-нибудь еще? Чтобы можно было передавать vector как параметр в функции, которые требуют массив. Например, в какую-нибудь старую библиотечную С-функцию, которая принимает массив и его размер, можно передать вектор, при условии, что он не пустой. Это было сделано специально, чтобы убедить людей пользоваться векторами. Ведь можно продолжать использовать старые библиотеки.

//если где-то описана такая функция
void myPrint(int* v, int vsize);

//ее можно вызвать так
vector <int> v;
v.push_back(2);
v.push_back(3);
myPrint(&v[0], v.size());


Коэффицент К
(Все приведенные ниже рассуждения верны только для first-fit схем выделения памяти, то есть выделяется первый по порядку подходящий кусок)
Что за коэффицент K, который используется при выделении памяти , чему он равен? Так, как у нас там происходит выделение памяти... Новую выделили, прокопировали туда данные, старую освободили. И так несколько раз. Если память идет подряд, то образуется пробел, который можно было бы использовать. Нужно подобрать такой коэффицент, который позволит эти пробелы использовать. Было вычислено, что коэффицент должен быть меньше, чем (1+sqrt(5))/2. Что примечательно, выражение (1+sqrt(5))/2 - это же "золотое сечение".
Откуда берется это число?

Я видела вот такое доказательство:
Пусть у нас изначально размер вектора был S, S>0.
После первого перевыделения памяти, он стал K*S.
После второго K*K*S.

Нам нужно, чтобы K*K*S влезло в S+K*S, то есть K*K*S<=S+K*S. S>0, на него можно сократить.
K^2-K-1<=0
Решаем, получаем
K<=(1+sqrt(5))/2 (второй корень, отрицательный, не интересен)
Правильно? Не правильно. Кусок K*S все еще занят, его нельзя использовать.

Нам нужно, чтобы в момент выделения K^(n+1)*S память размером S+K*S+K^2*S+...+K^(n-1)*S была достаточной, чтобы вместить этот K^(n+1)*S. K^n*S все еще занят, мы его использовать не можем. В итоге получаем.
S+K*S+K^2*S+...+K^(n-1)*S <= K^(n+1)*S или, зная, что S>0
1+K+K^2+...+K^(n-1) <= K^(n+1)
Решать я это не буду, Andrew Koenig считает, что подходящий в данном случае корень (1+sqrt(5))/2, доверюсь ему.
Если говорить уж совсем точно, то (1+sqrt(5))/2 не совсем правильное число, нужнен коэффицент поменьше. Потому что нужна еще дополнительная память для разных служебных нужд.
В Visual C++ 6.0 взята константа 2. Такой коэффицент использовать пробелы не дает. А вот в Visual C++ 7 уже используется константа 1.5.

Swap Trick

Про выделение памяти ясно. А как с освобождением памяти? Да, при увеличении размера вектора будет выделена память, а когда вектор уменьшается? Нет, она не будет освобождена. Что несколько неудобно, потому что если в векторе было 10000 элементов, а потом их количество уменьшилось до 10 и осталось где-то в таких пределах, то получается что куча памяти пропадает зря. Что можно сделать в такой ситуации? Сделать новый вектор и туда прокопировать старый. Это можно сделать красиво с помощью swap trick.
vector<int>(v).swap(v);
В этой строчке происходит следующее: создается безымянный vector <int>, который инициализируется элементами из v, а потом он меняется с вектором v местами. Это вовсе не гарантирует, что памяти будет выделено ровно столько, сколько нужно, а не больше. Это зависит от реализации. Но, скорее всего, все будет лучше, чем было.
Я читала у Герба Саттера, что swap сохраняет в корректном состоянии все итераторы, ссылки и указатели.

Может я чего-то не понимаю, но у меня получилось вот что.

std::vector <int> v;
std::vector <int>::iterator it;

v.push_back(1);
v.push_back(2);
v.push_back(3);

it=v.begin();
cout<<*it<<endl;

vector<int>(v).swap(v);
cout<<*it<<endl; //компиляла и gcc, и VC++ в обоих случаях получила мусор

Updated 23.11.2005:
Вычитала, что в Visual C++ 7.1 при вызове метода clear() память таки высвобождается. Не могу проверить для 7.1, зато проверила для Microsoft Visual C++ Toolkit 2003. Действительно, память освобождается.

То есть для такого кода:
vector <int> v;
v.reserve(17);
cout<<v.capacity()<<endl;
v.clear();
cout<<v.capacity()<<endl;

Вывод получается следующим
Microsoft Visual C++ Toolkit 2003:
17
0
MSVC++6.0:
17
17
MinGW gcc 3.4.4:
17
17

Стандарт не указывает должна ли освобождаться память при вызове метода clear(), так что все компиляторы здесь действуют по Стандарту.

Ссылки по теме:
Vector Resizing Algorithm
comp.lamg.c++.moderated, vector growth factor of 1.5


Technorati tag:

пятница, июня 24, 2005

Что такое "ABC"?

ABC - это распространенное сокращение от abstract base class, абстрактный базовый класс.
Абстрактный класс - это класс, в котором есть хотя бы одна чисто виртуальная функция. Создать экземпляр такого класса нельзя, ошибка вылезет на этапе компиляции. ABC обязывает наследников, экземпляры которых будут создаваться, переопределить все чисто виртуальные функции и тем самым определить конкретное поведение наследника.
Пример абстрактного класса:

class CMyClass
{
public:
virtual void myPureVirtual()=0;
};


Technorati tag:

пятница, июня 17, 2005

Чем плох vector <bool>

vector <bool> - это пример неудачной стандартизации контейнера. Что представляет собой vector <bool> согласно стандарту? На его примере решили показать как можно использовать проксированный контейнер. Это контейнер, к объектам которого нет прямого доступа. Работать с ними нужно через специальные прокси-объекты. Под один так называемый bool здесь отводится один бит, что не соответствует реальному типу bool, под который обычно отводится 8 бит (возможно больше). Для доступа к этим битам есть прокси-класс по имени reference, который, как утверждается, ведет себя как ссылка на бит. Нужен он потому, что типа бит не существует, а работать с отдельными элементами vector <bool>'а как-то надо. reference же позволяет написать выражение вида v[0] = true.
С первого взгляда такой подход к реализации vector <bool> выглядит неплохо, так как экономится память, но при внимательном рассмотрении возникают проблемы. Поскольку vector <bool>::reference не является обычной ссылкой, а лишь ведет себя похоже, не будет компилироваться код, который верен для всех векторов, кроме vector <bool>:

vector <bool> myVBool;
...
bool *pBool = &myVBool[0];

Итераторам для работы тоже нужна обычная ссылка, а не ее имитация.

Также для работы с vector <bool> были добавлены специфичные функции, которых нет у других векторов. Например flip(), которая инвертирует значение битов вектора.
В итоге получается, что vector <bool>, это и не vector, поскольку в нем отсутствуют стандартные возможности векторов и добавлены некоторые новые. И не bool, потому что его составными элементами являются отдельные биты, а не объекты типа bool. Более того, это решение фактически заставляет программиста использовать оптимизацию памяти, которая зачастую не нужна, зато это потенциально медленнее. Не для всех 1 килобайт - это страшная потеря, а экономия памяти будет в таких порядках.

В итоге тем, что получилось из vector <bool>, лучше не пользоваться. А что если он очень нужен? Вместо него можно использовать vector <char>, vector <int>, deque <bool>, bitset. bitset, правда не контейнер, к нему нельзя добавлять и из него удалять элементы, но он также использует 1 бит на bool.

Несколько слов о реализации vector <bool>. Как правило, его реализовывают согласно стандарту. Так сделано в популярной мультиплатформенной реализации STLPort. А что в родной реализации Visual C++?
В VC++5.0 vector <bool> был реализован не согласно стандарту и эта реализация перекочевала в 6.0. bool тут - обычный bool, никакого проксирования.
Вот этот код там успешно компиляется
vector <bool> myVBool;
...
bool *pBool = &myVBool[0];


Зато вот этот - уже нет:

vector <bool> myVBool;
myVBool.push_back(true);
myVBool.flip();

Хотя по стандарту должен.

Проблема с vector <bool> была замечена в конце 96-го года, Bill (PJ) Plauger (кстати, он президент той самой компании Dinkumware, которая писала реализацию STL для Visual C++ 5.0) упомянул о ней в статье C/C++ Users Journal. В конце 96-го, начале 97-го этот вопрос активно обсуждался в comp.lang.c++.moderated и comp.std.c++. После долгих разговоров, в 1999 году Herb Sutter направил в ISO два письма с описанием проблемы и предложениями по поводу ее устранения, пока никаких изменений внесено не было.

Ссылки по теме:
Стандарт на реализацию контейнеров. О vector <bool> сказано в пункте 23.2.5.
When Is a Container Not a Container?
vector <bool> Is Nonconforming, and Forces Optimization Choice
vector <bool>: More Problems, Better Solutions

Technorati tag:

среда, июня 08, 2005

Разработка под видекарты Intel

Вопреки устоявшемуся мнению видеокарты Интел весьма распространены. Сам Интел приводит цифру 40%, возможно они слегка лукавят, но доля значительная. Крупные производители игр не очень жалуют вниманием эти видеокарты, хотя Интел всячески пытается их привлечь на свою сторону. Но для shareware игр Интеловские карточки являются чуть ли не основными.

Интеловские видеокарты - это дешевые и встроенные решения. Чтобы обеспечить им приемлемую скорость работы, Интел применяет специфические подходы, пути ATI и NVidia им не подходят.
Итак, подробнее, какие именно подходы и что из этого следует.

Софтверные TnL(Transform and Lightning) и вертексные шейдеры (vertex shader)
Интеловская карточка не может позволить себе обрабатывать 3D геометрию хардварно, как это делают многие другие. Однако часто разработчики запрашивают только хардварную поддержку, на что им справедливо следует ответ, что ничего нет. То есть вместо IDirect3D::GetCaps() надо спросить IDirect3DDevice::GetCaps(). Соответственно, девайс должен быть создан с флагом D3DCREATE_SOFTWARE_VERTEXPROCESSING.
Интел говорит, что с Pentium4 софтверная обработка будет работать на вполне пристойной скорости, при этом они ненавязчиво предлагают делать игры многопоточными, чтобы использовался гипертрединг(Hyper-Threading Technology).
Пиксельные шейдеры есть на 900 серии карточек, они как раз реализованы хардварно.

Технология Zone Rendering
Используется для того, чтобы увеличить скорость рендеринга. Все треугольники сцены делятся на зоны, достаточно маленькие для того, чтобы они могли поместиться в кэше чипа. Зоны рисуются по-очереди. Сначала треугольники зоны сортируются по грубине, если надо, обрабатывается прозрачность, а потом отрисовываются. Цвет каждого пиксела пишется таким образом только один раз, не тратится время на лишнюю передачу. Это и есть Zone Rendering.

Zone Rendering - это эдакая неизбежная забота. Оно само лучше знает когда ему включаться, а когда выключаться. Оно постарается включиться, но если его что-то обеспокоит, то оно уйдет и придут ТОРМОЗА. Поэтому надо следовать определенным правилам, чтобы Zone Rendering не выключился и работал с максимальной отдачей:

  • Если требуется смена render target, то менять его перед отрисовкой сцены.
  • Не читать из Color, Z, Stencil буферов. Это вообще всегда медленно. Но на Интеловских карточках особенно плохо читать из Z-буфера. Zone Rendering в силу логики своей работы вообще Z-буфер не использует. За счет этого достигается большой рост производительности. А если из него начать читать, то его придется поддерживать.
  • Чистить буферы осторожно, лучше всего одновременно все, один раз в кадр. Когда это невозможно чистить Z и Stencil буферы вместе. Не чистить их по кусочкам.
  • Не смешивать 2D и 3D в одной 3D сцене.

Итак, управлять включением/выключением Zone Rendering можно, но только косвенно. Чтобы его выключить достаточно НЕ следовать вышеперечисленным правилам.

После внимательного изучения работы Zone Rendering возникает несколько вопросов:

Что будет, если треугольники настолько большие, что занимают несколько зон? Ответ на этот вопрос прозвучал на докладе на КРИ. Они будут прокопированы.

Что будет, если треугольники расположены таким образом, что их нельзя отсортировать по глубине? Предполагаю, что треугольники как-то дробятся на части. Выглядит все как и должно выглядеть.



Возникает вопрос и в связи с альфа-геометрией или, по простому, с прозрачностью.
Несколько слов о том, как реализована прозрачность. Все сплошной обман. Если у вас есть прозрачная текстура, то она не обладает прозрачностью в бытовом смысле этого слова. На ней просто нарисовано то, что в данный момент находится _за_ ней. В фильме про Джеймса Бонда была такая прозрачная машина, я помню. Поэтому прозрачные объекты следует выводить на экран в последнюю очередь. А то получится совсем не то, что хотелось бы. Вот пример: за забором находятся ящики. Но если ящики начать рисовать после забора, картина становится странной.



Ну а если Zone Rendering все сортирует за нас, быть может нам уже и не надо заботиться о правильном порядке отрисовки прозрачных объектов? Я попробовала.
Вот у этого забора сначала идут треугольники с красной стороны, потом с синей. Забор отправляется на отрисовку целиком, за один раз.



Вот что нарисовал GeForce6800. Со стороны красной стрелки забор отрисовывается не в том порядке, прозрачностью не кооректная.



А вот что Intel. Глюки с отрисовкой забора сохранились.





То ли догадки оказались неверны, то ли у меня по какой-то причине отключился Zone Rendering...

Dynamic Video Memory Technology (DVMT)
У Интеловской карточки нет своей видеопамяти, поэтому она использует оперативную. Вообще под видеопамять всегда выделено небольшое количество оперативной памяти, размер проставляется в БИОСе. Интеловская карточка может использовать и эту память, плюс запросить еще.
Когда приложение запрашивает видеопамять у Intel Graphics Driver (при запрашивании видеопамяти следует использовать флаг D3DPOOL_MANAGED), то этот запрос передается операционной системе. ОС выделяет нужно количество памяти. Когда приложение, запросившее память, будет закрыто, DVMT отдаст ее обратно ОС. Количество памяти, которую может запросить себе DVMT ограничено и зависит от того, сколько ее вообще есть в наличии.
Для проверки свободной видеопамяти можно использовать функцию GetAvailableTextureMem().

Интеловские карточки не поддерживают антиалиасинг. Интел предлагает его реализовывать вручную :-).

У Интела есть профайлер кода специально для их карточек, но только для 900 серии. Intel Graphics Media Accelerator profiler (IGMAP). Расскажет про доступную видеопамять, сколько треугольников в секунду и в кадр ему было отправлено и пр., ну и конечно включен ли Zone Rendering.

Очень много информации по этому поводу доступно на Intel Game Developers' Center. Все вышеизложенное гораздо подробнее и с примерами кода.

Technorati tag:

четверг, июня 02, 2005

TopCoder анонсировал TopCoder Open 2005

TopCoder - это сорвенования по программированию. От многих других соревнований их отличает то, что TopCoder платит деньги победителям. Призовой фонд в этом году составляет 150 000 долларов.
Соревнования до последних туров проходят удаленно, так что принять участие в них может практически любой желающий.
Проводятся соревнования двух видов.
Component Design & Development Competition - это разработка компонентов на Яве. На выполнение задания каждого тура дается около недели. Регистрация на эти соревнования будет проходить с 13 по 29 июня.
Algorithm Competition - решение логических задач на время. За 1 час 15 минут надо спрограммить 3 неслабые задачи разного уровня сложности. Это соревнование пользуется гораздо большей популярностью чем первое. Регистрация будет с 1 по 16 августа. Но есть небольшой нюанс. Поскольку соревнования проводят американцы, какой-нибудь из этапов да выпадает на очень неудобное время. Что-либо программить в 5 утра несколько напряжно :-).
Часто люди когда слышат про эти соревнования радостно считают, что деньги у них уже в кармане. Подумаешь, 3 задачки спрограммить. Не все так просто. Конкуренты у вас - со всего мира, это не городская Олимпиада по программированию. И потребуются вам весьма глубокие познания в алгоритмах на графах, теории вероятности, теории игр и т.п.
Потренироваться можно уже сейчас. TopCoder проводит мини-соревнования без призов каждую неделю.