#story

Как проходит отбор к межнару по информатике 🚬

Я подумал, о чем бы написать в канал, чтобы он не пустовал, и решил, что эта тема сойдет 😁 Про C++ тоже будет.

🅰️🅰️🅰️🅰️🅰️🫥1️⃣
Калибровка Dota MMR рейтинга Codeforces
Однажды я как обычно отсиживал время в своей школе, и кто-то сказал что бывают некие "олимпиады", с помощью которых можно поступить в любой вуз без экзаменов, но это не точно 👦

Я был не уверен, что мне особо нужен "топовый" (будто бы) вуз, что я вывезу если там сложно учиться и так далее 🚬 Но идти в рандомный ПТУ из-за слитых экзаменов тоже не хотелось.
Отнесся скептически, слово "олимпиады" ассоциировались со скучным занятием для ботанов 🤓 Стало просто интересно, за что дают ход в любой вуз.

Узнал, что в этом олимпиаде есть несколько этапов (школа/город/область/финал). Открыл Codeforces, который в интернете советовали для подготовки. Порешал там что-то (🔍 первый день).

Спустя какое-то время пару раз поучаствовал на Codeforces в "раундах" (их правила), по их результатам перерасчитывается твой рейтинг.

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

Прикол в том, что Codeforces превращает решение обычных алгоритмических задач в рейтинговую игру 🎮

В стандартном раунде дается 5 задач на 2 часа.
В самом начале задачи стоят 500-1000-1500-2000-2500 баллов, они отсортированы по сложности: первую решают почти все, последнюю единицы (из многих тысяч участников) ⌨️ Чем позже решишь задачу, тем меньше баллов она будет стоить, за неудачную попытку от задачи отнимается 50 баллов.

Во время раунда отосланное решение задачи проверяется на "претестах", то есть каком-то наборе из ~10-15 тестов, и только после раунда на всех ~100-150 тестах. Это значит, что статус "претесты пройдены" не означает полного решения и задача может упасть во время полного тестирования 🚬 Если кажется, что решение было неправильным, то можно в течение раунда перепослать решение, тогда от задачи также отнимается 50 баллов.

Если 100% кажется, что твое решение правильное, можно "заблокировать" задачу - тогда больше нельзя перепосылать решение, зато можно смотреть решения этой же задачи у других участников в твоей "комнате" (рандомные ~50 участников раунда) и попытаться "взломать" их решения ⌨️ То есть подбирать такой тестовый кейс, на котором чужое решение работает неправильно. Успешный взлом +100 баллов, неуспешный -50 баллов.

Это всё и еще ряд правил делают каждый раунд непохожим друг на друга. Есть несколько стратегий по разгрому раунда, самые необычные/сложные такие:
1️⃣ "Стальные Яйца" - первым делом решать 3-ю или 4-ю задачу. Так как более "весомые" задачи теряют больше баллов со временем, то выгоднее решать их быстрее всего (в разумных пределах) и потом уже 1-ю и 2-ю.
Это самый рискованный путь, и если задачу решить не удастся, то урон рейтингу будет мощным.
2️⃣ "Крутой Какер" - после решения первых задач (сколько можешь - 2 или 3) не пытаться решать оставшиеся, а "заблокировать" решения и бросить все силы на "взлом" чужих решений. Для этого усиленно ищутся крайние случаи и прокачивается навык скорочтения говнокода.
Можно пойти на такую хитрость - так как многие другие участники изредка мониторят "комнату" и сразу же блокируют свои решения после первых взломов (далеко не все задачи "взломабельные") и тоже пытаются ломать кого-то, лучше не ломать никого сразу, а накопить список лохов и потом грохнуть сразу пятерых и получить +500 баллов 👊
(Самые жесткие вариации стратегии дополнительно предполагают засылку хренового решения по сложной задаче, лишь бы пройти претесты, а потом прочитать чье-то нормальное решение в комнате и также ломать)

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

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ

#retro #story

Обзор Sega Mega Drive 🏃

16-битная приставка Sega Mega Drive появилась у меня в середине 00-х. Я переиграл во многие игры, потому что на городском рынке можно было брать напрокат картриджи на неделю за 15 рублей 🏃‍♂️
Хотя тогда было уже поздно для таких приставок, в провинции время идет с отставанием (обыграно в "Жмурках", снятом в то время), я помню даже оранжевые картриджи для совсем отсталой 8-битной Dendy на том же рынке 🎮

