C *

Представим задачу: хайлоад-сервис гонит поток данных — логи, IP-адреса, ID пользователей, миллиарды записей в сутки. Ваша задача — посчитать количество уникальных посетителей за неделю.

Первым решением может показаться завести HashSet и кидать туда ключи, а в конце посмотреть размер. Решение неплохое, но когда речь заходит о миллиардах записей — память будет слабым местом. Один IP-адрес (4 байта) как ключ в HashSet потянет за собой накладные расходы на ноды, указатели и хеши. На практике один элемент сжирает не меньше 50–100 байт. Поток в миллиард уникальных записей потребует под сотню гигабайт оперативной памяти. Это дорого, а если инстансов десять — то просто нереально.

Но существует алгоритм, который способен решить эту задачу примерно в 1.5 килобайта памяти с погрешностью около 2%? Без хранения самих данных и гигантских кластеров. Достаточно одного прохода по потоку и пары битовых трюков — именно так и работает HyperLogLog, алгоритм родом из математической статистики, который перевернул подход к подсчёту уникальности в Big Data.

HyperLogLog используют в Redis, BigQuery, ClickHouse, Presto. В этой статье мы разберем и реализуем этот алгоритм на C, а также узнаем его предысторию.

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

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

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

Или: как embedded-разработчик случайно написал визуализатор временных рядов

Это моя первая статья и сразу на тему в которой я разбираюсь примерно никак. Ее можно воспринимать как условный "дневник разработчика".

Статья написана не без помощи LLM, от нее по большей части редактура. Прошу камнями не кидаться

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

С чего всё началось

В миру я позиционирую себя как Embedded-разработчик, а как принято во многих местах в России разработчик встраиваемых систем - это инженер-разнорабочий. Написать firmware, развести не сложную PCB, поколдовать над ядром Linux,  провести исследования датчиков с китайского завода, напаять концевиков, собрать тестовый стенд, а если еще и осталось время - по возможности спроектировать корпус для устройства и произвести его прототип.

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

Но иногда появляется потребность в визуализации. Пока речь идет о низкочастотных датчиках и малом количестве данных - все довольно просто, но как только данных становится больше, а частоты выше - всплывает множество нюансов. При 70 кГц через 10 секунд работы датчика у меня уже 700 000 точек. Через минуту – 4.2 миллиона. А пользователь при этом хочет масштабировать/панорамировать оси, выделять области, нажимать кнопки – и всё это должно отзываться мгновенно. Стандартный подход «передать всё в библиотеку» ломается очень быстро.

Привет, Хабр! Меня зовут Кирилл, я разработчик СХД в YADRO и ML-энтузиаст, автор книги "Hands-on Machine Learning with C++". Я заметил, что роль С/С++ в экосистеме машинного обучения трансформируется прямо сейчас. Чтобы понять, какое значение язык играет в развитии ML, мы поговорим о классическом применении C++ для ручной оптимизации вычислительных ядер. Затем разберемся, почему новый стандарт не закрепляет реализаций линейной алгебры, а отдает это на откуп поставщикам стандартной библиотеки и вендорам оборудования. И в завершение подумаем, как работать с «зоопарком реализаций», который из-за этого остается. 

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

Оказалось, что классика вроде «Съешь ещё этих мягких французских булок» не подходит — в моём наборе каждая буква была только один раз. А те панграммы, где буквы не повторяются (можно найти, например, у Лебедева в «Ководстве») — «Эй, жлоб! Где туз? Прячь юных съёмщиц в шкаф.» или «— Любя, съешь щипцы, — вздохнёт мэр, — кайф жгуч» — они, скажем так, на любителя. Слишком много восклицаний, междометий и прямой речи. Хотелось чего-то более пристойное и связное.

У меня получилось найти следующую панграмму:

«Съев мяч, щипцы, эльф‑конюх ждёт груз шайб»

В ней все 33 буквы русского алфавита, каждая по одному разу. В статье — как я её искал, фильтры словаря и то, как устроен поиск.

Привет, мой читатель с Хабра!

Знаешь ли ты о том, что такое многопоточное программирование? Если да, то это хорошо! Если же нет, то придётся почитать немного скучноватой теории про такую известную технологию программирования, как многопоточное программирование, а затем мы копнём эту тему глубже…

Руководство по разработке своей версии vsnprintf для целочисленных значений для увлекающихся osdev. Проходит стандартные тесты от gcc

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

Идея возникла из необходимости быстро искать 16-битные целые числа в массивах размером до 4096 элементов — именно такие структуры лежат в основе популярного формата Roaring Bitmap. Вместо того чтобы на каждом шаге сравнивать искомый элемент только с одной серединой интервала, авторский алгоритм использует две ключевые аппаратные особенности современных процессоров. Во-первых, это SIMD-инструкции, позволяющие за раз сравнить до 16 элементов. Во-вторых, это распараллеливание работы с памятью, которое даёт возможность безболезненно делить массив не на две, а сразу на четыре части. Так родился гибрид, который сначала выполняет учетверённый поиск по блокам, а затем находит нужный элемент с помощью векторных инструкций. Давайте разберёмся, как это работает и почему такой подход действительно позволяет превзойти бинарный поиск.

Приветствую читатель!

Для тех кто со мной впервые вот оглавление:

Часть 1

Часть 2

Часть 3

Код лежит тут

Подразумевается что читатель знаком с архитектурой аллокатора из части 3 и понимает алгоритм неявного списка свободных блоков который был освещен в части 1

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

