В этот раз я хочу поделиться с вами одной проблемой, с которой столкнулся, когда решил сравнить итерационные и рекурсивные функции в C++. Между рекурсией и итерацией есть несколько отличий: о них подробно рассказано в этой стать. В языках общего назначения вроде Java, C или Python рекурсия довольно затратна по сравнению с итерацией из-за необходимости каждый раз выделять новый стековый фрэйм. В C/C++ эти затраты можно легко устранить, указав оптимизирующему компилятору использовать хвостовую рекурсию, при которой определенные типы рекурсии (а точнее, определенные виды хвостовых вызовов) преобразуются в команды безусловного перехода. Для осуществления такого преобразования необходимо, чтобы самым последним действием функции перед возвратом значения был вызов еще одной функции (в данном случае себя самой). При таком сценарии безусловный переход к началу второй подпрограммы безопасен. Главный недостаток рекурсивных алгоритмов в императивных языках заключается в том, что в них не всегда возможно иметь хвостовые вызовы, т.е. выделение места для адреса функции (и связанных с ней переменных, например, структур) на стеке при каждом вызове. При слишком большой глубине рекурсии это может привести к переполнению стека из-за ограничения на его максимальный размер, который обычно на порядки меньше объема оперативной памяти.

Как известно, недавно была опубликована книга по паттернам проектирования за авторством Сергея Теплякова.

Дабы поддержать мною уважаемого нашего разработчика (сам Сергей, несмотря на переезд заграницу, всё ещё считает себя нашим — за пруфом идите к нему в блог), не пожалел денег и сразу же купил электронную версию. До этого я читал банду четырёх и Design Patterns Head First, поэтому, в принципе, есть с чем сравнить.
Книга занимает чуть более 300 страниц, что вполне можно осилить за неделю неторопливого чтения. Книга разбита на 4 части:

1. Паттерны поведения
2. Порождающие паттерны
3. Структурные паттерны
4. Принципы проектирования

Чего только ни услышишь от апологетов тех же Java или C# про разработку на C/C++! Якобы этот язык устарел и на нем никто не пишет. Вот только когда требуется создать no latency или low latency сервис или нужно сэкономить память и время выполнения узкого места обработки больших объемов данных, то тут же прибегают за помощью к «архаичным» разработчикам на C/C++. Просто потому, что эти ребята умеют вручную управлять памятью и прекрасно представляют, что за начинка у той или иной высокоуровневой операции. Сегодня наша задача — стать на шаг ближе к этим ребятам.

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

Меня настолько заинтересовал вопрос о книгах, что я решил начать новую серию статей на своём сайте catonmat о моих топ-100 книгах о программировании, программном обеспечении, науке, физике, математике и компьютерах. В каждой статье я буду размещать по пять книг, ведь разбивать огромное задачи на маленькие подзадачи — это самый простой способ их решать (GTD — get things done).

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

Переменные и типы хороши, пока мы находимся внутри логики программы C++. Однако рано или поздно становится нужно передавать информацию между программами, между серверами или даже просто показать типы и значения переменных человеку разумному. В этом случае нам приходится заключать сделку со злобным Сериализатором и расплачиваться производительностью своего кода. В последней лекции Академии C++ мы наконец дошли до главного босса, которого нужно научиться побеждать с минимальными потерями в скорости выполнения кода. Поехали!

Шаблоны можно назвать самым главным отличием и основным преимуществом языка C++. Возможность создать шаблон алгоритма для различных типов без копирования кода и со строгой проверкой типов — это лишь один из аспектов использования шаблонов. Код специализаций шаблона строится на этапе компиляции, а это значит, что поведением создаваемых типов и функций можно управлять. Как тут удержаться от возможности попрограммировать компилируемые классы?

Метапрограммирование становится столь же неотъемлемой частью написания кода на C++, как и использование стандартной библиотеки, часть которой создана именно для использования на этапе компиляции. Сегодня мы произведем на свет библиотеку безопасного приведения скалярных типов C++, метапрограммируя шаблонами!

Метапрограммирование — вид программирования, связанный с созданием программ, которые порождают другие программы как результат своей работы (wiki). Это достаточно общий термин, к которому, согласно той же википедии, относится и генерация исходного кода внешними инструментами, и различные препроцессоры, и «плагины к компилятору» — макросы с возможностью модификации синтаксического дерева не посредственно в процессе компиляции, и даже такая экзотическая возможность, как самомодифицирующийся код — модификация программы самой программой непосредственно во время выполнения.