Mega Drive породил новый культурный пласт и сподвиг людей на такие увлечения:
1️⃣ Sonic 😈 - вырос из игры 1991 года, которая выжала максимум из тогдашнего железа (обзор только физики значителен).
После успеха оригинальной игры вышло овер 9000 других игр про Соника, мультфильмов, комиксов и прочего хлама для школьников.
Известный деятель sndk также вырос на нем - даже пробовал сделать свою игру, и в параллельной вселенной он стал бы обычным программистом, но куда лучше у него получалась треш-озвучка, что стало его карьерой.
Даже профессиональные издатели игр выпускали закосы под Соника 🦔
2️⃣ PixelArt 😊 - старые игры были вынуждены иметь пиксельную графику, но с эволюцией железа это почти сразу стало андеграундом. До сих пор живы ценители такого стиля.
В этой сфере популярно рисовать со всякими ограничениями, например "не больше 8 цветов на картинку".
3️⃣ RetroGaming 🎮 - любовь к старому железу и играм, анализ их архитектур и так далее. Играть можно на эмуляторах, хотя есть ценители которые приобретают старые оригинальные девайсы.
У некоторых приставок (у той же Mega Drive) есть новодельные реплики, можно их купить на алиэкспресс 😁
Еще, например, есть дистрибутив Raspberry Pi специально под ретро, и у всех версий RaspPi есть композитный видеовыход, способный работать со старыми телевизорами, что нужно для аутентичности.
4️⃣ Reversing ⚙️ - реверс и изменение старых игр.
Изменение старых игр называется "ромхакинг", про это тоже есть куча ресурсов.
Есть деятели, которые проводят лютые стримы по ромхакингу.
Есть даже ежегодный конкурс на лучший ромхак Соника.
5️⃣ Sega - отдельные ценители следят именно за компанией Sega, например выкладывают на форумах всякие найденные сомнительной ценности материалы, наподобии "финансовый отчет Sega за 1986 год" 😁 Это показывает, насколько приставка повлияла на культуру, что даже такие увлечения есть.

Архитектура Mega Drive выглядит так 🔍, то есть состоит из нескольких главных кусков:

1️⃣ Motorola 68000 - главный процессор, о нем писал тут. Игры программировались на его ассемблере.
Любое обращение к памяти в ассемблере выполнялось шиной (на картинке 68000 bus), которая преобразовывала адреса в разные места: ROM картриджа (объем 4Mb), RAM процессора (объем 64Kb), контрольные порты и так далее, подробнее описано тут.
В общем, больше сказать нечего 😁 Это обычный процессор для игровой логики, достаточно дешевый и популярный на момент создания Mega Drive.

2️⃣ VDP (Video Display Processor) - асик разработки самой Sega, чип видеоконтроллера. Полностью про его работу описано на этом крутейшем сайте (это лучшее, что я читал технического за год), ниже будет пересказ 😉
Этот процессор работает так - у него 24 регистра, которые отвечают за всякую хреновню, а также 64Kb собственного RAM (называется VRAM - Video RAM), куда нужно совать информацию о графике.
Данные во VRAM засовывает процессор 68000 (он же может менять регистры), и VDP просто отрисовывает на телевизор картинку согласно присланным данным и всё, больше ничего не делает.

В VDP достаточно навороченная система со цветами.
В любой момент времени активно 4 палитры, в каждой палитре находится 16 цветов, каждый цвет занимает 9 бит (то есть по 3 бита на R/G/B, суммарно доступно 512 уникальных цветов).
Первый цвет палитры всегда прозрачный, то есть по факту в палитре доступно 15 цветов плюс "прозрачность".

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ

#compiler

На фото типичная задняя обложка журнала или тетради в нулевые годы. Сейчас такого не увидишь (закон не позволяет или устарело?), но в то время я выбирал тетради с самым забитым задником, чтобы было на что посмотреть в школе 🔍

На кнопочном телефоне у меня было не так много Java-игр, плюс товарищи могли что-то передать по ИК-порту. Но однажды мне купили ШНУР по которому можно было с компа перекинуть все, и я стал "устанавливать все игры" 🖥

Ломая глаза об экран 240x320, я прошел все популярные игры, а для Gravity Defied я прошел все моды и даже пытался менять в .jar-файле что-то сам, получилось поставить картинку на фон и поменять окраску мотыка ⌨️

Обзор байткода Java 👩‍💻

Язык 👩‍💻Java появился в 1995 году и прошел большую эволюцию. Сначала он использовался для апплетов, выполняющихся в браузере. Потом для приложений Nokia и прочих кнопочников (подмножество J2ME).

