вторник, ноября 29, 2005

Статья Effective C++ Memory Allocation

В статье Effective C++ Memory Allocation, Аарон Дэйли (Aaron Dailey) рассказывает о реализации собственного менеджера памяти, обращаться к которому можно переопределив операторы new и delete. Это не абстрактная статья, таким образом организована работа с памятью в одной из разработанных Аароном встроенных систем. Несмотря на то, что статья адресована именно разработчикам встроенных систем, она может оказаться интересной и разработчикам игр.

Умер Джон Влиссидес

Джон Влиссидес (John Vlissides) был больше всего известен как один из соавторов книги "Приемы объектно-ориентированного проектирования. Паттерны проектирования" (Design Patterns: Elements of Reusable Object-Oriented Software). Всего авторов у этой очень известной книги по паттернам проектирования четыре: Эрих Гамма (Erich Gamma), Ричард Хелм (Richard Helm), Ральф Джонсон (Ralph Johnson) и Джон Влиссидес (John Vlissides). Иногда их называли "Банда четырех" (Gang of Four, GoF).

Martin Fowler's Bliki: JohnVlissides

среда, ноября 23, 2005

Освобождение памяти, выделенной под vector

Некоторое время назад я писала про выделение памяти под vector и в конце немного затронула тему высвобождения памяти. В большинстве реализаций освободить память, выделенную под vector, можно только с помощью трюка, известного как swap trick. Недавно я вычитала, что в реализации STL из 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 для последовательных контейнеров эквивалентен erase всего контейнера. Нашла упоминание об этом в документации STL на sgi.com. Вот оттуда выдержка:
a.clear() Equivalent to a.erase(a.begin(), a.end())
Запускаю код:
vector <int> v;
v.reserve(17);
cout<<v.capacity()<<endl;
v.erase(v.begin(), v.end());
cout<<v.capacity()<<endl;

Получаю:
Microsoft Visual C++ Toolkit 2003:
17
17 //не освободилась
MSVC++6.0:
17
17
MinGW gcc 3.4.4:
17
17

Получается, что в случае вышеупомянутого тулкита нет обещанной эквивалентности. Так, а что говорит об этом Стандарт? Вот тут интересный момент. Там нет слова "эквивалентно". Там erase(begin(), end()) приписано к clear() в качестве assertion/note для последовательных контейнеров. А вот требование там одно, что post condition: size()==0. Оно тут выполняется.
Так что MSVC++2003 тут прав.
Я пробовала также v.resize(0). Пробовала удалить все элементы вектора с помощью pop_back'ов. Память не освобождается. Это происходит только при вызове clear.

Ссылки по теме:
STL vector and reserve

воскресенье, ноября 20, 2005

Непрерывная подгрузка уровней

Статья о непрерывной подгрузке уровней на примере игры Dungeon Siege. Кроме самой статьи есть также слайды.

Вообще идея подгружать уровни непрерывно, не показывать игроку картинки с заставками и тем самым не прерывать геймплей очень интересна. Сейчас я это реализую в Winding Trail, но у нас все значительно проще, сама игра значительно меньше. В статье о Dungeon Siege рассказывается об организации непрерывной подгрузки, которую они делают отдельным потоком, что породило огромное количество странных багов, которые они потом ловили. Кроме этого говорится и о других проблемах, о которых при организации такого вот непрерывного мира сразу и не подумаешь. Например, у них начали переполняться float'ы при подсчете расстояний. Кроме всего прочего у них игра поддерживает многопользовательский режим, что еще добавило сложности. В итоге у них получился Игровой Мир с неевклидовой геометрией и одному из дизайнеров удалось создать в буквальном смысле слова бесконечную пустыню.

Статья очень хорошая, там не просто говорится "мы сделали так-то и так-то", а рассказывается почему они пришли именно к таким решениям, и какие претензии к этим решениям у них остались.

Там же они рекомендуют слайды на ту же тему: Stuart Denman. Highly Detailed Continuous Worlds: Streaming Game Resources from Slow Media. (PPT)

вторник, ноября 15, 2005

Точки следования (sequence points)

Их не рассматривают на занятиях, о них редко пишут в книгах. Тем не менее любой, кто пишет на C++, с ними сталкивается постоянно в ходе своей работе. И если знать о них чуть больше, многие из вещей, казавшихся раньше таинственными, становятся очевидными.

О таинственном. Я пишу программу
int x=0;
x=x++;
cout<<x;

Вопрос: что выведется на экран? Ну что может быть проще - сейчас запустим да проверим. Я запустила MSVC++6.0, ответ получился 1.
Потом запустила gcc 3.4.4 и получился 0.
Если бы запустила что-то еще, то могло получиться нечто третье...
Кто из них прав? На самом деле все. А вот почему так в двух словах и не скажешь...

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