Хотя, конечно, самомодифицирующийся код — это скорее отдельная большая тема, достойная отдельного исследования; здесь под метапрограммированием мы будем понимать процессы, происходящие во время компиляции программы.

Метапрограммирование реализовано в той или иной мере в очень разных языках; если не рассматривать экзотические и близкие к ним языки, то самым известным примером метапрограммирования является С++ с его системой шаблонов. Из «новых» языков можно рассмотреть D и Nim. Одна из самых удачных попыток реализации метапрограммирования — язык Nemerle. Собственно, на примере этой четверки мы и рассмотрим сабж.

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

Сегодня мы поговорим о вещественных числах. Точнее, о представлении их процессором при вычислении дробных величин. Каждый из нас сталкивался с выводом в строку чисел вида 3,4999990123 вместо 3,5 или, того хуже, огромной разницей после вычислений между результатом теоретическим и тем, что получилось в результате выполнения программного кода. Страшной тайны в этом никакой нет, и мы обсудим плюсы и минусы подхода представления чисел с плавающей точкой, рассмотрим альтернативный путь с фиксированной точкой и напишем класс числа десятичной дроби с фиксированной точностью.

Говоря о тексте, большинство программистов C++ думают о массивах кодов символов и кодировке, которой эти коды соответствуют. Наиболее опытные разработчики вообще не мыслят понятие текста без указания кодировки, наименее опытные просто считают массив байтов с кодами символов данностью и интерпретируют в понятиях кодировки операционной системы. Фундаментальная разница между этими двумя подходами не только в опыте разработчика, но и в том, что не думать о кодировке намного проще. Пора рассмотреть способ, как не заботиться о хранении кодировки, перекодировке текста, получать свободный доступ к символам и при этом видеть безошибочное представление текста вне зависимости от того, кто и где смотрит на строку текста: в Китае ли, в США или на острове Мадагаскар.

Создавая объект за объектом, мы часто не обращаем внимания на такую «мелочь», как динамическое выделение памяти. Наравне с копированием и сериализацией, выделение памяти из кучи через new постепенно сводит на нет преимущества C++ в скорости. Чем интенсивнее мы пользуемся заветным new, тем сложнее становится приложению, поскольку память кончается, фрагментируется и всячески стремится утекать. Эта участь уже постигла удобные, но неявно опасные для производительности контейнеры STL: vector, string, deque, map. Особенно обидно терять скорость на выделении небольших объектов в больших количествах. Но есть способ обработать размещение памяти таких объектов на стеке, при этом скрывая детали реализации в специальный класс данных. В этом нам поможет механизм размещающего new — непревзойденный способ оптимизации приложения, полного частых и мелких выделений памяти из кучи.

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

Итак, приступим.

Создаем хэш из массива

Проще простого. Ставим команду Hash перед любым массивом и получаем готовые пары ключ/значение:

Hash['key1', 'value1', 'key2', 'value2']

# => {"key1"=>"value1", "key2"=>"value2"}

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

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

В этой статье мы рассмотрим, как работает match в Rust. Вот основные элементы, которые match и его дополнение, enum, объединяют в единое целое:

• Структурное сопоставление с образцом: анализ вариантов и удобство использования гораздо лучше, чем при использовании switch в C или Java.
• Исчерпывающий анализ: match гарантирует, что ни один вариант не пропущен.
• match поддерживает и императивный, и функциональный стили: вы можете и дальше использовать оператор break, присваивания и прочее, и вам совершенно не нужно переучиваться на стиль, основанный на выражениях;
• match умеет как «заимствовать», так и «перемещать»: Rust поощряет программиста думать о владении и заимствовании данных. Выражение match спроектировано в том числе с возможностью только заимствования части структуры вместо её перемещения. Это нужно для того, чтобы не передать право владения какими-либо данными раньше, чем нужно.

Мы рассмотрим каждый из этих пунктов по отдельности ниже, но для начала нам следует заложить фундамент дальнейшего обсуждения — как match выглядит и работает?

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

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

В публикации рассматриваются следующие темы:

