Когда x/2 не равно x>>1

Наткнулась на блоге The Old New Thing на размышления на тему When is x/2 different from x>>1?. Там автор ссылается на Стандарт C, а не C++, но в целом все похоже. Итак, известно соотношение между сдвигами и делением и умножением на 2 в С++.
x*2 эквивалентно x<<1
x/2 эквивалентно x>>1

Соотношения эти выполняются не всегда. При сдвиге влево, x<<1, результат еще берется по модулю ULONG_MAX+1 или UINT_MAX+1 в зависимости от типа x. То есть при достаточно большом x первое соотношение выполнено не будет.
Если x отрицательно, то по Стандарту (5.8) поведение при сдвиге влево вовсе не должно как-то соотноситься с умножением на 2, а при сдвиге вправо зависит от реализации (implementation-defined). Например, при вычислении выражения (-1)>>1 я получила -1 во всех компиляторах, в которых смотрела. Хотя (-1)/2 это 0.
Microsoft Visual C++ Toolkit 2003:
-1
MSVC++6.0:
-1
MinGW gcc 3.4.4:
-1

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

Статья Testing For Developers

Статья Testing For Developers (Тестирование для разработчиков) - это советы по тестированию кода от профессионального тестера программистам. Часто бывает так, что код, переданный тестерам, не то чтобы не работает, а совсем не работает. Возникает резонный вопрос "Вы вообще это пробовали запустить?". Происходит это как правило не по злому умыслу программистов и не от лени, а потому что программистам зачастую не хватает навыков тестирования. Приведенные в статье советы помогут и тестерам, и программистам сделать их совместный труд более эффективным.

Лучшее за 2005 год

Первое сообщение в блоге датировано 21-м января 2005. С тех пор прошел целый год... За это время популярность блога несколько возросла, уже далеко не всех его читателей я знаю в лицо. Особенно она возросла после публикации ссылки сюда в закладках Компьютерры-Онлайн.

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

Вот подборка за 2005 год, разбитая по темам.

По основной теме блога: язык программирования C++
Приведение типов в C++ лидирует с большим отрывом. Этот пост держится в лидерах с момента его опубликования. Его пытались догнать только Точки следования (sequence points), безуспешно.

Сравнительно недавняя заметка о разработке нового стандарта C++ C++0x вызвала некоторое оживление.

Более-менее популярны были Выделение памяти под vector и довесок к нему Освобождение памяти, выделенной под vector.

Постов по поводу константности было несколько, но лишь один вызвал интерес, да и то довольно вялый. mutable и const_cast

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

3D шутер на языке Haskell. Пост вызванный вдруг появившимся у меня интересом к функциональному программированию вообще и к языку Haskell в частности.

Старенький пост Перепрограммирование Aibo все еще вызвает устойчивый интерес.

На перевод выступления Кармака на Quakecon 2004 было затрачено больше всего времени и сил. Но, увы, интерес был сравнительно небольшим, точно так же как и на сообщение Выступление Джона Кармака на QuakeCon2005 (в комментариях к нему есть сокращенный перевод, спасибо Александру Васильеву).

Развлекаловка
Развлекательные публикации с программистским уклоном людей порадовали. Я сама периодически заглядываю в комментарии к сообщению Художественная литература для программистов. Ссылок на всякие книги надовали - ух! Yuri рекомендовал там фильм Pirates of Silicon Valley, который я посмотрела, понравился. Надо будет еще посмотреть. Фильм этот порадует всех ненавистников Билла Гейтса. Он там изображен просто жутким гадом, актер его хорошо играет.

В разное время блог оживляли сообщения .kkrieger - о 3D шутере размером 96 килобайт, Nether Earth и Tower Toppler - о ремейках старых классических игрушек, Лучшие друзья девушки - о необычной бижутерии и о других симпатишных гэджэтах.

Updated 23.01.2006: Незаслуженно забыла весьма популярный рассказ о лекции профессора Вирта в Политехническом музее - Сегодня видела Никлауса Вирта.

Haskell и Java

Муж мне подкинул интересную ссылку. Написание одного и того же проекта на Haskell'е заняло часы, в то время как на Java - недели.

Дмитрий Астапов, автор Haskell варианта, утверждает, что он тут ни при чем, это просто Haskell для данной задачи подошел намного лучше Java. Возможно, скромничает.

CAPTCHA

CAPTCHA расшифровывается как Completely Automated Public Turing test to Tell Computers and Humans Apart. В переводе на русский: "Полностью автоматический публичный тест Тьюринга, который может отличить человека от компьютера". Тест Тьюринга - это предложенная Аланом Тьюрингом в его работе 1950-го года Computing Machinery and Intelligence игра, которую позже стали называть "Тест Тьюринга". Цель этого теста - методом последовательных вопросов выяснить кто перед тобой - человек или компьютер. Проблема эта очень актуальна для защиты ресурсов от различных роботов, особенно от спам-роботов.

