C++ *

Прочитал статьи про комбинаторную кодогенерацию на С++ в контексте линейного поиска в базе данных: Возможности оптимизации в языках C и C++ и Скорости разработки и исполнения не достижимые на С. Попробуем достигнуть скоростей разработки и исполнения на C?

После того, как я запустил компиляцию С++ кода из второй статьи, мне стало интересно — успею ли я написать аналог на С, который будет работать быстрее, пока код… компилируется? Не успел, код скомпилировался через 5 минут, а аналог на С писался все 15.

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

В первой части этой статьи основное внимание будет уделено потокам и блокировкам в С++11, условные переменные во всей своей красе будут подробно рассмотрены во второй части…

Существует мнение, что C++ имеет заметные накладные расходы по сравнению с C и поэтому он медленнее. Помимо этого, даже, существуют статьи показывающие преимущества в скорости языков с компиляцией налету (JIT — Just-in-time compilation), таких как Java и C#. Сравнить последние мы оставим тем, кто считает их быстрыми, но мы объясним почему это не так. А C и C++ мы сравним на примере задачи поиска данных.
Задача поиска данных часто встречается в: веб-сервисах, системах управления баз данных (СУБД), гео-поиске и аналитике.
Сначала для простоты объяснения поставим задачу поиска элементов полным проходом по массиву из 10 000 000 элементов (структур), содержащих 5 полей с диапазонами значений: amount_of_money(0-1000000), gender(0-1), age(0-100), code(0-1000000), height(0-300). А в следующих статьях добавим в решение индексный поиск.
Мы будем писать кроссплатформенно под MSVC11(MSVS2012) и GCC 4.7.2, и использовать в них частично реализованный стандарт C++11.

В продолжении статьи о кроссплатформенной и кросс-аппаратной оптимизации, на примере задачи поиска полным проходом по таблице из 5 полей и 10 000 000 строк, и неизбежности этой задачи даже при индексном поиске, я покажу как ускорить такой поиск в 3.5-5.3 раза с использованием C++ независимо от аппаратной платформы.
В предыдущей статье нам удалось ускорить поиск в 1.3 раза: GitHub.com
Мы не будем банально описывать конструкции языка, а покажем преимущества C++ при решении одного из этапов реальной задачи.
Мы по-прежнему пишем кроссплатформенно под MSVC11(MSVS2012) и GCC 4.7.2, и используем в них C и частично реализованный стандарт C++11.
Для упрощения понимания мы все ещё пишем без индексного поиска, но это решение в дальнейшем будет использоваться при индексном поиске.

На мой взгляд Qt Graphics Scene FrameWork — мощный инструмент, незаслуженно обделенный вниманием на Хабре. Я попытаюсь исправить ситуацию, посвятив ему цикл статей. И в этой, пилотной, статье покажу как можно программировать с помощью этого замечательного фреймворка на примере более-менее реальной задачи.

Перевод статьи Аллана О’Доннелла Learning C with GDB.

Исходя из особенностей таких высокоуровневых языков, как Ruby, Scheme или Haskell, изучение C может быть сложной задачей. В придачу к преодолению таких низкоуровневых особенностей C, как ручное управление памятью и указатели, вы еще должны обходиться без REPL. Как только Вы привыкнете к исследовательскому программированию в REPL, иметь дело с циклом написал-скомпилировал-запустил будет для Вас небольшим разочарованием.

Недавно мне пришло в голову, что я мог бы использовать GDB как псевдо-REPL для C. Я поэкспериментировал, используя GDB как инструмент для изучения языка, а не просто для отладки, и оказалось, что это очень весело.

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

Движок для Doom III был написан в период с 2000 по 2004 год, в то время, когда большинство ПК были однопроцессорными. Хотя архитектура движка idTech4 разрабатывалась с учетом поддержки SMP, это закончилось тем, что поддержка многопоточности делалась в последнюю минуту (см. интревью с Джоном Кармаком).

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

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

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

