Постановка задачи

Один из алгоритмов, который я реализовывал, имел интересные особенности при работе с памятью:

• Могло выделяться огромное количество, до десятков и сотен миллионов небольших объектов одного типа.
• Объекты представляли собой POD- типы.
  
  POD

  A Plain Old Data Structure in C++ is an aggregate class that contains only PODS as members, has no user-defined destructor, no user-defined copy assignment operator, and no nonstatic members of pointer-to-member type.
• Заранее было неизвестно какое количество объектов понадобится, могло так случится, что потребуется сотня, а может и сто миллионов.
• Объекты никогда не удаляются по одному, в какой-то момент они становятся не нужны все сразу.
• Алгоритм хорошо распараллеливается, по этому выделением объектов занимается одновременно несколько потоков, по количеству ядер процессора(ов).

Использование в таких условиях стандартного new – delete приводит к очень большим потерям времени на удаление объектов. Если без отладчика удаление происходило хотя бы за несколько секунд, то в присутствии отладчика освобождение памяти замедляется примерно в 100(!) раз, и отладка проекта становится просто невозможной. Кроме того из-за большого количества выделенных объектов достаточно ощутимым становился перерасход памяти на внутренние данные распределителя памяти.
Для решения задачи выделения огромного количества объектов одного типа, и их пакетного удаления, был сделан lock-free контейнер MassAllocator. Код компилируется Visual Studio 2012. Полный код проекта выложен на github.

Преподаватель из Стэнфордского университета Кит Шварц (Keith Schwarz) уже несколько лет пополняет свой архив интересного кода — образцы самых лучших алгоритмов и структур данных, когда-либо изобретённых человечеством (Шварц весьма амбициозно оценивает свою коллекцию).

Примеры на сайте преимущественно закодированы в C++, поскольку STL предоставляет прекрасную базу для выражения алгоритмов, работающих с различными типами данных. Структуры данных реализованы на Java.

Кит Шварц дает разрешение использовать свой код всем желающим без всяких ограничений.

Сегодня вас ждет рассказ об исходном коде Doom 3 и о том, насколько он красив.
Да, красив. Позвольте мне объясниться.

Так как у меня была одна неделя до моего следующего контракта, я решил закончить мой цикл статей id. После Doom,Doom Iphone, Quake1, Quake2, Wolfenstein iPhone и Doom3, я решил изучить код, который я еще не рассматривал: idTech3 — 3D движок Quake III и Quake Live.

Часть 1: Введение.
Часть 2: Многопоточность
Часть 3: Рендеринг (Прим. пер. — в процессе перевода)
Часть 4: Doom classic — интеграция (Прим. пер. — в процессе перевода)

26 ноября 2012 ID Software выпустила исходный код Doom 3 BFG edition (всего через месяц после появления игры на прилавках магазинов). Движок idTech4, которому уже почти 10 лет, был обновлен решениями, используемыми в idTech 5 (Rage — первая игра на этом движке), и с его исходным кодом ознакомиться было очень интересно.

Я бы назвал движок «idTech4 улучшенный», т.к. по сути это idTech4, но с использованием элементов idTech5:

• Систему управления потоками (Threading system)
• Звуковую систему (Sound system)
• Систему управления ресурсами (Resources system)

Недавно заинтересовался реализацией std::string в libstdc++. Не в связи с принятием нового стандарта, а чтобы разобраться. Благо требования к строковму типу почти не изменились.

Основным средством для анализа кода несомненно является метод пристального вглядывания, но чтобы сузить область вглядывывания и сделать процедуру более захватывающей можно реализовать для строки идиому «трассер» подсмотренную в «C++ Templates: The Complete Guide». Трассировка позволяет выявлять подозрительные интересные операции над строками.

Как известно, std::string это псевдоним для

std::basic_string<char>

и нам ничего не мешает определить

std::basic_string<X>

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

std::string a(«entrails»); 

выражение

std::cout << reinterpret_cast<char*>(*((void**)(&a))); 

выведет содержимое строки. Т.е. std::string — является, по сути, указателем на char.
Вобщем, эти и другие шокирующие поднобности под катом.

Данная статья написана в форме поста для блога. Если она окажется вам интересной, то будет продолжение.

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

Общая задумка (пока весьма далёкая от реализации) следующая: единое 64-битное адресное пространство с вечно живущими нитями (как у Phantom OS); виртуальная машина, обеспечивающая безопасность исполнения кода. На данный момент реализованы:

1. загрузка ядра при помощи multiboot-загрузчика (GRUB);
2. текстовый VGA-режим (16-цветов, kprintf);
3. простой интерфейс настройки отображения страниц;
4. возможность обработки прерываний на C;
5. идентификация топологии процессоров (сокеты, ядра, потоки) и их запуск;
6. работающий прототип вытесняющего SMP-планировщика с поддержкой приоритетов;

Пропустим описание multiboot-загрузки и работы с VGA-режимом (об этом не писал, разве что, ленивый). Про отображение страниц тоже не хочу писать, боюсь это будет скучно (может, в другой раз). Давайте лучше поговорим об обработке прерываний.

