Pull to refresh
3
0.1
Сергей @gres_84

C++ Developer

Send message

Фрактальное самоподобие Вселенной и бесконечная вложенность материи – правда или миф?

Level of difficultyMedium
Reading time22 min
Views7.5K

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

Читать далее

Алгоритмы манипуляций с битами

Level of difficultyMedium
Reading time13 min
Views12K

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

Читать далее

Пишем графический ASCII-калькулятор с помощью стандартной библиотеки Си

Level of difficultyHard
Reading time17 min
Views16K

Программа calculator.c родилась как школьный проект в рамках Student Innovation Scholarship. Сперва я решил написать простой инструмент для построения графиков функций с помощью символов ASCII, но после завершения первого прототипа понял, что задача намного сложнее, чем предполагалось. Вернувшись к проекту год спустя, я увидел, что в нём есть много неочевидных нюансов. Поэтому предлагаю разобрать весь процесс разработки моего графического калькулятора с нуля.


Читать дальше →

Как уместить поиск по 30 тысячам слов в 64 КБ ОЗУ

Level of difficultyMedium
Reading time17 min
Views8.5K

Как уместить словарь размером 250 КБ в 64 КБ ОЗУ с возможностью выполнения быстрого поиска? Для справки: даже современные методики сжатия наподобие gzip -9 не могут сжать этот файл до размера меньше 85 КБ.

В 1970-х Дуглас Макилрой столкнулся с этой непростой задачей при реализации проверки правописания для Unix в AT&T. Из-за ограничений компьютера PDP-11 весь словарь должен был умещаться всего в 64 КБ ОЗУ. Кажется, подобную задачу решить невозможно.

Вместо того, чтобы использовать стандартные методики сжатия, Дуглас воспользовался преимуществами свойств данных, разработав алгоритм сжатия, отличавшийся от теоретического минимума сжатия всего на 0,03 бита. И по сей день этот рекорд остаётся непревзойдённым.

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

Читать далее

C++26 — встреча ISO в Хагенберге

Level of difficultyMedium
Reading time8 min
Views16K
В середине февраля в Хагенберге состоялась встреча международного комитета по стандартизации языка программирования C++.



В этот раз прорабатывались следующие большие темы:
  • std::hive
  • Constexpr, ещё больше constexpr
  • Безопасность, контракты, hardening, профили, UB и std::launder
  • Relocate
  • #embed

Об этом и других новинках расскажу в посте

Game++. Juggling STL algorithms

Level of difficultyEasy
Reading time29 min
Views3.5K

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

stl::vector numbers = {1, 2, 3, 4, 5};
int sum = 0;
for (int num : numbers) {
sum += num;
}

Конечно, это просто: код суммирует элементы массива. Похожую задачу про суммирование или другую операцию над массивом мой лид даёт на собесах :) Люди смотрят с удивлением, а потом большинство пишут, вот то, что было выше. И тут три вещи - человек либо поленился прочитать про STL алгоритмы, либо не доверяет нам и знает про них, но думает что не поймем мы, либо знает, но не понимает зачем показываеть эти знания, почему? вопрос оставим открытым. Этот пример с циклом - простейший алгоритм.

Алгоритмы STL — это настоящий швейцарский нож для разработчика. Они не просто помогают писать код, а делают его чище, понятнее и надежнее. В проектах с большими кодовыми базами, где легаси код не всегда стабилен и удобен для поддержки, это особенно важно. Каждый, кто писал циклы вручную, сталкивался с ошибками: вылезли за границы массива, забыли обработать пустой контейнер, сделали лишнее копирование. STL-алгоритмы избавляют от многих проблем, позволяя выразить мысли кратко и четко. Вместо простыней кода с индексами — несколько строк с понятным смыслом. Так что, если вы еще не знакомы со стандартными алгоритмами, самое время это исправить. Это один из тех инструментов, которые однажды освоив, уже невозможно забыть, это как езда на велосипеде, хорошем промышленном велике, за авторством Кнута или Саттера - надежном и с серийным номером.

Читать далее

Game++. Dancing with allocators

Level of difficultyEasy
Reading time34 min
Views9.6K

C и C++ не имеют встроенной сборки мусора, поэтому разработчик сам решает, как и когда выделять и освобождать память. Мы, конечно, можем покивать в сторону STL, сокрытия аллокаций в контейнерах, но от этого они никуда не денутся. Просто если раньше приходилось думать про выделенный кусок памяти, понимать, как он скажется на времени фрейма, помнить, что его надо удалить (а может, не надо и стоит оставить на следующий фрейм), то теперь всё заворачивается в сахарные контейнеры и разработку в стиле STL-blin-vse-sterpit. STL-то может и стерпит, и даже как-то будет ворочаться, однако не стоит полагаться исключительно на системный аллокатор, бездумно вызывая new или malloc для каждого запроса памяти. Вы ведь понимаете, что std::vector посреди цикла или горячей функции — это плохая идея?

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

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

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

