Algorithm Visualizer — сайт, где 30+ алгоритмов разобраны пошаговой анимацией

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

Что внутри:

🔘поиск пути и обходы графов: BFS, DFS, Dijkstra, Bellman-Ford;
🔘остовные деревья Краскала и Прима, компоненты связности, потоки в сетях (Edmonds-Karp, Ford-Fulkerson);
🔘сортировки, бинарное дерево поиска, связные списки, дерево рекурсии;
🔘классика собеседований и олимпиад: N-Queens, выпуклая оболочка, машина Тьюринга.

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

Работает прямо в браузере, ничего ставить не нужно. Сохранять студентам перед сессией, всем, кто готовится к алгоритмическим секциям собеседований, и менторам — объяснять джуну Дейкстру по анимации сильно проще, чем по псевдокоду.

Полная ссылка: https://tamimehsan.github.io/AlgorithmVisualizer/

@prog_stuff

Сжать баг до минимального примера автоматически: про недооценённые test-case reducers

Когда баг воспроизводится на огромном входе — файле, программе, последовательности действий — стандартный совет «сделайте минимальный пример» звучит легко, а руками делается мучительно. Лори Тратт напоминает про инструменты, которые делают это сами: test-case reducers берут падающий вход и ужимают его, часто на 95-99%, до состояния, где удалить уже нечего.

Ключевая идея — reducer ничего не знает про ваш язык и формат. Ему нужен только оракул: функция, которая отвечает «да, этот вход всё ещё интересен», то есть баг по-прежнему воспроизводится. Всё остальное — перебор и выбрасывание кусков.

Что полезно знать:
🔘 reducer языконезависим: тот же инструмент сжимает и C-программу, и JSON, и лог действий, лишь бы был тест на «интересность»;
🔘 написать хороший тест на интересность сложнее, чем кажется: легко получить переусушку, когда вход схлопывается в другой баг, не тот, что вы ловите;
🔘 скорость этого теста решает всё: reducer вызывает его тысячи раз, поэтому его выгодно делать максимально дешёвым;
🔘 сжимать можно не только по длине входа, но и по другим метрикам — длине трейса, числу инструкций, частоте срабатывания ошибки;
🔘 есть приёмы и для недетерминированных багов, которые воспроизводятся через раз.

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

Полная статья: https://tratt.net/laurie/blog/2026/test_case_reducers_are_underappreciated_debugging_tools.html

@prog_stuff

p99 0 мс на автодополнение 240 миллионов доменов

Автор поставил себе дерзкую цель: показывать подсказки раньше, чем пользователь успеет отпустить клавишу. Задержку он меряет от момента keyUp до готового результата и закладывает бюджет p99 в 121 мс на два нажатия с паузой между ними. Чтобы в него уложиться, выдача должна быть готова почти мгновенно.

Архитектура делится на две части по распределению запросов:
🔘голова, миллион самых частых доменов из списка Tranco, лежит в памяти как символьный trie с заранее посчитанным топ-8 для каждого префикса;
🔘хвост, все 240 миллионов доменов из CZDS, лежит на SSD как memory-mapped блочный индекс с дельта-сжатием: 27 МБ оглавления в памяти и 2,5 ГБ на диске;
🔘большинство запросов к API отвечают за 2 мс, на нагрузке 1600 запросов в секунду p99 связки nginx и API держится около 15 мс;
🔘оставшаяся задержка упирается в сетевой путь через Cloudflare, поэтому для дальних регионов нужна геобалансировка.

По дороге видно, как требование «мгновенно» раскладывается на конкретные структуры данных и бюджеты по миллисекундам.

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

Полная статья: https://ruurtjan.com/articles/p99-0ms-autocomplete-for-240-million-domain-names

@prog_stuff

Сжать GIF без потерь полным перебором: история ZGIF

GIF внутри использует LZW, а не DEFLATE, и это влияет на то, как его сжимать. Существующий flexiGIF уже умеет гибкий разбор с заглядыванием вперёд, но иногда делает хуже: занятый слот в словаре потом аукается. Автор задался вопросом, какой LZW-поток для картинки минимален в принципе, и написал ZGIF, который ищет этот минимум полным перебором. По духу это Zopfli, только для LZW.

Путь к рабочей версии занял несколько подходов, от поиска A* через динамическое программирование к гибриду с отсечением:
🔘первая реализация на Python сжимала картинку 16 на 16 пикселей, всего 256 байт, за 30 минут;
🔘после оптимизаций то же самое стало занимать 4 минуты;
🔘с отсечением и заглядыванием на один шаг скорость упала до 4 секунд;
🔘результат при этом всё равно плотнее, чем у существующих инструментов.