30 мая вышел Qt Creator 2.8 beta, в котором реализовано много новых функций и исправлено большое количество ошибок.

Все нововведения и исправления в одном посте уместить будет весьма трудновато, поэтому попытаюсь выделить только несколько основных моментов.

Часть 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)

Введение

После продолжительного перерыва мне пришлось вернуться к программированию на C++. После C# очень не хватало ключевого слова var и возможностей построения запросов linq. Однако как оказалось прогресс не стоит на месте и за время моего отсутствия вышла новая версия С++11, имеющая новые интересные возможности, к тому же реализованная в большинстве компиляторов. Я занимался кросс-платформенным проектом и меня интересовали компиляторы GCC для Linux, Visual Studio и mingw для мира Windows. Попытка найти linq-like библиотеку не увенчались успехом, все, что я находил, было нежизнеспособной поделкой на коленке. Смирившись, я бросил поиски, однако в апреле 2012 вышла обнадеживающая статья LINQ to Objects на языке C++, в которой описывалась библиотека, которая мне подходила. Попробовав ее в деле и разобравшись в ее устройстве, я был разочарован неэффективностью, но некоторые идеи я подчерпнул. Оставалось одно – написать такую же, только с блэк-джеком, что я и сделал github.com/drbasic/CppLinq, заодно разобравшись автоматическим выводом типа (auto) и лямбда выражениями.

Проектировалась библиотека так, что бы с помощью fluent-синтаксиса и лямбда выражений пользователь мог построить граф преобразований. Эти графы можно копировать, достраивать, объединять, т.е. реализовать поведение максимально близкое к прообразу Linq to Objects из мира C#. Функционал библиотеки, недолго думая, я позаимствовал из C#, добавив, явный left join и full join. Важным ограничением библиотеки является перемещение по графу преобразования не копий, а указателей на элементы исходной последовательности. Это позволяет эффективно обходиться со сложными элементами коллекций, ведь теперь не происходит накладных расходов на копирование, но исходная последовательность из-за этого не должна быть «виртуальной». Т.е. к началу работы у каждого элемента исходной последовательности должен быть уникальный адрес и элементы не должны перемещаться в памяти во время работы linq-преобразований. В общем, для этого подходят массивы, контейнеры Qt, все стандартные контейнеры, кроме std::bitset. Сложности возникли лишь с константными последовательностями, которые так и не доделал, так как мне они были не особо нужны. Библиотека проверена и успешно компилируется Visual Studio 2010 и 2012, gcc 4.8, mingw 4.8. Проще всего совладать оказалось с компилятором Microsoft, сделать счастливыми gcc было куда сложнее, причем с внутренней ошибкой бывало падали все компиляторы, порой даже без вразумительных криков.

Профильная оптимизация это очень интересный способ оптимизации кода приложения в среде выполнения (в команде разработчиков Visual C этот метод называют POGO или PGO, от английского Profile Guided Optimization). Впервые профильная оптимизация была применена в конце 90-х исследовательскими группами в Visual C и Microsoft. Тогда она была рассчитана для архитектуры Itanium. Затем PGO была включена в состав Visual Studio C/C++ 2005. На сегодня это основной процесс оптимизации, значительно повышающий производительность приложений Microsoft и других разработчиков.
В этом посте будет рассказано, как создавать более быстрые и высокопроизводительные нативные приложения. Для начала, познакомимся ближе с PGO, а затем рассмотрим на примере (симуляция NBody), как с помощью нескольких простых шагов можно применить этот процесс оптимизации в ваших приложениях. Для работы используйте исходный код из примера. Для сборки проекта вам понадобится DirectX SDK.

По мотивам одного вчерашнего поста про оптимизацию условных переходов при расчете x=sign(a,b)*min(abs(a), abs(b)) якобы в 10 раз. Краткая сводка:

• оптимизация налицо, но размер мнимый: не в 10 раз, а 2.5 раза;
• бенчмарки надо делать правильно: не надо мерить CPU stalls, RAM bandwidth итп вместо исследуемой функции;
• бенчмарки надо делать правильно: иначе могут дико дрожать;
• выставлять только приоритет прикольно, но на коротких бенчмарках зря: +0.5% скорости, -15% дрожания;
• нужно мерить исследуемую функцию и только ее, только так получаешь корректные данные;
• нужно греть проц, нужно считать минимум из N прогонов/секунд, только так побеждаешь дрожание;
• нужно пользовать SSE, с ним получилось 8.6 раз, причем код… читается.

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

При оптимизации времени выполнения алгоритма, использующего LDPC декодер, профайлер привел к функции, вычисляющей следующее значение:

где a и b — целые числа. Количество вызовов шло на миллионы, а реализация ее была достаточно

Мы проверили заголовочные файлы, входящие в состав Embarcadero C++Builder XE3. Фактически, это означает только проверку небольшого числа inline-функций. Соответственно найдено совсем немного подозрительных мест, но достаточно для небольшой заметки.

Недавно заинтересовался инстанцированием плюсовых шаблонов. В интернетах втречается термин code bloat. Для с++ это может означать неконтроллируемое увеличение кода генерируемого компилятором. Код увеличивается за счет того что инстанцирование новой функции имеет более высокий приоритет чем преобразование аргументов к более удобному типу. Т.е. template T foo(T a); для int и char — это две разные функции. Получить одну функцию можно либо отказом от шаблонов, либо использованием явного преобразования типов.
Но давайте вывернем проблему наизнанку и попробуем получить из минимума строк кода исполняемый файл максимально возможного размера.
Результат не очень впечатил — у меня получилось всего 53Mb из 60 строк кода. И то лишь для одного из трех опробованных компиляторов и ценой нескольких часов компиляции. Максимальное отношение объем/строки — 2.3МБ/строку для объема 14МБ.
Как и почему так получилось — под катом.

Приглашаю Си/Си++ программистов присоединиться к блогу PVS-Studio. Вы узнаете о разных интересных вещах из мира Си/Си++ и о том, кто, где и как программирует. Расскажу немного о том, что не было опубликовано на Хабре за время нашего отсутствия здесь.

В жизни любой достаточно большой программы наступает момент, когда нужно вывести наружу какой-нибудь API — для плагинов, для интеграции с другими системами, для автоматизации и т.д. Для этого есть много разных технологий, но как-то так исторически сложилось, что сейчас принято делать API в виде REST-сервисов. В принципе, если не гнаться за экономией каждого байта и микросекунды, то в этом есть смысл: HTTP-запрос сделать легко из любого языка, это хорошо работает и локально, и по сети, не нужно сильно глубоко погружаться в недры сетевых протоколов.
Давайте посмотрим, как к уже существующей программе на C++ можно быстренько прикрутить Web API, используя для этого библиотеку POCO.

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

В этом посте мы обсудим решение нескольких задачек, которые я подсмотрел из «Марафон задач по С++» (мне кажется ссылки легко найдутся поисковиком). Нет, к сайту я решительно никакого отношения не имею, однако узнал о нем с хабра: либо был у кого-то в профиле, либо была ссылка в комментариях, правда сомневаюсь, что это помешает последователям локальной теории заговора с легкостью минусовать топик. Выдохнул… Итак, определимся с задачками, решения которых будут рассматриваться (задачек всего 9, но эти показались мне интересными):

• Забыл, как умножать. Помогите!
  Умножить число на 7, не используя операцию умножения.
  
• Два в одном.
  Какой-то умник поменял местами кнопки в лифте. Поставил вместо первого этажа второй, а вместо второго – первый. Честное слово, мне лень ковырять кнопки. Я лучше перепрограммирую лифт. Но программировать мне тоже лень. На вас вся надежда. Напишите, пожалуйста, функцию-переключатель, которая возвращает 1, если на входе 2 и 2, если на входе 1.
  

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