Эти направления давно умерли, но язык живет - он популярен для разработки в Android, в финтехе и бэкенде (лучший в мире фреймворк для бэкенда 👩‍💻 Spring), есть много проектов (Kafka, ZooKeeper, etc.), появились интероперабельные языки - 👩‍💻Kotlin, 👩‍💻Scala, Closure.
Есть несколько реализаций компилятора Java и виртуальных машин.

Язык довольно простой, потому что на него наложена куча ограничений:
Весь код должен находиться внутри классов.
Тело функции надо писать сразу (нельзя как в C++ только "объявить" функцию).
Принцип "1 класс = 1файл" - в файле Foo.java должно находиться определение ровно одного класса с именем Foo.
Все типы, кроме примитивных (int, double, и пр.), неявно наследуются от класса java.lang.Object. Все методы виртуальные (кроме статических методов).

Генерики в языке - просто развод, их по факту нет. Они добавлены аж в 2004 году как синтаксический сахар 🍫
Все ссылки на объекты указывают на java.lang.Object, а в коде делается неявное приведение к типу.
То есть запись ArrayList<Foo> это самообман - в действительности хранятся ссылки не на Foo, а на java.lang.Object, просто есть неявное приведение к Foo и компилятор чекнет что в твоем коде нигде нет некорректных приведений 🔍

Чтобы примитивные типы можно было использовать в контейнерах, для них сделаны типы-"обертки", наследующиеся от java.lang.Object. Для int это Integer, для double это Double, и так далее.
Нельзя сделать ArrayList<int>, можно сделать ArrayList<Integer>.
Можно оценить оверхед - если std::vector<int> из 128 элементов это 4*128 последовательных байт в памяти, то ArrayList<Integer> из тех же элементов это 128 объектов (которые находятся хрен знает где в куче), каждый является оберткой над int-ом 🍔
Хотя в Java это нормально - он не задумывался как супер вычислительный язык.

После компиляции каждый Foo.java преобразуется в Foo.class, потом они все попадают в "исполняемый" .jar-файл, который является просто zip-архивом 📦
В начале .class-файла находится "constant pool", это константы (строки, длинные числа, и прочее).
Потом в файле находятся функции класса, скомпилированные в байткод.

В супер понятной официальной спеке можно увидеть примерный вывод компилятора в разных случаях, формат .class-файла, что должна делать виртуальная машина, и прочее.
Байткод очень простой - каждая команда состоит из 1 байта, называется "опкод", после него может быть 1-2 байта дополнительной инфы, если надо.
Команды разбиты на ~20 групп из почти одинаковых опкодов, список тут. Многие высокоуровневые, например опкод arraylength который положит на стек размер массива.

Компилятор (который переводит язык в .class-файлы) не делает никаких предположений о memory layout объекта, поэтому вызов метода выглядит так:

    invokevirtual #4 // каждый метод (кроме статических) является виртуальным

Где #4 это 4-й объект в "constant pool", являет собой "символическую ссылку", то есть тупо строку 😁
Если это метод int addtwo(int a, int b) в классе Example, то ссылка такая: Example.addtwo(II)I
Виртуальная машина должна сама все отрезольвить и подставить адрес метода.

ПРОДОЛЖЕНИЕ В КОММЕНТАРИИ

#story

Психоакустика и Bluetooth 🎧

(Вступление)

Heute treff ich einen Herrn,
Сегодня встречаюсь с одним господином,
Der hat mich zum Fressen gern.
Который охотно меня съест.
Weiche Teile und auch Harte,
Нежное филе, да и твердые куски
Stehen auf der Speisekarte.
Входят в меню!

На фото господин, чей голос я почти каждый день слушаю уже давно.
Особенно круто было в 12-13 лет. Представьте - на улице среди панелек мрак и холод, в дворовой школе безвкусно одетые учителя талдонят про деепричастия, на перемене порамсил с иностранным специалистом (и его 100500 братьев хотят с тобой поговорить), на обед вчерашние макароны.
Но вот ты за компьютером, включаешь эту музыку, и все проблемы тают как майский снег, ты становишься "Богом, входящим в Вальгаллу". Всегда есть что посмотреть - например клип из 1995 (вдохновленный романом "Парфюмер"), клип из 1998 (нарезанный из фильма "Олимпия" 1938 года), запись концерта 1998 года Live Aus Berlin (море огня) 🔥

Самый базовый формат цифрового звука это PCM, он представляет собой просто значения амплитуд (это громкость звука).
Например, формат WAV это заголовок из 44 байт, после которого идут байты PCM.
Несжатый звук длительностью в 1 секунду, с частотой 48kHz, стерео (то есть два канала), с двумя байтами на каждое значение амплитуды занимает примерно 1.5 Мбит.