Сохранять тем, кто любит алгоритмы сжатия и истории про то, как наивная идея «давайте переберём всё» доводится до практичной скорости.

Полная статья: https://blog.arusekk.pl/posts/lossless-gif-recompression/

@prog_stuff

Похвала memcached: зачем намеренно держать кеш простым

Автор объясняет, почему в новых проектах снова берёт memcached вместо Redis. Redis он плохим не называет. Просто напоминает, что у простого инструмента есть свои сильные стороны, про которые многие забыли.

Главные мысли разбора:
🔘Redis легко перерастает из кеша в самодельную базу: положить данные через SET проще, чем сделать INSERT, и команда постепенно перестаёт относиться к нему как к временному кешу;
🔘у memcached нет персистентности на диск, и это сделано намеренно: его можно гонять как нагрузку без состояния и не думать о сохранности;
🔘клиентские библиотеки memcached прощают сбои: если сервер упал, get возвращает пустоту, и приложение просто идёт в основной источник данных;
🔘кластеризация живёт на стороне клиента через хеширование ключей по нескольким адресам, упавшая нода выводится из ротации;
🔘автор спокойно поднимает десятки инстансов по 64 МБ почти без накладных расходов.

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

Полная статья: https://jchri.st/blog/in-praise-of-memcached/

@prog_stuff

Git-сервер без диска: как объектное хранилище научили говорить по git

Git-репозиторий под капотом это объектное хранилище: коммиты, деревья и сами файлы лежат как сжатые объекты с адресацией по содержимому, а ветки и теги это крошечные изменяемые указатели на них. Обычно git-сервер держит всё это на локальной файловой системе одной машины, и она становится единой точкой отказа. Автор решил проверить, что будет, если направить git-сервер прямо в бакет объектного хранилища, без диска, без бинарника git и без базы данных.

Получился objgit, один бинарник, который хранит репозитории в облачном бакете и говорит по трём транспортам: HTTP, классический git:// и SSH. Внутри он опирается на go-git, чистую реализацию протоколов git на Go, и на billy, файловую абстракцию, которую автор натянул на объектное хранилище, чтобы go-git не заметил подмены.

Самое предметное в статье это грабли латентности, разобранные по числу запросов:
🔘push пакета из 100 тысяч объектов разворачивался в 200 тысяч обращений к хранилищу, по одному stat и write на каждый объект, и при задержке около 10 мс это полчаса ожидания;
🔘клон простого репозитория из 318 объектов с пакетом в 200 КиБ до починки кеша делал больше 8500 вызовов GetObject;
🔘поиск объектов по двухсимвольным префиксам каталога давал до 256 вызовов листинга бакета за один клон;
🔘ошибка в кеше приводила к тысячам фоновых листингов каждые 30 секунд в течение 10 минут;
🔘pack-файлы неизменны и адресуются по содержимому, поэтому их можно держать в локальном кеше без инвалидации: первый запрос медленный, дальше скорость файловой системы;
🔘атомарное обновление веток автор делает через расширение RenameObject, переименование объекта за один запрос к хранилищу.

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

Полная статья: https://www.tigrisdata.com/blog/objgit/

@prog_stuff

Пассивный Ethernet-tap на бредборде за 15 евро

Чтобы посмотреть трафик в домашней сети, обычно нужен управляемый свитч с port mirroring или отдельный TAP-девайс за сотни долларов. Ata Kuyumcu собрал пассивный вариант на минибредборде: без чипов, без питания и без активной обработки пакетов.

🔘 четыре разъёма RJ45: два в разрыв рабочего кабеля, два мониторных для утекающей копии;
🔘 два конденсатора по 220 пФ на линиях мониторных портов сбрасывают Gigabit-автосогласование до 100 Mbps, чтобы приёмник видел только нужные пары;
🔘 рабочие пары идут напрямую через плату, поэтому отключение или поломка тапа не рвёт основной линк;
🔘 вся сборка обошлась примерно в 15 евро;
🔘 в тесте с телевизором за 7,5 минуты плата поймала 2769 пакетов и 877 SSDP-анонсов без единой CRC-ошибки.

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

Полная статья: https://blog.lvmbdv.dev/posts/building-a-passive-ethernet-tap/

@prog_stuff

Что на самом деле такое database cluster в PostgreSQL

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

Каждая база сама является объектом со своим OID. У встроенных баз он захардкожен: 1 у template1, 4 у template0, 5 у postgres. Пользовательские объекты стартуют с 16384. Все объекты и связи между ними хранятся в системных каталогах вроде pg_class и pg_database, устроенных как обычные таблицы.