Точки следования (sequence points) - это некие точки в программе, где состояние реальной программы полностью соответствует состоянию абстрактной машины, описанной в Стандарте. С помощью точек следования стандарт объясняет, что может, а чего не может делать компилятор и что нам нужно сделать, чтобы написать корректный код.

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

Если код выглядит так:
int x;
x = 3;
cout << x << endl;
x = 4;

То нет никаких сомнений, что на печать будет выведено 3. Точка с запятой в конце выражения "x = 3;" как и любая точка с запятой в конце любого выражения - это точка следования. Перед тем как любой код после этой точки с запятой выполнится, побочный эффект от сохранения значения 3 в int объект x должен быть полностью завершен. И мы точно знаем, что вывод не будет равен 4, потому что вывод полностью завершен к тому моменту, как выполнение программы достигнет точки с запятой в конце выражения "cout << x << endl;". Побочный эффект от сохранения значения 4 в x в следующем выражении еще не случился.

Где находятся точки следования


  1. В конце каждого полного выражения(Глава Стандарта 1.9/16). Обычно они помечены точкой с запятой ;

  2. В точке вызова функции (1.9/17). Но после вычисления всех аргументов. Это и для inline функций в том числе.

  3. При возвращении из функции. (1.9/17) Есть точка следования сразу после возврата функции, перед тем как любой другой код из вызвавшей функции начал выполняться.

  4. (1.9/18) После первого выражения (здесь оно называется 'a') в следующих конструкциях:

    a || b

    a && b

    a , b

    a ? b : c

    Вычисление здесь идет слева направо. То есть левое выражение (по имени 'a') вычисляется и все побочные эффекты от такого вычисления завершаются. Потом, если все значение всего выражения известно, правое выражение не вычисляется, иначе вычисляется.
    Правило слево-направо не работает для переопределенных операторов. В этом случае переопределенный оператор ведет себя как обычная функция. Еще такой момент - ?: не может быть переопределен по стандарту.

    (Упомянутая запятая это оператор запятая. Она не имеет никакого отношения к запятой, разделяющей аргументы функции.)


Если рассмотреть пример "x = x++;", то здесь имеет место попытка изменить объект дважды.
Если программа пытается модифицировать одну переменную дважды не пересекая точку следования, то это ведет к undefined behavior. Так говорит Стандарт. И тут же в Стандарте приводятся примеры.

1) i = v[i++]; //unspecified behavior
2) i = 7, i++, i++; //i равно 9

3) i = ++i + 1; //unspecified behavior
4) i = i + 1; //значение i увеличено на 1

Что-то с чем-то не сходится. В первом и третьем примерах указано "unspecified behavior", хотя переменная изменяется дважды и только что было сказано, что это ведет к undefined behavior.
И точно в списке багов Стандарта это место упомянуто. В предложении по устранению бага советуют поменять слово unspecified на слово undefined.
Но на самом деле не так уж и важно, unspecified или undefined behavior. Важно то, что непонятно, что именно получится в итоге. Поэтому не надо модифицировать переменную больше одного раза между двумя точками следования, поскольку это может привести к весьма неожиданным последствиям. Вот, например
int x;
x = 3;
cout << (++ x + ++ x) + ++ x << endl;
x = 3;
cout << ++ x + (++ x + ++ x) << endl;

gcc 3.4.4:
16
18
Получилось, что операция сложения не ассоциативна!

MSVC++6.0:
18
18

Примеры:
i = ++i; // undefined behavior, переменная модифицируется дважды
i = i + 1; // все в порядке
i ? i=1 : i=5; // все в порядке (там, где знак ? есть точка следования, а потом выполнится лишь одно из выражений)
i=1; i++; // все в порядке (после каждого выражения находится точка следования)
i=1, i++; // все в порядке (на операторе запятая находится точка следования)

Пример с функциями:
void f(int, int);
int g();
int h();
f(g(), h());
По Стандарту неизвестно, какая из функций g или h будет вызвана первой, но известно, что f() будет вызвана последней.


Разработчикам gcc периодически сабмитят баги по этому поводу, в итоге в
Frequently Reported Bugs in GCC было внесено:
Результат следующих операций непредсказуем и это полностью соответствует стандарту
x[i]=++i
foo(i,++i)
i*(++i) /* special case with foo=="operator*" */
std::cout << i << ++i /* foo(foo(std::cout,i),++i) */

Вот пример такой баги: Bug13403. Их таких там очень много.

В следующей программе
#include <iostream>
int main(){
int i=0;
i = 6+ i++ + 2000;
std::cout << i << std::endl;
return 0;
}

Результат единица! А должен быть 2006.
Если убрать "i++", то результат правильный ("2006"). Но пока есть "i++" внутри выражения, я могу делить, умножать, вычитать, складывать, все равно результат всегда "1".
Например в выражении
i = (6+ i++ + 2000)/2;
"i" все равно единица.