Звук передается мне через Bluetooth 🤙 Но в таком случае его приходится сжимать.
Рекламируется, что пропускная способность Bluetooth составляет 3 Мбит/с, но по факту доступно в разы меньше и вышеуказанный звук нельзя передать несжатым.
Например, под "3 Мбит/с" подразумевается, что идут две одновременные передачи битов от девайса A к девайсу Б, и наоборот от девайса Б к девайсу А, обе 1.5 Мбит/c (направление меняется каждые 625 микросекунд). Кроме этого, много места занимают служебные заголовки, и бывает снижение битрейта из-за расстояния и интерференции 😔

Звук можно сжимать без потерь (lossless кодеки), там применяется много приколов и есть много кодеков (например FLAC), но толку мало - сжатие получается примерно в два раза. Этого недостаточно, чтобы нормально передавать звук по Bluetooth. Еще такие алгоритмы обычно вычислительно сложные 👎

Звук можно сжимать с потерями (lossy кодеки). Всего кодеков в Bluetooth с десяток, но единственный, который должен поддерживаться каждым девайсом это SBC (sub-band coding) 🤷‍♂️
Этот кодек сжимает по отдельности небольшие куски стрима. Например, для 16-битного стерео это 512 байт, то есть 128 значений амплитуд, что при частоте 44.1kHz соответствует 2.9мс. В кодеке можно поставить разные настройки (о них "договариваются" девайсы при коннекте через специальные пакеты), при High Quality на такой кусок выходит пакет в 119 байт, что соответствует битрейту 328 Кбит/с.

Чтобы так сильно сжать звук, используются познания психоакустики 👁 Эта наука изучает обработку звука мозгом. Если есть какой-то громкий звук в определенной частоте, то остальные звуки в других частотах мозг как бы "не слышит".
В SBC используется примитивная психоакустическая модель. Частоты разделяется на несколько равных диапазонов (называются "band", в SBC их максимум 8 штук, а в MP3 аж 32), и чем "громче" диапазон, тем больше битов выделяется на его кодировку, а информацию о "тихих" диапазонах можно и вовсе выбросить.
Информация упаковывается в фрейм, получателю остается вычислительно куда менее трудоемкая задача - распаковать фрейм, восстановить подпорченный сжатием звук и воспроизвести его 🎧

За мощность сжатия в SBC отвечает параметр bitpool. Чем он больше, тем меньше сжимается аудио. К сожалению, абсолютное большинство производителей девайсов и софта (даже Windows и Linux) ограничили его сверху значением 53, что дает этот самый битрейт 328 кбит/с.

ПРОДОЛЖЕНИЕ В КОММЕНТАРИИ

#opensource

Обзор опенсорсных программ и конкурсов Google 🕸

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

1️⃣ Google Code-In 👦
Это уже закрытая программа, она проходила каждый год с 2010 до 2019.
Суть была такова - с одной стороны заявлялись разные опенсорсные организации (как KDE, Fedora, Tensorflow и прочие), которые готовили кучу задачек чуть сложнее чем "добавить виджет в панель", то есть довольно лайтовые.
С другой стороны заявлялись микрочелики 13-17 лет (включительно), которые их выполняли в течении нескольких недель. Бесплатно, за опыт 😁 Но в конце каждая организация выбирала двух жостиков, и они на халяву езжали в США 🇺🇸

Я поучаствовал пару раз, во второй мне подфартило и я на пару недель на халяву съездил в Bay Area (несколько "официальных" дней полностью за счет Google, остальные дни оплачивали отель на свои 💳)
Примерно как это было можно посмотреть в более древнем фотоотчете этого хлопца.
В целом, было интересно после глубинки белгородской области, побывал во многих местах, которые потом снял пизДудь в своей рекламе. Из минусов были конские цены на всё и засилье бомжей сидящих на крэке, но это общеизвестные факты насчет Bay Area.

2️⃣ Google Summer of Code 🏝
Тоже программа про опенсорс как предыдущая, есть разница:
1️⃣ Длится три месяца
2️⃣ Участвуют только студенты
3️⃣ Опенсорсных организаций намного больше - практически все известные там есть
4️⃣ Сделать надо какую-то серьезную задачу для организации, вот список для LLVM. Студент должен предоставить план ("пропозал"), как он собирается делать эту задачу. Некоторые организации требуют наличие коммитов в проекте, или сдать тест на C++, или еще как-то доказать достойность. Но многие организации "легкие" и там проекты полная халява.