Ребята из HFT, Database, Automotive и Embedded-систем наверняка могут рассказать немало интересных историй про оптимизацию new/delete. Давайте я расскажу немного про разные аллокаторы в играх?

Аллокатор аллокатору аллокации аллоцировал

Game++. Cooking vectors

Level of difficultyEasy
Reading time12 min
Views5.3K

В разработке игр динамические и статические массивы являются основным инструментом при работе с набором объектов, буду дальше называть их vector. Вы можете подумать про разные map, set, и другие ускоряющие структуры, но их тоже предпочитают делать поверх векторов. Почему так? Вектора просты для понимания, удобны для большого числа задач, особенно там, где объём данных заранее неизвестен или примерно известен. Но как вы понимаете, за все надо платить, и расплачиваться приходится производительностью, которой, как обычно, всегда не хватает. Так что, использование динамических массивов имеет свои ограничения и особенности.

Читать далее

Game++. String interning

Level of difficultyEasy
Reading time8 min
Views6.1K

«String interning», иногда это называют «пулом строк» — это оптимизация (https://en.wikipedia.org/wiki/String_interning), при которой хранится только одна копия строки, независимо от того, сколько раз программа ссылается на нее. Среди других оптимизаций по работе со строками (SWAR, SIMD-cтроки, immutable strings, StrHash, Rope string, и немного других), часть которых была описана тут, она считается одной из самых полезных оптимизаций в игровых движках, есть правда небольшие недостатки у этого подхода, но экономия памяти и скорость работы при правильной подготовке ресурсов и работе с лихвой их перекрывают.

Вы 100% когда-нибудь писали одну и ту же строку несколько раз в одной программе. Например:pcstr color = "black"; А позже в коде пришлось написать: strcmp(color, "black");Как видите, строковый литерал "black" встречается несколько раз. Означает ли это, что программа содержит две копии строки "black"? Более того, означает ли это, что в оперативную память загружаются две копии этой строки? На оба вопроса ответ — зависит от компилятора и вендора. Благодаря некоторым оптимизациям в сlang (Sony) и GCC, каждая строка-литерал хранится в программе только в одном экземпляре, и, следовательно, только одна копия загружается в оперативную память, поэтому иногда cтановятся возможными разные фокусы.

Просто не копируй это...

Game++. run, thread, run…

Level of difficultyEasy
Reading time33 min
Views4.9K

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

В обычном программировании с блокировками, когда возникает необходимость пошарить данные, приходится использовать механизмы сериализации доступа к таким данным, чтобы операции, выполняющие работу с такими данными, были ограничены от одновременного вмешательства со стороны других потоков и возможности их поломать. В прямом смысле поломать. Даже такая простая операция, как ++count, где count имеет тип integer, требует блокировки, поскольку операция инкремента в общем случае представляет собой трехшаговую операцию (чтение, модификация, запись), которая не является атомарной. Про что-то более сложное и длительное я уже и не говорю.

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

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

Читать далее

Простейшие алгоритмы сжатия: RLE и LZ77

Reading time9 min
Views145K
Давным-давно, когда я был ещё наивным школьником, мне вдруг стало жутко любопытно: а каким же волшебным образом данные в архивах занимают меньше места? Оседлав свой верный диалап, я начал бороздить просторы Интернетов в поисках ответа, и нашёл множество статей с довольно подробным изложением интересующей меня информации. Но ни одна из них тогда не показалась мне простой для понимания — листинги кода казались китайской грамотой, а попытки понять необычную терминологию и разнообразные формулы не увенчивались успехом.

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

Спинлок в современном C++ с применением атомиков, барьеров памяти и экспоненциальной выдержкой

Reading time9 min
Views3.3K
Эта статья послужит вам быстрым, но глубоким введением в низкоуровневую конкурентность.

Механизмы блокировки — важнейшая часть конкурентного программирования. Такие механизмы позволяют множественным потокам одновременно обращаться к разделяемым ресурсам, не мешая друг другу. Одна из самых популярных блокировок – это спинлок (циклическая блокировка), при которой применяется активное ожидание, механизм, позволяющий раз за разом проверять, не освободилась ли блокировка. Правда, при таком подходе будут тратиться драгоценные такты процессора, если блокировка зациклится и станет впустую потреблять ресурсы процессора. Для решения этой проблемы применяется подход под названием экспоненциальная выдержка. При экспоненциальной выдержке применяются постепенно нарастающие периоды ожидания, что позволяет не тратить ресурсы впустую.

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

inplace_vector: новый контейнер C++26

Level of difficultyMedium
Reading time5 min
Views5.2K

Вы когда-нибудь мечтали о динамически расширяемом последовательном контейнере с фиксированной емкостью, хранящем свои элементы на стеке? Комитет по стандартизации C++ исполняет желания! Теперь вам не нужно обращаться к Boost.Container за boost::container::static_vector. Встречайте, std::inplace_vector (P0843), принятый в C++26!

Читать далее

Range-v3 в C++

Reading time4 min
Views4.5K

Привет, Хабр!

В этой статье рассмотрим Range-v3 — библиотеку, которая изменила подход к обработке последовательностей в C++ и стала основой для std::ranges в C++20.

Range-v3 — это библиотека, расширяющая стандартную библиотеку C++ возможностью работать с диапазонами вместо begin()/end(). В основе идеи лежат три концепции.

Читать далее

А в чем проблема работать с файлами?

Level of difficultyMedium
Reading time53 min
Views35K

Данные - это важный компонент системы. Приложение может хранить их где угодно, но в результате все сводится к файлам. Файлы - это хорошая абстракция, но она протекает: если не знать того, как работают ОС или гарантии файловой системы, то легко выстрелить себе в ногу.

Меня увлекла тема отказоустойчивости, а конкретно - отказоустойчивой работы с файлами. В этой статье я попытался соединить все полученные знания:

Кто участвует в процессе записи

Ошибки, которые могут произойти

Что от нас зависит, а что нет

И самое главное - как это этого защититься

Читать далее

Глия: как самые неизученные клетки нервной системы меняют нейронауку

Level of difficultyHard
Reading time13 min
Views2.4K

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

Почему тема глиальных клеток очень популярна именно сейчас, какие виды глии существуют и за что они отвечают, рассказывает научный журналист и главный редактор портала «Нейроновости», член научного комитета премии «Вызов» Алексей Паевский. Специально для нас он кратко изложил историю изучения глии и поделился работами, которые меняют представления о глиальных клетках в нейронауке. Предупреждаем: будет сложно (но интересно).

Читать далее

Сборка проектов Си и Си++: от простого к сложному. Часть I. Библиотеки

Level of difficultyMedium
Reading time12 min
Views17K

Каждый раз, в течение многих лет, собирая пилотную версию мизерного проекта или простой утилиты, мне кажется, что уж в этот раз точно обойдусь обычным скриптом для сборки, и никакие сборщики проекта мне не понадобятся. Но суровая реальность приводит меня в чувство уже в течение первых нескольких минут работы. Сначала оказывается, что до невозможности простая программка нуждается в JSON-парсере, HTTP-запросах CURL и прочих библиотеках. А по мере возбуждения хотелок эти все зависимости нарастают как снежный ком. И все мечты быстро скомпилировать страничку кода встречают на каждом шаге всё новые и новые проблемы.

Вот сегодня и расскажу о том, какие бывают способы борьбы с зависимостями и сборки проекта из множества файлов на Си++. Заодно те, кто не любят Си++, смогут порадоваться «прелестям» этого процесса. И хоть тема очень важная для программистов, но я обратил внимание, что даже многолетний опыт не гарантирует понимания этих процессов. Но сразу предупреждаю — история длинная даже с учетом всех попыток не убегать на смежные темы.
Читать дальше →

Путеводитель C++ программиста по неопределённому поведению

Level of difficultyHard
Reading time3 min
Views11K

Путеводитель C\+\+\ программиста по неопределённому поведению


Вашему вниманию предлагается полный список разделов электронной книги (12 из 11 :)), посвящённой неопределённому поведению. Книга не является учебным пособием и рассчитана на тех, кто уже хорошо знаком с программированием на C++. Это своего рода путеводитель C++ программиста по неопределённому поведению, причём по самым его тайным и экзотическим местам. Автор книги — Дмитрий Свиридкин, редактор — Андрей Карпов.

Читать дальше →

Хронология зарубежной научной фантастики

Level of difficultyEasy
Reading time28 min
Views23K

Опубликованный хронологический справочник содержит зарубежные литературные произведения научной фантастики, которые литературоведы и литературные критики относят к классике жанра. Хронология охватывает период со 160 года до 1 января 2025 года.

Читать далее

Кэш. Теория кэширования. Устройство и разновидности кэша

Level of difficultyEasy
Reading time7 min
Views13K

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

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

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

Стать гуру кэша
1
23 ...

Information

Rating
3,994-th
Location
Москва, Москва и Московская обл., Россия
Date of birth
Registered
Activity