Но если я заменю постфикс "i++" префиксом "++i" тогда все считается корректно.


Ну отвечают на это все - "это undefined behavior по Стандарту" и баг закрывают.

Несколько присваиваний подряд
Интересный момент с таким кодом:
int a=1, b=2, c=3;
a=b=c=0;
Стандарт как-то очень нечетко описывает такую ситуацию. Он говорит, что операция должна происходить справа налево, но ничего не говорит дополнительно по поводу того, когда должен быть результат этой операции записан в переменную. Точек следования внутри выражения нет, что значит, что компилятор может теоретически творить здесь что угодно и не обязательно все переменные в итоге будут равны 0. Так что, опять же теоретически, здесь имеет место unspecified behavior. По этому поводу периодически рождаются хвостатые флеймы в comp.lang.c++.moderated. Но на самом деле я не слышала о компиляторе, который делал бы в такой ситуации присвоение не справа налево. Вопрос этот известен, а компиляторы не садисты пишут.

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

Ссылки по теме:
Разница между unspecified behavior и undefined behavior
comp.lang.c++.moderated Undefined behavior?? I think not!
comp.lang.c++.moderated postfix increment and assignment
comp.lang.c++.moderated fresh look on copying objects and passing args by value
comp.lang.c++.moderated Evaluation precedence questions
comp.lang.c++.moderated = Operator?
comp.lang.c++.moderated How defined is undefined behaviour?
comp.lang.c++.moderated Case for post-increment/decrement
comp.lang.c++.moderated What is a sequence point?
comp.lang.c++.moderated Sequence point and evaluation order
comp.lang.c++.moderated sequence point and reference
comp.lang.c++.moderated sequence points and , operator

пятница, ноября 11, 2005

Открыт блог проекта Winding Trail

Мы с Джимом открыли блог нашего игрового проекта под рабочим названием Winding Trail, разработка которого идет полным ходом.
Честно говоря, меня мучали сомнения - "а не преждевременно ли?". Но сомнения такого рода меня мучают постоянно, поэтому я решила на них забить.

вторник, ноября 08, 2005

Aardvark'd - документальный фильм о работе программистов

Этим летом Джоэл Спольски затеял интересный проект. Он пригласил на работу стажеров и дал им задание за 12 недель создать готовый программный продукт. Обычно-то стажеров загружают всякой фигней. Стажеры вели блог о своей работе: Aardvark блог. Проект закончился успешно, продукт они выпустили.
Сейчас на DVD вышел документальный фильм о проекте Aardvark под названием Aardvark'd, 12 weeks with geeks.

пятница, ноября 04, 2005

Тесты Brainbench бесплатны до 15 ноября

Brainbench - сравнительно известный сервис по тестированию на самые различные знания, в том числе и на знание программирования. Оценка умения программировать таким образом кажется мне сомнительной, но Brainbench сделал свои тесты бесплатными до 15 ноября, почему бы и не попробовать? Бумажный сертификат высылается за деньги, как и было. Как говорит Brainbench, по "многочисленным просьбам" в апреле 2006 вновь пройдут какие-то их Игры и вот, чтобы народ мог к ним подготовиться они открывают всю библиотеку тестов.
Когда-то давно тесты постоянно были бесплатными и назывался он не Brainbench, а Tekmetrics. И бумажные сертификаты высылали бесплатно, а сейчас только за деньги...

вторник, ноября 01, 2005

Художественная литература для программистов

Как-то так получилось, что все книги, которые я читаю в последнее время так или иначе связаны с программированием. Вот несколько лучших на мой взгляд книг, в которых рассказывается о технических вещах, но тем не менее, к технической литературе их отнести нельзя.




Just for fun. Рассказ нечаянного революционера
Авторы: Линус Торвальдс, Дэвид Даймонд

Биография Линуса Торвальдса, создателя Linux. Собственно о том, как он писал Linux и рассказывается в основном. Написано очень весело, с юмором, перевод хороший.

online: Just for fun. Рассказ нечаянного революционера.

Купить на Amazon.com: Just for Fun: The Story of an Accidental Revolutionary


Хакеры, герои компьютерной революции
Автор: Стивен Леви

О первых хакерах, не о тех, кого сейчас называют хакерами, а о людях, пытавшихся лучше понять и использовать компьютеры. О создании первых персональных компьютеров. О Старых Добрых Временах. Единственный минус - повествование несколько занудное.

online: Хакеры, герои компьютерной революции
Купить на Amazon.com: Hackers: Heroes of the Computer Revolution



Криптономикон
Автор: Нил Стивенсон

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

online: Криптономикон часть 1, Криптономикон часть 2.

Купить на Amazon.com: Cryptonomicon


Сейчас разыскиваю чего бы еще почитать в том же духе. Меня заинтересовала Crypto Стивена Леви, хотя отзывы о ней на Амазоне неоднозначные. Может кто-нибудь еще чего присоветует?