🔘 tablespace физически реализован через symlink, поэтому файлы базы можно раскидать по разным дискам, не трогая логику выше;
🔘 heap-страница весит ровно 8192 байта, и модуль pageinspect позволяет заглянуть внутрь неё вручную;
🔘 значения длиннее 2 КиБ Postgres выносит во внешнее хранилище TOAST вместо того, чтобы впихивать их в страницу целиком;
🔘 VACUUM FULL переписывает файл и меняет relfilenode, а OID самой таблицы при этом остаётся прежним.

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

Полная статья: https://www.buraksen.dev/articles/internals-of-postgresql-db-cluster-and-tables

@prog_stuff

Zig вынес пакетный менеджер из компилятора в систему сборки

Andrew Kelley описал редизайн Zig: вся логика пакетного менеджера переехала из компилятора в отдельный процесс сборки maker. Раньше компилятор сам тянул зависимости, теперь этим занимается build-система, а компилятор остался компилятором.

🔘 из бинарника zig вынесены fetching пакетов, HTTP-клиент, TLS/crypto, Git-протокол, распаковка xz/gzip/zstd/flate/zip и парсер build.zig.zon;
🔘 сам бинарник похудел на 4%: с 14,1 МиБ до 13,5 МиБ на сборке без LLVM в режиме ReleaseSmall;
🔘 пакетный менеджер теперь собирается в ReleaseSafe, то есть все сетевые операции работают с включёнными проверками безопасности;
🔘 crypto и хеширование файлов могут использовать редкие инструкции конкретного CPU, потому что maker компилируется прямо на машине пользователя, а не распространяется готовым бинарником;
🔘 флаг --maker-opt заменили на переменную окружения ZIG_DEBUG_MAKER, а --zig-lib-dir — на ZIG_LIB_DIR.

Это промежуточный шаг к протоколу build server, который нужен языковому серверу ZLS.

Сохранять тем, кто интересуется архитектурой компиляторов и тем, как языки постепенно выносят периферийную логику из ядра.

@prog_stuff

Как эмулировать inline-ассемблер в Haskell, которого там нет

Задача простая на словах: перемножить два Word64 и получить обе половины 128-битного результата через одну машинную инструкцию mulq. В GHC нет inline assembly, и разработчик под ником minoki перебрал все возможные обходные пути, от честного FFI до чёрной магии на уровне calling convention.

🔘 unsafe FFI с указателем через alloca работает, но тянет за собой IO и лишнюю память;
🔘 unsafe FFI в два вызова, отдельно для старшей и младшей половины, укладывает всё в регистры без указателей;
🔘 unsafe FFI через XMM-регистры возвращает обе половины сразу, но требует __m128i на стороне C;
🔘 foreign import prim позволяет написать собственный PrimOp прямо на ассемблере, с ручным учётом регистров STG (%rbx, %r14, jmp *(%rbp)) и макросов LEADING_UNDERSCORE и TABLES_NEXT_TO_CODE;
🔘 отдельная ассемблерная обёртка переводит между C calling convention и GHC calling convention, чтобы дёргать C-функцию, которая возвращает unsigned __int128 структурой по значению.

На Zen4 в WSL2 встроенный timesWord2# отработал за 4 нс, foreign import prim на чистом ассемблере уложился в 4,5 нс, а unsafe FFI с указателем скатился до 19 нс. Safe FFI для такого короткого вызова вышел медленнее 60 нс, то есть медленнее чистого Haskell на Integer.

Сохранять тем, кто когда-нибудь спорил, действительно ли safe FFI в GHC настолько накладен, как все говорят.

@prog_stuff

Rust-компилятор, переписанный в 46 миллионов строк C

Rustc — самокомпилирующийся компилятор Rust — переведён в 46 миллионов строк C и собирается обычным GCC и make, без единой строчки cargo или rustc в цепочке сборки. Автор — разработчик бэкенда cilly, который компилирует Rust в C.

🔘это уже 14-я попытка автора скомпилировать Rust в C — до этого были публичные и приватные проекты вроде rustc_codegen_clr;
🔘бэкенд генерирует «witness»-программы, которые прощупывают, что поддерживает целевой C-компилятор и платформа, и подстраивает вывод под них;
🔘получившийся код собирает core, alloc и std и способен пересобрать сам себя;
🔘практической пользы для повседневной разработки в этом немного — это демонстрация переносимости, а не замена rustc.

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

Полная статья: https://github.com/FractalFir/crustc

@prog_stuff