Решение потребовало реализации функции mem_malloc_aligned которая выделит бОльший кусок памяти с учетом запрошенного выравнивания что бы мы там точно нашли правильно выровненный адрес.

Но что если адрес указателя из mem_malloc_aligned не совпадает с адресом указателя который вернул mem_malloc? Что делать в mem_free? Что делать в mem_realloc? Как мне работать с указателем перед которым не хедера?

Для начала я решил применить технику добавления смещения перед payload выровненного блока вместо хедера, смещения до payload изначального блока у которого есть хедер и футер.

Но как мне отличить offset от header? Я решил добавить magic number в хедер и футер увеличив тем самым размер оверхеда в 2 раза и раз уж от него считалось внутреннее выравнивание блоков памяти в аллокаторе и минимальный размер блока, то теперь минимальный размер блока стал 32 байта, а с оверхедом все 64. Теперь можно просто проверять magic number и если он не совпадает, то интерпретировать число на месте хедера как смещение до payload блока который вернул mem_malloc и далее получив на него указатель работать с блоком стандартным образом.

У меня было множество вело фар и всегда меня напрягало то, что фара включается практически мгновенно.

Глаза даже не успевают приспособиться и это доставляет существенный дискомфорт.

В связи с этим я принял решение разработать свою безопасную вело фару.

Примерно полгода назад я познакомился с VLIW‑процессором Эльбрус-8СВ. На тот момент у меня уже был опыт написания кода на ассемблере для VLIW‑процессора TMS320C66. Поэтому я захотел сделать нечто похожее для Эльбруса, а именно, написать алгоритм FFT на ассемблере. Но из‑за нехватки документации на инструкции процессора мне пришлось начать с реализации какого‑нибудь простого алгоритма на Си, чтобы изучать его ассемблерный вывод.
По результатам этой работы была опубликована предыдущая статья на Хабре.

После завершения той статьи я решил попробовать написать алгоритм FFT на Си для Эльбруса. Работа ещё не завершена, но определённые успехи уже есть (сравнение с EML присутствует). В этой статье я хочу поделиться полученными на данный момент результатами.

Изначально цели у меня свергнуть с пьедестала популярные сетевые инструменты типа BloodHound и иже с ними не было. Нет ее и сейчас. У них было, есть и будет заслуженное место в арсенале redteam и blueteam‑команд. Все нижеописанное можно воспринимать с легкой иронией, как необычный побочный эффект моих изысканий.

Вопрос у меня был простой — какие компоненты подсистемы COM лежат в основе AD? Если вкратце, то Windows управляет AD через ADSI — Active Directory Service Interfaces. Это довольно замороченная COM‑абстракция над LDAP, которую использует сама Windows, когда компоненты, подключенные к домену, запрашивают каталог. Её используют процессы групповой политики, оснастки MMC и так далее

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

Вот уже более 20 лет проходит масштабная конференция разработчиков свободного и открытого ПО – FOSDEM. Для CodeScoring она примечательна тем, что с 2021 года на ней регулярно представлен тематический деврум "SBOMS and supply chains" посвященный составу программного обеспечения и цепочкам поставок.

Эта статья – адаптация доклада "LibreOffice and Collabora Online – how we managed to automate SBOM generation for a large legacy project", с которым Торстен Беренц выступил на конференции в 2026 году. Специально для вас мы перевели выступление и превратили его в статью, оригинал доклада на английском языке – по ссылке.

Привет, Хабр! Меня зовут Владислав, я разрабатываю компиляторы в YADRO. В этой статье я расскажу вам про алиасинг памяти в C++: как он развивался, к чему пришел сейчас и что комитет по стандартизации языка думает делать с алиасингом в будущем. По пути я немного затрону алиасинг в других языках, рассмотрю связанные случаи undefined behavior, а также пропозалы C++, которые, как ожидалось, проблемы с алиасингом решат.

В третьей статье пойдет речь уже о готовом аллокаторе который вполне пригоден для распределения памяти

Я продолжаю освещать работу с USB на Raspberry Pi Pico. В текущей статье хочу привести пример, как можно использовать Raspberry Pi Pico в качестве загрузочного USB-устройства.

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

Как-то давным-давно я заинтересовался дешевым железом, ибо был студентом-ардуинщиком, который очень хотел сэкономить. И как-то раз пришла идея — поработать с E-INK дисплеем. Цены на новые модули на Али кусались, поэтому я отправился шерстить Авито и нашел там объявление о продаже б/у электронных ценников из супермаркета и DNS.

О чудо! Всего 250 рублей за штуку: плата, контроллер, корпус, и оно даже работает... наверное.

Я заказал целую партию, не подозревая, что внутри меня ждет коррозия всего - чего можно, чип nRF52832 в новой партии, нестандартный протокол связи и абсолютный ноль документации. О том, как я ковырял эти платы китайским программатором, как писал в RAM через GDB, убил пару ценников, экранов и в итоге завел дисплей через Zephyr RTOS. Спойлер: фрактал Мандельброта успешно выведен! Дум не за горами

Существует два фундаментальных подхода к доставке данных: уникаст - передача "точка-точка", и мультикаст - передача "один-ко-многим". Подавляющее большинство данных в локальных и глобальных сетях ходит по TCP, уникасту. У большинства программистов сложилась четкая ассоциация: если нужно устроить сетевое взаимодействие, то используем TCP. Но в финансовой сфере на этот счёт мы привыкли думать по-другому. Если требуется построить систему с минимальным временем отклика, но при этом с высокой пропускной способностью и надежной доставкой, то мультикаст годится лучше.