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

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

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

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

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

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

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

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

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

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

Привет! Сегодня мы выложили в опенсорс Perforator — систему непрерывного профилирования (continuous profiling), которую используем внутри Яндекса для анализа производительности большинства сервисов.

В Github-репозитории доступен исходный код системы и инфраструктура для развёртывания своей инсталляции Perforator на кластере Kubernetes. Кроме того, Perforator можно использовать на своём компьютере как более простую замену perf record: профили получаются точнее, а оверхед меньше. Исходный код доступен под лицензией MIT (и GPL для eBPF-программ) и запускается под x86-64 Linux.

При помощи Perforator и прошлых подходов к задаче профилирования мы регулярно оптимизируем самые крупные сервисы в Яндексе, например Баннерную крутилку или Поиск, на десятки процентов. Кроме того, Perforator реализует недостающий в опенсорсе компонент профилирования для простой автоматической оптимизации программ с использованием profile-guided optimization. Наши тесты показывают, что использование PGO даёт ускорение около 10% в разных сценариях.

Под катом поговорим про профилирование под Linux, опишем вызовы и сложности, возникающие при профилировании, изучим, как устроен Perforator внутри, и обсудим, как можно использовать полученную систему.

Несколько лет назад я подумал, что эра Xbox 360 прошла, исследования забиыты, и потихоньку начал избавляться от наследия студенческих времён - приставки продал, запчасти раздал, на форумы залезать перестал. Но у вселенной были совершенно другие планы, стоившие мне нескольких месяцев бессонных ночей…

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

Я хочу, чтобы вы задали себе один вопрос и честно на него ответили. Когда в последний раз вы получали настоящее удовольствие от программирования? Оглядываясь назад, я понимаю, что не испытывал подобных ощущений, наверное… уже лет десять. Удовольствия у меня не было ни от JavaScript, ни от Python, ни от Ruby или C — ни от чего. Когда я говорю «удовольствие» — я имею в виду ощущения человека, которого во время работы над неким проектом переполняет искренний восторг. Этот человек постоянно ловит себя на такой мысли: «Ох, ну какая ж круть. Поверить не могу, что моя безумная идея и правда сработала!».

Например, я писал маленькую игру-«рогалик». У меня была такая идея: «Готов поспорить, что у меня получиться воспользоваться этим вашим алгоритмом Дейкстры для соединения комнат при генерировании карты, сначала инвертируя карту, а потом его запуская. Вероятно, мне удастся прокопать отличнейшие туннели между комнатами». То было благословенное время, когда я пытался справиться с этой задачей, и при этом не чувствовал, что C++ мне мешает. Мне тогда удалось решить эту задачу, попутно многому научившись. Потом у меня появилась такая мысль: «Интересно, получится мне взять пользовательский интерфейс, сделанный на FTXUI, и просто напрямую его отрендерить в окно визуализации SFML?». Как и следовало ожидать, у меня всё отлично получилось. И хотя это было не так уж и сложно, я по ходу дела много узнал о том, как в C++ обрабатывается юникод. Ни одна из этих задач лёгкой не была, но все их, в принципе, можно было решить, и я не могу напридумывать себе достаточно много «подводных камней», которыми C++ мог бы помешать мне сделать то, что я хочу. Это — то, что я называю «удовольствием».

Моя текущая позиция и аутсорсы последних пяти лет на 90% были в западных gamedev студиях, соответственно и общение было преимущественно с не‑ру коллегами. А когда надолго отрываешься от славянских коллективов разработки, то отличия начинают проявляться очень четко, начиная от модели управления командой и заканчивая культурой разработки. Хотя вот культурой я бы это не назвал, скорее плясками варваров‑полуиндусов на останках штатовской империи софтостроения. Индийцы тут ни при чем, а вот практики и сам процесс написания кода очень попахивает этими жителями полумифической страны Индустана. Есть немало книг по истории развития игровой индустрии и истории успехов и провалов разных студий, в основном западных, оставлю в статье список самых интересных и захватывающих, если решите углубиться в историю (кому интересно, будет под спойлером).

Одна из последних — «Not All Fairy Tales Have Happy Endings» (Ken Williams), мемуары одного из основателей Sierra On‑Line, прочитана была около года назад и понравилась больше других, наверное потому, что читая книгу — я, наконец, понимал большинство решений и причин которые привели к тому или иному результату. Этого понимания точно не было десять лет назад, это сложно объяснить, если не работал непосредственно сам долгое время с людьми с иным образом мыслей, культурным кодом, как сейчас принято говорить. Нынешняя команда на 95% франко‑испано‑английская — австралийцы, немного европейцев и американцы. В студии по‑русски говорят трое, включая меня. До этого в карьере были по большей части все же ру‑студии с привычным менталитетом, пускай и под управлением все тех же американцев, но менеджмент скрадывал все огрехи и брал «разговоры как надо» на себя, а нам доставались только технические задачи, грамоты и иногда премии. Десять лет назад, придя в индустрию создания игр, я не задавался вопросом — чем отличаются мои таски, мой код, мои идеи от тасок, кода и идей Джона из Кемпбеловки под Сан‑Хосе, потому что вокруг были все «свои». Сейчас уже тоже все «свои», но те «свои», от этих «своих» отличаются примерно — всем.

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