Последний 5️⃣ факт - Google платит за работу студентам. Раньше всем за лето платили 5000$ независимо от страны, расы, гендера и прочая, и прочая 💰
Потом решили, что слишком много участников из бантустанов, им такое бабло будет жирно. Поэтому ввели какой-то индекс гамбургера. Студенты из России и ее любимых соседей получают по 3000$ (минимум по шкале), из США по 6000$ (почти максимум) и так далее 💸

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

3️⃣ Google Code Jam 🍯
Легендарный контест по решению задачек, с лайв-стримами и прочим ⌨️
К сожалению, уже закрытый, проходил каждый год с 2003 до 2020 года.

Там была "воронка" из нескольких раундов: Qualification, Round 1, Round 2, Round 3, Final - с возрастающей сложностью.
На квалификацию записывались десятки тысяч людей, до финала доходило по ~26 человек из топа Round 3 (стата по годам).

Я до финала никогда не доходил - пик был в 2019, когда в Round 3 получил 171 место 🧐 И потом мне на почте не отдали футболку за участие в 3м раунде, потому что паспорт находился на замене по причине наступления 20 лет 🕺
А мой подписчик @bminaiev был в финалах неоднократно 😎 Подписывайтесь на его блог - @bminaiev_blog 😉

4️⃣ Google Hash Code #️⃣
Самый бомжацкий из конкурсов (тоже отменен, с 2023) - надо зарегистрировать команду из 2-4 человек и решать задачу оптимизации чего-нибудь несколько часов онлайн.

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

#books

Обзор книги "Modern Parallel Programming with C++ and Assembly Language" (2022 г.) 📚

(можно скачать PDF тут)

Как можно понять, книга посвящена "параллельному программированию".
Но тут имеется в виду не та параллельность когда есть много CPU (и используются мьютексы, etc.), а параллельность внутри одного CPU, а если точнее, то вся книга про SIMD (single instruction, multiple data) 🏃

Сейчас стандартные типы данных имеют размер 8/16/32/64 бит (соответственно это byte/word/dword/qword), они "нативно" поддерживаются потому что сами регистры общего назначения у процессора имеют размер 64 бита 🤡

Но в процессорах часто есть регистры на 128, 256 и даже 512 бит (соответственно это xmmword/ymmword/zmmword в x86) 😎 В эти регистры "упаковываются" значения стандартного размера и над ними затем делаются групповые операции.

Проще показать на примере - пусть мы суммируем float'ы:

// float* z, const float* x, const float* y, size_t n
for (size_t i = 0; i < n; i++)
    z[i] = x[i] + y[i];

То SIMD-версия на 256-битных регистрах могла бы выглядеть так (с поправкой на конкретный компилятор, т.к. эти интринсики не специфицированы в Стандарте С++):

// представим что `n` делится на 8
for (size_t i = 0; i < n; i += 8) {
    __m256 x_vals = _mm256_loadu_ps(&x[i]); // грузим x[i..i+8] в один регистр
    __m256 y_vals = _mm256_loadu_ps(&y[i]); // грузим y[i..i+8] в другой регистр
    __m256 z_vals = _mm256_add_ps(x_vals, y_vals); // вычисляем z[i..i+8] в третьем
    _mm256_storeu_ps(&z[i], z_vals); // выгружаем z[i..i+8] в память
}