Приветствую!

Некоторое время назад попалась мне статья об экспорте избранного Хабра в формат FB2.
Мне идея понравилась, но было одно 'но': необходимо было вручную запускать экспорт на локальной машине, а хотелось сразу в браузере; и во-вторых — для запуска надо было установить локально PHP и закачать исходники.

Поэтому я решил написать расширение для браузера, которое бы позволяло просто экспортить в FB2. По ходу написания добавил также экспорт в FB2 и для Самиздата.

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



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

В первой части нашей статьи мы рассказали о том, каким образом можно получить простую программу “Hello World”, которая запускается без операционной системы и печатает сообщение на экран.

В этой части статьи, хочется развить получившийся в первой части код таким образом, чтобы он мог быть отлажен через GDB, компилировался через оболочку Visual Studio и печатал на экран список PCI устройств.

! ВАЖНО!: Все дальнейшие действия могут успешно осуществляться только после успешного прохождения всех 6-ти шагов описанных в первой части статьи).

Это статья была написана для людей, которым всегда интересно знать как работают разные вещи. Для тех разработчиков которые обычно пишут свои программы на высоком уровне, C, C++ или Java — не важно, но при этом столкнулись с необходимостью сделать что-то на низком уровне. Мы будем рассматривать низкоуровневое программирование на примере работы bootloader-а.

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

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

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

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

Недавно пристально посмотрел на С++ Variadic Templates и неожиданно для себя изобрел новый RAII Scoped Resource Manager.
Получилось кратко и эффектно.

Например, с C-style выделением памяти:

// Аллоцируем ресурс в блоке.
{
    ha::scoped_resource<void*, size_t> mem(::malloc, 1, ::free);

    ::memset(mem, 65, 1);
}

На написание этого топика меня сподвиг топик "Какие кодотрюки вы знаете?", и я хотел было поделиться данным логгером там, но автор просил «без фанатизма», и желал видеть такие трюки, на понимание которых требуется не больше пяти-десяти секунд, поэтому я решил вынести это дело в отдельный топик, т.к. по-быстрому такое взглядом не окинешь.

Будет рассмотрен небольшой, но иногда довольно полезный класс, плюс небольшой трюк с макросами, позволяющие проводить первичный анализ стека вызовов (call stack) прямо в stdout, в процессе работы программы. Разумеется, на stdout свет клином не сошёлся, и можете перенаправить хоть в файл, хоть куда-нибудь ещё — я лишь демонстрирую общий принцип.

Сразу договоримся:

1. злоупотребление макросами — зло
2. ничего нового и сверхъестественного в данной статье нет, она будет понятна даже новичку (на них и рассчитана)
3. данный приём мало применим (или вообще не применим) в многопоточной среде
4. реализация не претендует на идеальность, полноту, и уж тем более уникальность
5. данный приём ни в коем случае не заменяет, а лишь дополняет дебаггер

Но если при написании программы вы не раз писали что-то вроде printf(«Entering Foo()\n»); для мониторинга входа в ту или иную функцию, то вы пришли как раз по адресу.

Прежде чем отправить в AppStore ваше приложение, вы долго тестируете его, чтобы убедиться, что ваше приложение работает безупречно. Оно отлично работает на вашем устройстве, но после того, как приложение попало в App Store, некоторые пользователи сообщают, что оно «вылетает»!

Если вы похожи на меня, то вы хотите, чтобы ваше приложение было на пять с плюсом. Значит, вы возвращаетесь в свой код, чтобы исправить сбой… а куда надо смотреть?

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

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

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву.

Под влиянием предыдущей статьи предлагаю продолжить тему создания собственной реализации такой полезной идиомы, как function в C++, и рассмотреть некоторые аспекты ее использования.

Как я уже говорил, описанному мной ранее framework-у не хватает очень многого, для того чтобы считаться полноценным игровым движком. В нем нет моделирования физики, он использует негибкий и не быстрый Iw2D для вывода графики. Фактически, все что он умеет делать — это выполнение 2D анимации спрайтов, сопровождаемое звуковыми эффектами. Чтобы как-то расти над собой, очевидно, необходимо осваивать новые возможности, но делать это, не имея какой-то цели, скучно и неинтересно.

Мы поставим перед собой цель, и разработаем небольшой прототип всем известной игры Arcanoid. Для начала, попробуем внять совету уважаемого crmMaster и попытаться разобраться с тем, что-же такое IwGl и как его можно использовать. Правда натягивать текстуры на куб мы сегодня не будем. Начинать надо с простого, и сегодня мы поучимся рисовать треугольники.

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

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

В результате стандартный консервативный аллокатор выстраивает все запросы в очередь на pthread_mutex / critical section. И наш многоядерный процессор медленно и печально едет на первой передаче.

И что с этим делать? Познакомимся поближе с деталями реализации метода Scalable Lock-Free Dynamic Memory Allocation. Maged M. Michael. IBM Thomas J. Watson Research Center.

Самый простой код что я сумел найти — написан под LGPL камрадами Scott Schneider и Christos Antonopoulos. Его и рассмотрим.