• Наследование VS компоненты
• Сложные иерархии классов юнитов, предметов и прочего
• Машины состояний, деревья поведений
• Абстракции игровых объектов
• Упрощение доступа к другим компонентам в объекте, сцене
• Сложные составные игровые объекты
• Характеристики объектов в игре
• Модификаторы (баффы/дебаффы)
• Сериализация данных

Мы продолжаем публиковать лекции Натальи Васильевой, старшего научного сотрудника HP Labs и руководителя HP Labs Russia. Наталья Сергеевна читала курс, посвящённый анализу изображений, в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS-клуба.



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

Хорошо в плане поддержки JSON живётся программистам на Javascript — по какому-то невероятному стечению обстоятельств там JSON входит в спецификацию самого языка: есть JSON — есть объект. Удобно. Неплохо дело обстоит и в языках, где JSON не входит в сам язык, но поддерживается стандартной библиотекой (Python, Ruby): импортируешь модуль — и готово.

Жизнь программистов на С++ никогда не была особо простой — поддержки JSON у нас нет ни на уровне языка, ни в стандартной библиотеке. И не будет, возможно, никогда. «Тоже мне проблему нашел!» — скажут мне опытные коллеги — «Её там и не должно быть, С++ поставляется без „батареек“. Для решения этой задачи мы...» и вот здесь они разделятся на два лагеря:

1. «Мы используем большой фреймворк (boost, Qt, POCO, другой), который применяется во всех наших проектах и умеет 150 000 разных вещей, в том числе и JSON.»
2. «Мы придерживаемся подхода в котором для каждой задачи применяется своя легковесная библиотека. В частности, для JSON мы уже 150 000 лет назад выбрали отличную библиотеку %JSON_LIB%, которая прекрасно работает.»

Да, всё так и есть. Вот только…





Давайте немного помечтаем.

А что, если бы JSON вошел в стандартную библиотеку нового стандарта С++? Что, если бы он был написан в терминах С++11\14 и без требований обратной совместимости со старыми стандартами языка? Что, если бы синтаксис этого модуля попытались бы сделать максимально приближенным к родному для JSON использованию «а-ля Javascript», но в том же время сохранить дух С++ (эффективность, минимальное потребление памяти, совместимость с STL)? Что, если бы его можно было включить в проект одним инклюдом и не беспокоиться о его сборке и линковке? Как бы это всё выглядело и работало?

И у нас есть ответ на этот вопрос! Давайте посмотрим на JSON-библиотеку для С++ написанную в соответствии со всеми этими принципами, ну и вообще написанной людьми для людей, а не чужими для хищников, как это обычно бывает.

Привздохнув, произнесла:
«Как же долго я спала!»

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

Все примеры относятся к Linux, хотя многие из них справедливы для других *nix систем, я просто взял за основу самую активно развивающуюся ОС, к тому же ту, которая у меня перед глазами и где я могу быстро проверить предлагаемый код.

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

«Пожалуйста, напишите на C++ функцию, которая получает диаметр круга как float и возвращает длину окружности как float».

Звучит как задание на первой неделе курса по C++. Но это только на первый взгляд. Сложности возникают уже на первых этапах решения задачи. Предлагаю рассмотреть несколько подходов.

Студент: Как вам такой вариант?

#include <math.h>
float CalcCircumference1(float d)
{
    return d * M_PI;
}

Преподаватель: Да, этот код может нормально откомпилироваться. А может и нет.

Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.

Мы продолжаем наши еженедельные публикации учебных материалов Технопарка. Предыдущие лекции были посвящены web-технологиям в целом, а также алгоритмам и структурам данных. В третьем блоке лекций рассказывается о языках С и С++.

Лекция 1. Язык С. Основы организации и использования оперативной и сверхоперативной памяти

Лекция начинается с введения в язык С: рассказывается об истории его появления, особенностях, преимуществах и недостатках, о сферах применения. Описываются основы препроцессорной обработки, рассматриваются вопросы управления памятью (модели управления памятью, области видимости объектов хранения) и производительность программ на языке С. Обсуждается связывание объектов хранения и их инициализация. Затем рассказывается о классах памяти в языке С. Следующая часть лекции посвящена проблематике указателей, а также работе с одномерными массивами. В заключение рассматривается стандарт POSIX и вопросы переносимости.

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