Код выше работает быстро, решительно, в разы быстрее "наивного" варианта.
Общий flow такой - в "длинный" регистр выгружается мини-массив чисел (в примере выше массив из 8 float'ов), и ускорение достигается за счет того, что процессор не тратит время на чтение одних и те же опкодов, а сразу делает нужную операцию.

Так как процессоры сейчас гига сложные (я наклал кирпичей даже когда делал эмулятор m68k 45-летней давности!), то таких "групповых операций" наделали много. Можно, например, вычислять еще z[i] = min(x[i], y[i]), или y[i] = x[2*i] + x[2*i+1], или даже быстро переставить элементы z[i] = x[y[i]], и так далее.

Книга посвящена только архитектуре x86 (архитектуры как ARM не рассматриваются).
SIMD-расширений в x86 есть несколько. Сначала в 1997 году появился MMX от Intel, потом в 1998 году 3DNow от AMD, и так далее, многие давно устарели и не выпускаются.
Книга посвящена только сравнительно новым SIMD-расширениям AVX (2011 год), AVX2 (2013 год) и AVX-512 (2017 год).

Глава 1️⃣ описывает базу SIMD.
В главах 2️⃣➖8️⃣ по одному шаблону описываются фичи AVX / AVX2 / AVX-512:
1️⃣ Описывается какая-нибудь платиновая задача - найти минимум/среднее в массиве, перемножить матрицы, применить свёртку, etc.
2️⃣ Приводится портянка кода на C++: "наивная реализация" vs "реализация на SIMD", с нудным описанием что откуда идёт.
3️⃣ Приводится бенчмарк, наивная реализация проигрывает SIMD в среднем в 10-15 раз.
В главе 9️⃣ описывается как можно было бы сделать портабельную SIMD-программу - для этого в x86 есть опкод cpuid, по которому можно узнать поддерживаемые SIMD-расширения и еще много что.
В главе 1️⃣0️⃣ неплохо описывается боян архитектура процессора x86-64 вместе с этими SIMD-регистрами в 256/512 бит.
В главах 1️⃣1️⃣➖1️⃣8️⃣ описывается то же, что в главах 2-8, но на ассемблере... Я это не читал 😁
В главе 1️⃣9️⃣ описывается здравый смысл, то есть гайд по SIMD-оптимизациям, общая тема - оптимизировать надо не всё подряд, а только то что видно в профайлере, потому что SIMD-код понимать трудно и легко ошибиться.
В аппендиксах есть инфа как ставить вижуэл студио и ссылки на доки... 🔍

В целом полезная книга, можно почитать для общего развития. Только нужно иметь в виду:
1️⃣ Некоторые задачи лучше решаются через GPU, а не через SIMD на CPU (который ускорит лишь в единицы раз, а не в сотни).
2️⃣ Современный компилятор может сам сгенерировать SIMD-код (но это бабка надвое сказала).
3️⃣ Сначала профайлер, потом оптимизации.

#jostik

Обзор жостиков C++ 😱 (номер sizeof(char))

(Предисловие)
Эту картинку я сделал месяц назад, и хотел отправить в WG21 (Working Group 21, он же Комитет C++) как предложение для логотипа 🎨 Это буква "С" и два плюса.

Но вспомнив комитетские приколы, решил не делать 🦆
Какой-нибудь товарищ комиссар Рабочей Группы по многообразию не принял бы ее, аргументировав что для репрезентации нужна широкая цветовая палитра, а вместо одного из крестов, например, символ зороастризма 🤲 Зачем это делать, если он сам не живет так, как говорил Заратустра - непонятно. Слишком многим людям форма важнее содержания.

Поэтому это будет новая ава 😐

1️⃣ Strong-типы 🙂

Теория о них тут, реализация на гитхабе.
Strong-типы это обертки над базовыми типами (int, double и пр.), которые не могут конвертироваться в другие типы. Это полезно, чтобы не путать аргументы и понимать цель значения из имени типа.

Например, вместо такого конструктора:

Rectangle(double width, double height);

Можно сделать такой:

Rectangle(Width width, Height height);

Где Width и Height - обертки над double, и их нельзя перепутать ✋

Strong-типам можно придавать разные "скиллы" - например Addable, Comparable, Hashable и прочие, чтобы соответственно работали операции сложения, сравнения или можно было положить тип в хэшмапу.

Эти типы "бесплатные" для рантайма - компилятор выбрасывает шелуху и работает с базовым типом 🕶

Раньше я их не принимал (если ты путаешься в параметрах, то вместо 15 параметров нужен builder pattern 🛑), но сейчас наоборот, без них жить сложнее - это неплохая вещь.

2️⃣ Упакованные типы 📦

Как известно, у типов есть выравнивание:

struct Biba {
    uint16_t a; /* 2 bytes */
    /* padding 6 bytes */
    uint64_t b; /* 8 bytes */
};
static_assert(sizeof(Biba) == 16);
static_assert(alignof(Biba) == 8);

Но во время парсинга пакетов всяких протоколов это может мешать, потому что никаких padding'ов между полями не предусмотрено. Также во время работы с сетью супер важно оптимизировать память. Тогда надо убирать выравнивание (alignment) 🎩

Это можно сделать разными способами, самый удобный такой:

#pragma pack(push, 1)
struct Boba {
    uint16_t a; /* 2 bytes */
    uint64_t b; /* 8 bytes */
};
#pragma pack(pop)
static_assert(sizeof(Boba) == 10);
static_assert(alignof(Boba) == 1);

(Этот pragma pack выглядит странно, потому что у него есть типа внутренний стек)
Команда pack(push, N) значит что все типы будут иметь alignment максимум N байт, а pack(pop) убирает это.

Менее удобный способ (потому что надо ставить каждому классу вручную) это вешать на структуру __attribute__((packed)).
Это немного по-другому работает внутри компилятора, но итог один - alignment равный единице.

Способ, который не работает - спецификатор alignas, он может только увеличить дефолтный alignment. Оно используется для подгона структуры под кэш-линию (64 байта) или SIMD-инструкции (16/32/64 байта).

А как это работает на уровне ассемблера? 🤔 Компилятор не будет генерировать дичь с переносами байтов (как для bitfield), там формируется честный unaligned access.
Как оказывается, на x86 никаких сюрпризов нет. Оно всегда поддерживало unaligned access (работающий медленнее чем aligned).
А на других архитектурах может произойти треш - надо беречься 🤔

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ 👀

#compiler

День, когда умер CRTP 🫡

По исходникам проектов на C++ можно определять, примерно в какое время был написан код 👨‍🦳 В истории C++ был революционный стандарт C++11, еще чуть менее революционный C++20 (по убыванию используемости - concepts, ranges, coroutines, modules), и проходные между ними (C++14, C++17).

В C++23 есть единственная крупная фича, ради которой стоило его ждать - deducing this 😳 Единственное место, где нужно про него читать - пропозал в стандарт, там есть всё - мотивация, обоснование всех тонкостей дизайна, примеры использования, разбор всех корнер кейсов, и прочее. Все другие объяснения из интернета принципиально менее полны 📖 Я сюда не буду копипастить примеры, они есть в пропозале.

Long story short, в каждом методе используется неявный "нулевой" параметр this, эта фича добавляет возможность явно указать этот параметр, причем необязательно с исходным типом (можно заиспользовать шаблон). Это оказалось очень нужным - уменьшает дублирование методов, убирает необходимость в CRTP, позволяет удобнее рекурсивные лямбды, и прочее 😎

Конечно, у deducing this есть ряд drawbacks 🤷‍♂️
1️⃣Есть ряд спецэффектов по типу shadowing'а переменной базового класса (в пропозале они разобраны)
2️⃣ Методы становятся шаблонными со всеми вытекающими - Clang известен тем, что в отличие от MSVC не особо проверяет код шаблона до инстанциации
3️⃣ В коде начинается треш с категориями значений, нужно понимать разницу между auto, auto&&, decltype(auto), и специально добавили срань как std::forward_like.

Реализация deducing this наконец-то появилась в LLVM/Clang 18, который зарелизился 6 марта 😮 К сожалению, релиз получился всратым, и баги не пофикшены до сих пор 🚬 Поэтому его пока никто не использует.

Но уже сейчас можно изучать вопрос - как лучше всего подготовиться к использованию этой фичи и гарантировать, что все перестанут писать "по-старому"? 👦
В этом нам поможет libclang! Мы можем написать простые python-тесты на исходный код (о них писал тут🔍), и отлавливать устаревший код.

Первым делом нужно, чтобы в проекте генерировался compile_commands.json. Это простой список команд для компилятора, его описание тут, он нужен для многих вещей, например для автокомплита.
Его создание поддерживается в CMake, для этого в корневом CMakeLists.txt надо добавить:

set(CMAKE_EXPORT_COMPILE_COMMANDS ON)

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

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ 🏃

#jostik #compiler

Обзор жостиков C++ 😎 (номер 0x00000002)

1️⃣ Сделай сам requires-clause для полей класса 😶

Шаблоны C++ развиваются в сторону упрощения - многое было сделано, чтобы избавиться от enable_if и ручной специализации шаблонов.

Одна из фичей - сейчас можно наложить trailing requires-clause на класс и на метод, чтобы ограничить их использование:

template<typename T>
  requires std::copyable<T> && std::movable<T>
struct Blow {
  void make_job()
    requires (sizeof(T) > 100)
  { /* ... */ }
};

Логичным следующим шагом должно стать ограничение на поле класса.

Такое опциональное наличие поля было бы полезно везде, где из-за свойств шаблонной сущности меняется размер класса. Например делетеры в умных указателях (как std::unique_ptr). Или отсутствие поля "size", если он указан в шаблоне (как std::span).

Супер синтетический пример, как это должно работать у вектора, который на стеке или куче в зависимости от параметра:

template<typename T, std::size_t N = 0>
class JanusVector {
private:
  // static vector, N is fixed
  std::array<T, N> arr_ requires (N > 0);

  // dynamic vector, N is not fixed
  std::size_t size_ requires (N == 0);
  T* data_ requires (N == 0);
};

// ...

int main() {
  JanusVector<int, 228> vec1;
  static_assert(sizeof(vec1) == 4 * 228);

  JanusVector<int> vec2;
  static_assert(sizeof(vec2) == 16);
}

Недавно мной была вкинута идея в разнорабочую группу по C++, пока без эффекта 🥱

Решил для прикола сделать реализацию этой фичи на Clang 👀
(Ссылки: как настроить сетап для clang, как создать свой keyword)

Дифф за пару вечеров получился не очень большим (он на gist.github.com), состоит из таких кусков:
1️⃣ В парсере разрешить парсить выражение trailing requires-clause после полей класса.
2️⃣ Сохранять это выражение в класс FieldDecl, вычислять его значение в методе isRequiresClauseSatisfied.
3️⃣ Добавить проверки в LayoutBuilder'е, чтобы не вкомпилировать storage под неудовлетворяющие поля.
4️⃣ Диагностировать обращения к неудовлетворяющим полям (создается ошибка компиляции).
5️⃣ Осторожно проинстанцировать выражение во время инстанциации шаблона 😠 Непроинстанцированные зависимые константные выражения невычисляемы!

Вот так можно делать proof of concept фичи 🥂 Это самый базовый пример, еще не рассмотрено несколько концептуальных вопросов, например:
1️⃣ Разрешить ли одинаковые имена у полей, если они никогда не скомпилируются вместе в одном классе?
2️⃣ Нужно ли помещать поле в скоуп выражения, для такого:

    // типа поле `kek_` скомпилится если у него будет метод `foo()`
    T kek_ requires requires { kek_.foo(); };

3️⃣ Всякие мелкие баги, наподобии того что в реализации не запрещено брать адрес &Foo::kek у нескомпилировавшегося поля kek.

В КОММЕНТАРИЯХ ЕЩЕ ТРИ ЖОСТИКА C++ 🏃

#story

Обзор на работу в большой компании 💼

В начале этого года я покинул Яндекс, где проработал чуть больше 4 лет 👨‍🦳
Хотя там была ровная братва среди коллег и «интересные проекты»™️, я внял мудрости современного философа - «за деньги да» 😃 Но обо всем по порядку...

Часть1️⃣ Рассказ бывалого балабола

Я накидал субъективный обзор 😀 на плюсы и минусы
➕1️⃣ Hard skills
За несколько первых месяцев реальной работы в мощном темпе выучиваешь в разы больше, чем за годы «саморазвития» до этого 👦
За долгий срок работы можно порешать задачи из широкого спектра, испытать все виды инцидентов, и в целом это интересный опыт 🤡 Можно смотреть курсы ШАД, код крутых коллег, внутренние ресурсы.
Нельзя сказать, чтобы у каждого было супер крутое знание какого-либо языка - это не самоценность, а просто инструмент выполнения задачи. Нередко встречаются ржаки по типу как на этом скрине, что чела закинули в команду где пишут на Х и он тоже выучил Х за 21 день (можно догадываться про уровень понимания)👶
Компании не нужно, чтобы ты был rockstar - большие проекты делаются сотнями людей, и адекватный менеджмент ориентируется на их средний уровень, а также резервирует время под возможные переделки ⏰
Если же менеджмент неадекватный, то будут требовать сделать космолет за неделю, что будет не под силу даже Леннарту Поттерингу 😐
К вопросу о том - можно ли считать себя "ылитой", если ты работаешь в FAANG или под них косящих 😀 - имхо это звучит неуместно, когда речь идет о супер формализованном процессе найма workforce (результат каждого собеса это буквально true или false) с "good enough" компетенцией, чтобы закрывать стандартные таски. Так вижу.

➕2️⃣ Soft skills
Если есть желание, софт скиллы тоже неплохо прокачиваются. Хотя их можно качать бесконечно - если какой-то алгоритм или фичу можно выучить раз и навсегда, то взаимодействие с людьми это то, чему можно учиться всю жизнь 🤗
Обычный "работяга" - низшее звено пищевой цепочки. То, что он делает какие-то таски - это значит что топы определили направление, менеджеры поборолись за скоуп, а тимлид нарезал таски из глубокого знания codebase.

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

Это тот случай, когда "негативный опыт - тоже опыт". Так как многое завязано на человеческий фактор, комфортное пребывание во многом зависит от твоих коллег и еще намного больше от рукля.
За все время у меня было 5 руклей, со всеми я супер ровно сработался, кроме одного. Так оно работает - чтобы у тебя были задачи с высоким импактом и рост, необходимое условие чтобы рукль (и дальше по цепочке вверх) этого тоже хотели. Некоторое время я с ним промучался, но ничего не помогало и все было настолько плохо, что мне даже ставили встречу с HR с неприятным разговором 😵 Так что совет - лучше сразу уходить, если есть негатив с руклем, а не пытаться это исправить.
Я чуть не перешел к кенту в стартап, но по итогу просто ротировался в другой под-отдел и неплохо поработал в компании еще 1.5 года 💼

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ 📖