Один из классических вариантов CAPTCHA - картинка со слегка деформированными буквами, которые человеку предлагается распознать. Есть и более экзотичные варианты, вот такой пробегал в ЖЖ:



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

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

Вот рассказ одного такого исследователя. Он решил распознать CAPTCHA на блоге друга.

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

Еще один проект, посвященный распознованию CAPTCHA, также без исходников. PWNtcha (Pretend We’re Not a Turing Computer but a Human Antagonist). Там есть веб-интерфейс, через который ей можно скормить картинку, а она попытается распознать буквы. Я ей скормила CAPTCHA с блоггера, не распозналось.
Не все CAPTCHA так уж легко распознаются. Есть отдельные плохие реализации.

Вот из проекта PWNtcha

	Один и тот же шрифт, без поворота, без деформации, символы выровнены, один и тот же фон, мало возможных цветов. Как результат - распознается PWNtcha на 100%.
	Один и тот же шрифт, постоянная позиция символов. Распознается PWNtcha на 99%.

Но если сильно увлечься деформациями и тому подобным, можно сделать CAPTCHA, которую и человек-то с трудом поймет, если поймет.


Работы по распознаванию CAPTCHA ведет UC Berkeley Computer Vision Group. Они работают с CAPTCHA под названием Gimpy и EZ-Gimpy (последнюю использует Yahoo!).

EZ-Gimpy		Распознается 92%
Gimpy		Распознается 33%

Критики таких CAPTCHA очень много. Что они формируют ложное чувствуо защищенности, сбивают с толку пользователя. Если у человека отключены картинки в браузере, то он вообще CAPTCHA не увидит. В качестве альтернативы предлагаются, например, логические задачки. Но тем не менее графические CAPTCHA с буквами очень распространены. У меня к ним сложное отношение. Раздражать они, конечно, раздражают, особенно когда с первого раза понять не получается что же там написано. Но с другой стороны, я слышала, что они действительно отсекают бОльшую часть спама. Статистики никакой по этому поводу я не видела, просто встречала мнения людей, что "да, помогает".

Ссылки по теме:
Второй раз повторяю: я человек! Статья про CAPTCHA на SecurityLab.
The CAPTCHA project
Accessibility Problems with Visual Verification Systems. Слайды, подробно разбирающие недостатки CAPTCHA, предлагаются решения.
Inaccessibility of CAPTCHA. Документ на w3.org.
WP-Gatekeeper

Советы по написанию портируемого кода от разработчиков Мозиллы

Набрела тут на мозилловские C++ Portability странички. Кому лучше знать про написание портируемого кода, чем разработчикам кроссплатформенного браузера.
Чего они хотели добиться: чтобы код компилировался без приключений в различных версиях одного и того же компилятора, также чтобы он компилировался разными компиляторами, на разных платформах. Они предупреждают, что портируемый код не бесплатен. Он требует большего объема тестирования, более глубоких знаний от программиста. Также накладывается ограничение на использование библиотек.

Чего собственно советуют: следовать стандарту, иметь копию стандарта при себе. Избегать "темных углов": нестандартных библиотек, специфических фич любимого компилятора. Знать о дефектах языка. Обращать внимание на ворнинги и исправлять их.
Из библиотек рекомендуют только STL и boost.

Один из разработчиков, Скотт Коллинз, рассказывает какие они приняли решения для обеспечения портируемости кода, какие из них оказались хорошими, а какие не очень.
Из плюсов Скотт упоминает регулярное тестирование кода на различных платформах, на различных компиляторах. Также они изобрели тулзы для поддержки портируемости. Это, например, XUL - язык описания интерфейсов.
Из минусов: не использовали исключения, не использовали STL, не использовали темплейты. Написали аналог COM'а, кроссплатформенный COM, XPCOM (Cross Platform Component Object Model). Сам по себе XPCOM не такой уж и плохой, однако, по мнению Скотта, его использование было оправдано в весьма небольшом количестве специфических мест, а его где только не использовали, включая места где это было совершенно не нужно.

В процессе разработки Мозиллы был составлен C++ portability guide. Это сборник правил, которыми руководствовались разработчики Мозиллы для обеспечения портируемости кода. Он составлен по результатам портирования кода на 25 разных машин и около дюжины компиляторов. Он несколько устарел, правила там драконовские. Как сказано выше, один из его составителей, Скотт Коллинз, признал, что некоторые из них, например отказ от исключений и от STL, были ошибочными.

Ссылки по теме:
Домашняя страничка Скотта Коллинза
Блог Скотта Коллинза

Ролики про робота по имени TempBot