В текущей версии TS (5.7) нет нативного расширения типов.

Расширение в TS реализуют интерфейсы через ключевое слово extend, причем интерфейсы могут быть расширены только от одного объекта.

Хотя для типов (type/interface) предусмотрена операция интерсекции (&), которая объединяет свойства двух или более типов - она обладает важным ограничивающим свойством - при наличии одинаковых свойств, операция интерсекции присваивает их результирующему типу значение never.

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

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

Так делает imgui, равно как и все, кто использует stb_truetype. Сам процесс приятно напоминает процесс наборного производства на физических станках.

Причудливо, правильно, но в то же время напряжно.

Если нам нужно просто вывести какое‑то сообщение для дебага? Нет ли какого‑либо более простого метода?

В данной статье я опишу метод бестекстурной отрисовки дебаг‑текста. Вдобавок, отрисовка будет производиться в один вызов draw.

В предыдущей статье (ч.1, ч.2) я рассказывал как построить свою полностью открытую вычислительную систему на опенсорсных решениях — некую синтезируемую систему-на-кристалле, которая будет адаптирована под ваши задачи, в которой всё до последнего триггера находится под вашим управлением и не зависит ни от рыночной конъюнктуры, ни от политических решений. В этой статье я расскажу и покажу как добавить к этой СнК простейший видеоадаптер под тип старого доброго Color Graphics Adapter (CGA), но с современным (HDMI) интерфейсом, с графическим и текстовым режимами и аппаратным скроллингом для плавной прокрутки изображений. Как и в предыдущей статье, речь пойдет о проектировании аппаратуры на языке SpinalHDL и синтезе её для микросхем ПЛИС, используя опенсорсный тул. Все эксперименты я буду проводить на плате «Карно» с ПЛИС Lattice серии ECP5, но весь мой код, за исключением части касающейся настроек PLL, будет аппаратно независимым и легко адаптируемым под любой тип микросхем ПЛИС из поддерживаемых тулчейном Yosys/NextPNR.

Здравствуйте, дорогие читатели!

Меня зовут Алексей Карпенко. Проработав в разработке игр больше 5 лет, разрабатывая экономику и баланс для проектов, принесших более 150M$+ выручки, я решил подытожить все свои знания в экономике, балансировке и монетизации игр в одну работу, и поделиться с другими разработчиками.

Материалов в данной сфере совсем немного, на момент написания статьи осень 2024 года, всего +-20 научных статей и пару книг, одна из которых 800 страничный фолиант от Brenda Romero and Ian Schreiber. Я собрал всю эту информацию в одной статье, а также добавил свои знания и опыт, поэтому я считаю что мои знания будут полезны для вас.

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

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

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

Приятного чтения! 😊

Хотя алгоритмы определения простоты числа известны с древних времён, полиномиального алгоритма долгое время известно не было. То есть было неизвестно, принадлежит ли эта задача классу сложности P. В 2002 году индийскими математиками Агравалом, Кайялом и Саксеной был впервые предложен полиномиальный алгоритм проверки простоты чисел, поставивший точку в этом вопросе.

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

Мы рассмотрим несколько примитивных настроек Linux, которые могут повысить производительность NVMe SSD дисков в разы. Под катом много интересных подробностей, так что скучно не будет.

В этом посте разобраны некоторые фокусы, причуды и фичи языка C (некоторые из них – весьма фундаментальные!), которые, казалось бы, могут сбить с толку даже опытного разработчика. Поэтому я потрудился сделать за вас грязную работу и (в произвольном порядке) собрал некоторые из них в этом посте. Примеры сопровождаются ещё более вольными краткими пояснениями и/или листингами (некоторые из них цитируются).

Конечно же, здесь я не берусь перечислять абсолютно всё, так как факты из разряда «функция nan() не может устанавливать errno, поскольку в определённых ситуациях поведёт себя как strtod()» не слишком интересны.

ВНИМАНИЕ: сам факт попадания тех или иных вещей в эту подборку  не означает автоматически, что я рекомендую или, наоборот, не рекомендую ими пользоваться! Некоторые из приведённых примеров никогда не должны просачиваться за пределы списков наподобие этого, тогда как другие примеры невероятно полезны! Уверен, что могу положиться на ваш здравый смысл, дорогие читатели.

В чём состоит проблема​

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

Этот API настолько невероятен, что я, наверно, посвящу несколько постов описанию его основных возможностей. Однако в первом посте я расскажу об одном из его главных преимуществ: у нас наконец появился нативный объект, описывающий Zoned Date Time.

Но что же такое Zoned Date Time?

Вы когда-нибудь задумывались, что происходит, когда вы нажимаете кнопку питания на компьютере? За той краткой паузой, прежде чем экран загорится, скрывается сложный процесс. В этой статье мы погрузимся в увлекательный мир прошивок (firmware) и исследуем, как разные компоненты взаимодействуют во время загрузки системы. Поняв эти связи, вы получите четкое представление о том, как основные элементы приводят вашу систему в действие. Мы сосредоточимся на Intel архитектуре x86, хотя многие принципы применимы и к другим архитектурам.

Всем привет. Сегодня я хочу рассказать об использовании WASM с C++ и разберу, как взаимодействовать с этим всем делом через JavaScript.

Материал предназначен для новичков в данной теме.