Что влияет на скорость работы программ на C++ и как её добиться при высоком уровне кода? Ведущий разработчик библиотеки CatBoost Евгений Петров ответил на эти вопросы на примерах и иллюстрациях из опыта работы над CatBoost для x86_64.


— Всем привет. Я занимаюсь оптимизацией для CPU библиотеки машинного обучения CatBoost. Основная часть нашей библиотеки написана на C++. Сегодня расскажу, какими простыми способами мы добиваемся скорости.

Привет! Я время от времени рассказываю на Хабре о решениях распространённых задач на C++ и вообще люблю делиться опытом. Поэтому даже написал целую книгу, которая называется «Разработка приложений на С++ с использованием Boost». Она может быть интересна разработчикам, которые уже немного знакомы со стандартной библиотекой языка, хотят глубже изучить Boost, упростить и повысить качество разработки приложений. Уверен, что информация, которую я собрал в книге, будет полезна — всё больше библиотек Boost становятся частью стандарта. Сегодня предлагаю прочитать главу, посвящённую работе с файлами. В ней я рассказываю о перечислении файлов в каталоге, стирании и создании файлов и каталогов, а также о самом быстром способе чтения. Надеюсь, будет интересно. И, пожалуйста, не забывайте делиться впечатлениями в комментариях.

UPD: добавил в конец поста бонус для читателей Хабра.

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

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

В этой статье я расскажу как написать свою реализацию известной игрушки Сокобан, а также алгоритм для её решения с нуля. Заодно применю на практике некоторые шаблоны проектирования и принципы SOLID.

Весь код расположен по адресу

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

История компьютерных наук в целом сводится к тому, что учёные пытаются понять, как работает человеческий мозг, и воссоздать нечто аналогичное по своим возможностям. Как именно учёные его исследуют? Представим, что в XXI веке на Землю прилетают инопланетяне, никогда не видевшие привычных нам компьютеров, и пытаются исследовать устройство такого компьютера. Скорее всего, они начнут с измерения напряжений на проводниках, и обнаружат, что данные передаются в двоичном виде: точное значение напряжения не важно, важно только его наличие либо отсутствие. Затем, возможно, они поймут, что все электронные схемы составлены из одинаковых «логических вентилей», у которых есть вход и выход, и сигнал внутри схемы всегда передаётся в одном направлении. Если инопланетяне достаточно сообразительные, то они смогут разобраться, как работают комбинационные схемы — одних их достаточно, чтобы построить сравнительно сложные вычислительные устройства. Может быть, инопланетяне разгадают роль тактового сигнала и обратной связи; но вряд ли они смогут, изучая современный процессор, распознать в нём фон-неймановскую архитектуру с общей памятью, счётчиком команд, набором регистров и т.п. Дело в том, что по итогам сорока лет погони за производительностью в процессорах появилась целая иерархия «памятей» с хитроумными протоколами синхронизации между ними; несколько параллельных конвейеров, снабжённых предсказателями переходов, так что понятие «счётчика команд» фактически теряет смысл; с каждой командой связано собственное содержимое регистров, и т.д. Для реализации микропроцессора достаточно нескольких тысяч транзисторов; чтобы его производительность достигла привычного нам уровня, требуются сотни миллионов. Смысл этого примера в том, что для ответа на вопрос «как работает компьютер?» не нужно разбираться в работе сотен миллионов транзисторов: они лишь заслоняют собой простую идею, лежащую в основе архитектуры наших ЭВМ.

Моделирование нейронов

Кора человеческого мозга состоит из порядка ста миллиардов нейронов. Исторически сложилось так, что учёные, исследующие работу мозга, пытались охватить своей теорией всю эту колоссальную конструкцию. Строение мозга описано иерархически: кора состоит из долей, доли — из «гиперколонок», те — из «миниколонок»… Миниколонка состоит из примерно сотни отдельных нейронов.



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

У каждого компьютера есть ОЗУ, встроенное в процессор или находящееся на отдельной подключенной к системе плате — вычислительные устройства просто не смогли бы работать без оперативной памяти. ОЗУ — потрясающий образец прецизионного проектирования, однако несмотря на тонкость процессов изготовления, память ежегодно производится в огромных объёмах. В ней миллиарды транзисторов, но она потребляет только считанные ватты мощности. Учитывая большую важность памяти, стоит написать толковый анализ её анатомии.

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

Зачем же ты, RAM-ео?

Процессорам требуется очень быстро получать доступ к данным и командам, чтобы программы выполнялись мгновенно. Кроме того, им нужно, чтобы при произвольных или неожиданных запросах не очень страдала скорость. Именно поэтому для компьютера так важно ОЗУ (RAM, сокращение от random-access memory — память с произвольным доступом).

Существует два основных типа RAM: статическая и динамическая, или сокращённо SRAM и DRAM.

Мы будем рассматривать только DRAM, потому что SRAM используется только внутри процессоров, таких как CPU или GPU. Так где же находится DRAM в наших компьютерах и как она работает?

Профессор Никлаус Вирт был прав. Создатель языка Pascal, соавтор технологии структурного программирования, лауреат премии Тьюринга в 1995 году заметил:

«Замедление программ происходит куда быстрее, чем ускорение компьютеров»

С тех пор это высказывание считается законом Вирта. Он фактически нивелирует закон Мура, согласно которому количество транзисторов в процессорах удваивается примерно с 1965 года. Вот что пишет Вирт в статье «Призыв к стройному софту»:

«Около 25 лет назад интерактивный текстовый редактор умещался всего в 8000 байт, а компилятор в 32 килобайта, тогда как их современные потомки требуют мегабайтов. Стало ли всё это раздутое программное обеспечение быстрее? Нет, совсем наоборот. Если бы не в тысячу раз более быстрое железо, то современное программное обеспечение было бы совершенно непригодным».

С этим трудно не согласиться.

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

Как можно понять, это достаточно серьёзная проблема: я разработчик ПО, и вся моя карьера зависит от возможности пользования клавиатурой!

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

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

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

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

Поэтому я согласился на работу. И это была просто отдушина после того, что я пережил в бэкенд разработке.

Как разработчику научного ПО мне приходится много программировать. И большинство людей из других научных областей склонны думать, что программирование — это «просто» набросать код и запустить его. У меня хорошие рабочие отношения со многими коллегами, в том числе из других стран… Физика, климатология, биология и т. д. Но когда дело доходит до разработки ПО, то складывается отчётливое впечатление, что они думают: «Эй, что тут может быть сложного?! Мы просто записываем несколько инструкций о том, что должен сделать компьютер, нажимаем кнопку „Выполнить” и готово — получаем ответ!»

Проблема в том, что невероятно легко написать инструкции, которые означают не то, что вы думаете. Например, программа может совершенно не поддаваться интерпретации компьютером. Кроме того, нет буквально никакого способа определить, завершится ли программа вообще, не выполнив её. И есть много, очень много способов сильно замедлить выполнение программы. В смысле… реально замедлить. Так замедлить, что выполнение займёт всю вашу жизнь или больше. Это чаще всего происходит с программами, которые написаны людьми без компьютерного образования, то есть учёными из других областей. Моя работа — исправлять такие программы.

Люди не понимают, что информатика учит вас теории вычислений, сложности алгоритмов, вычислимости (то есть можем ли мы действительно что-то вычислить? Слишком часто мы считаем само собой разумеющимся, что можем!) Информатика даёт знания, логику и методы анализа, помогающие написать код, который выполнится за минимальное количество времени или с минимальным использованием ресурсов.

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

Доброго времени суток!

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