Updated 11.1.2006: изменились URL'ы на сервере, так что мне тоже пришлось поменять ссылки. И они перевели все на ActiveX, так что первый ролик работает только в IE.

Грустный ролик про робота, который пытается работать в офисе вместе с людьми.
Робот целиком и полностью рисованный, но сделан очень качественно. Выглядит как настоящий. Я дала ссылку на маленький ролик, 38Мб, есть вариант побольше.

Про TempBot'а есть еще один ролик, Tetra Vaal, он там выступает в роли робота-полицейского. (Обычный .mov файл, без извращений.)

Ресурсы по оптимизации

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

Сайт Пита Исенси (Pete Isensee). Пит программист, сейчас он работает в группе Xbox и специализируется на оптимизации. На его сайте полно статей и слайдов.

Слайды с различных конференций, включая GDC2004 и GDC2005 на сайте ATI. По оптимизации это:
Optimizing DirectX Graphics первый вариант и второй вариант. Отличаются дизайном :-).
Tutorial Optimizations.
Optimizing Star Wars: Galaxies - тут больше про многопользовательские игры.

Можно скачать слайды с конференции Meltdown 2005. Что плохо, они запакованы пачкой все, так что придется качать все целиком. По оптимизации там Optimization Best Practices - Kang Su Gatlin.

Несколько стареньких статей с Гамасутры:
Optimizing Direct3D Applications For Hardware Acceleration
Optimizations Corner: Sorry... But Size Does Count!
Optimizing Games for the Pentium III Processor

Game Development Performance Optimization - раздел на сайте Intel. Соответственно, рассматриваются только Интеловские карточки и процессоры.

Знаменитые высказывания Джона Кармака

Я периодически встречаю цитирования Кармака, особенно про низкоуровневое программирование любят вспоминать. Вот, перевела наиболее известные.

Focused, hard work is the real key to success. Keep your eyes on the goal, and just keep taking the next step towards completing it. If you aren't sure which way to do something, do it both ways and see which works better.	Сосредоточенная, тяжелая работа - вот настоящий ключ к успеху. Видеть цель и делать каждый новый шаг в сторону ее завершения. Если не уверен каким способом делать что-либо, сделай обоими способами и посмотри какой из них лучше работает.
Low-level programming is good for the programmer's soul.	Низкоуровневое программирование хорошо для души программиста.
I'm good? Seriously?	Я хороший? Серьезно?
I'd rather have a search engine or a compiler on a deserted island than a game.	На необитаемом острове я предпочел бы иметь поисковик или компилятор, а не игру.
Note to self: Pasty-skinned programmers ought not stand in the Mojave desert for multiple hours.	Замечание для себя: Программистам с бледной кожей не стоит оставаться на несколько часов в пустыне Мохаве.
Because of the nature of Moore's law, anything that an extremely clever graphics programmer can do at one point can be replicated by a merely competent programmer some number of years later.	По природе закона Мура, все, что очень умный программист графики может сделать в какой-то момент времени, может быть повторено просто компетентным программистом через несколько лет.
Focus is a matter of deciding what things you're not going to do.	Сосредоточенность - это принятие решения по поводу того, какие вещи ты не собираешься делать.
I recognize that I possess a very special intellect, but at the same time, I recognize that I'm lacking in a lot of areas. But being well-rounded is greatly overrated.	Я осознаю, что я обладаю специфическим интеллектом, но в то же время, я понимаю, что не дотягиваю во многих областях. Но всестороннее образование сильно переоценено.
It's nice to have a game that sells a million copies.	Хорошо иметь игру, которая продается миллионами копий.
Programming is not a zero-sum game. Teaching something to a fellow programmer doesn't take it away from you. I'm happy to share what I can, because I'm in it for the love of programming.	Программирование - это не игра с нулевой суммой. С тебя не убудет, если ты научишь чему-либо знакомого программиста. Я счастлив поделиться тем, чем могу, потому что я занимаюсь всем этим из любви к программированию.
Story in a game is like a story in a porn movie. It's expected to be there, but it's not that important.	Сюжет в игре - это как сюжет в порнофильме. Он должен там быть, но он не так уж и важен.
Telneting into your rocket is sort of fundamentally cool.	В общем круто теленетиться на собственную ракету.
The cost of adding a feature isn't just the time it takes to code it. The cost also includes the addition of an obstacle to future expansion. ... The trick is to pick the features that don't fight each other.	Цена добавления фичи это не только время ее кодирования. Эта цена также включает в себя добавление препятствия для дальнейшего расширения. Вся штука в том, чтобы выбрать фичи, которые не мешают друг другу.
The speed of light sucks.	Скрость света - отстой.

Ссылки по теме:
John Carmack Quotes
John Carmack quotes
Выступление Джона Кармака на QuakeCon2005
Перевод выступления Кармака на Quakecon 2004