На протяжении более двух лет я много времени уделял разработке моего собственного эмулятора Game Boy, GameRoy. Я немало успел сделать. В эмуляторе был готов графический пользовательский интерфейс (с отладчиком и дизассемблером), сама программа прошла многочисленные тесты и могла сравниться с некоторыми наиболее точными эмуляторами. Я даже портировал её на Android!

Прошло много лет с тех пор, как я написал donut.c, и всё это время я не раз задумывался, можно ли как-то упростить этот проект. Например, может быть, нашёлся бы способ очертить пончик лучами, дописав для этого немного кода. В октябре 2023 года я написал твит о совершенно внезапном просветлении, позволившем мне найти новый подход к этой проблеме — без привлечения памяти, без каких-либо синусов, косинусов, без квадратных корней, деления, строго говоря, даже без умножения. Всё нужное можно отобразить с помощью одних только сдвигов и сложений. Вот обновлённая версия на C.

Эта программа представляет собой свободную от зависимостей реализацию GPT-2. Она загружает матрицу весов и файл BPE из оригинальных файлов TensorFlow, токенизирует вывод при помощи простого энкодера, работающего по принципу частотного кодирования, реализует базовый пакет для линейной алгебры, в котором заключены математические операции над матрицами, определяет архитектуру трансформера, выполняет инференс трансформера, а затем очищает вывод от токенов при помощи BPE-декодера. Всё это — примерно в 3000 байт на C.

Код достаточно эффективно оптимизирован — настолько, что малый GPT-2 на любой современной машине выдаёт отклик всего за несколько секунд. Чтобы этого добиться, я реализовал KV-кэширование и применил эффективный алгоритм перемножения матриц, а также добавил опциональный OMP-параллелизм.

Взяв это за основу, можно создать некий аналог Chat GPT — при условии, что вас не слишком волнует качество вывода (объективно говоря, вывод получается просто ужасный… но решение работает). Здесь есть некоторые глюки (особенно с обработкой символов в кодировке UTF-8), а для эксплуатации модели размером XL с широким контекстным окном может потребоваться ~100 ГБ оперативной памяти. Но, если вы просто набираете текст в кодировке ASCII при помощи малого GPT2, то такая модель должна нормально работать примерно везде.

Я выложил весь код на GitHub, поэтому можете свободно брать его там и экспериментировать с ним.

Мы работаем над базой данных EdgeDB и в настоящее время портируем с Python на Rust существенную часть кода, отвечающего за сетевой ввод/вывод. В процессе работы мы узнали много всего интересного.

От переводчика.

Под катом я помещаю для вас перевод статьи знаменитого и влиятельного инженера из Кремниевой Долины Дэвида Крошо (David Crawshaw), сооснователя и технического директора (CTO) компании Tailscale. Ранее Дэвид более 9 лет работал программистом-исследователем в компании Google и в настоящее время является одним из самых авторитетных практикующих специалистов по языку Go. В частности, именно Дэвид адаптировал Go для платформ iOS и Android. В статье Дэвид делится своими наблюдениями о том, какую работу программист может и должен поручать большим языковым моделям, какие подводные камни есть в этом искусстве, и как оно может развиваться в ближайшие годы. Далее — от автора.

Обратная разработка аппаратного обеспечения бывает очень сложна — но иногда для неё может потребоваться только уютное кресло и Google Translate.

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

Недавно юный предприниматель взбаламутил соцсети, заявив, что приобретённый им в Китае девайс для подключения Ethernet-to-USB сразу был начинён вредоносом, который «ускользал от виртуальных машин», «считывал клавиатурный ввод» и «использовал характерные русскоязычные элементы».

Считайте, что я этого не говорил.

Если я хочу посмотреть видео — разве для этого обязательно покидать vim?

Что ж, прямо в заголовке этого поста я пообещал вам продемонстрировать Bad Apple в vim, пользуясь только поисковыми запросами. Вот Bad Apple в vim, всё, что здесь меняется — только поисковый запрос:

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

Не могу подобрать идеального названия для этого явления, так что буду называть его просто «эффект Makefile». Эффект Makefile не назовёшь однозначно порочным — просто нужно иметь его в виду при проектировании инструментов и систем.

Суть эффекта Makefile сводится к следующему:

В ходе нашего исследования, охватывавшего записи SPF, DKIM и DMARC на 1 миллионе самых популярных веб-сайтов мы с удивлением обнаружили более 1 700 открытых DKIM-ключей длиной менее 1 024 бит каждый. Эта находка нас удивила, поскольку RSA-ключи короче 1 024 бит расцениваются как небезопасные, и их не рекомендуется использовать в DKIM с 2018 года, когда был введён в действие документ RFC 8301.

Просто из любопытства мы решили проверить, а удастся ли нам взломать один из таких ключей. Мы стремились извлечь закрытый ключ из открытого RSA-ключа, так, чтобы можно было подписывать им электронные сообщения, выдавая себя за их подлинного отправителя. Кроме того, нас занимало, пройдут ли DKIM-верификацию электронные письма, подписанные таким скомпрометированным ключом. Мы решили проверить крупнейших провайдеров электронной почты —  в частности, Gmail, Outlook.com и Yahoo Mail — вдруг они просто с порога откажутся проверять цифровые подписи, сгенерированные настолько коротким ключом.

Для нашего эксперимента мы выбрали домен redfin.com, на котором нашли 512-разрядный открытый RSA-ключ по адресу key1._domainkey.redfin.com (сейчас он уже не доступен):

Ответ: да! И вот же он:

Игра запускается, и вы можете перемещаться по миру 64x64x64 при помощи клавиш WASD. Пробелом прыгаем, мышью осматриваемся. Щёлкнув левой кнопкой мыши, можно разрушить блок, а правой — установить землю.

Можно просмотреть QR-код при помощи следующей команды под Linux:

zbarcam -1 --raw -Sbinary> /tmp/m4k &&chmod +x /tmp/m4k  && /tmp/m4k

-1: выйти после того, как код будет просканирован

--raw: не обрабатывать его как текст

--Sbinary: воспользоваться двоичной конфигурацией

Проект выложен на GitHub здесь:TheSunCat/Minecraft4k

Ассемблерные вставки, используемые компиляторами GCC и Clang, опосредуют взаимодействие высокоуровневых и низкоуровневых языков программирования. Это тонкая и коварная штука. Многие попадают в расставленные здесь капканы, зачастую совершенно неожиданно для себя. В сущности, ключевое слово asm можно перевести на C и C++ как unsafe. Почти в любых руководствах по встроенному ассемблеру, в том числе, и на ужасной странице ibilio, которая десятилетиями попадает в самый верх поисковой выдачи, неисправимо фигурируют фундаментальные серьёзные ошибки, а примеры в большинстве своём некорректны. Наиболее опасно, что эти примеры обычно приводят к ожидаемым результатам! Ситуация плачевная. Эта статья — не руководство, а подборка элементарных правил, которые помогут вам избежать самых распространённых ошибок либо отловить их при ревью кода.

Здесь мы сосредоточимся сугубо на расширенном, а не на базовом ассемблере, а правила в этих версиях отличаются. На первом пишут любые инструкции, относящиеся к встроенному ассемблеру, с ограничениями или затираемыми. То есть, имеем токен : в обрамлении asm. Базовый ассемблер — тупой инструмент, который используется сравнительно нечасто, в основном в самом верху файла с кодом или в “голых” функциях. Поэтому злоупотребления базовым ассемблером на практике маловероятны.

Возможно, вы слышали о финансовой стратегии ставок по методу Келли. Это система, позволяющая оборачивать себе на пользу известную информацию в азартной игре или связанные с ней предубеждения. Эта стратегия также называется максимально агрессивной или стратегией высокой дисперсии. Дело в том, что если сделать ставку выше, чем позволяет предел Келли, то последствия могут быть катастрофическими.
Недавно мне попалась странная карточная игра, в которой стратегия Келли абсолютно не подразумевала риска, поскольку в игре действует Нулевая дисперсия. В своей знаменитой книге «Математические головоломки» Питер Уинклер называет её «Next Card Bet» («Следующая карточная ставка»). Саму задачу и её решение, по-видимому, сформулировал Томас Кавер. Мне понравилась как сама эта игра в ставки, так и её анализ, поэтому я поделюсь ими с вами здесь.

Почему я это написал, и как читать статью

Недавно получил от друга такое сообщение:

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

Я сразу же подумал: «Ну конечно, я знаю тысячу статей и видеороликов на эту тему», но вскоре осознал, что практически во всех таких источниках от читателя требуется знать компьютерный жаргон, внутреннее устройство, промежуточные представления, т.д. Вот какая проблема здесь возникает: те, кто пользуется компиляторами (как, например, мой друг), всем этим не заморачиваются. Их не волнует, каково именно промежуточное представление LLVM, или что такое φ-узел, или какой проход и почему называется «ротацией циклов». Нет, их интересуют (в порядке убывания приоритета) ответы на вопросы: (1) что, (2) почему, (3) как.

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

Я работаю в компании Nomic, и многие из моих коллег заняты созданием больших TSNE-подобных визуализаций, работающих в браузере. При визуализации таких двумерных карт возникает две проблемы: проецировать эти конструкции (напр. TSNE и UMAP) в 2D-координатную систему протекает медленно и требует больших затрат оперативной памяти, особенно по мере того, как вы увеличиваете датасет и пытаетесь визуализировать в браузере миллионы точек данных, не расплавив при этом ноутбук невзначай.

Отобразить в браузере миллионы точек данных, не расплавив компьютер — та ещё задача. Мне доводилось слышать, что многие проблемы с масштабированием удаётся решать при помощи инструмента Deepscatter, разработанного Беном Шмидтом.

Но многие из таких разговоров, которые мне известны, вертятся вокруг Typescript и великолепия WebGPU как такового. Готовя эту статью, я не смог найти ни одной библиотеки для автоматического дифференцирования выражений, которая была бы написана с применением WebGPU. Но было бы упущением не назвать здесь два репозитория с функционально схожим наполнением: webGPT (библиотека на основе трансформеров, приспособлена только для логического вывода) и webgpu-blas (ядра для быстрого перемножения матриц под webGPU). Поэтому, в качестве самообразования и желая получше изучить WebGPU и Typescript, я решил написать Surfgrad, высокопроизводительную библиотеку для автоматического дифференцирования выражений под управлением WebGPU. Она обеспечивает тензорные операции в браузере. Как понятно по названию и по принципу работы, она во многом сделана по примеру tinygrad и micrograd.

Если в этом посте вам в основном интересно, как что ломается, сразу можете переходить к последнему разделу.

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

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

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

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

Оказалось, что тема суммирования целых чисел в кодировке ASCII в Haswell со скоростью memcpy гораздо популярнее, чем я мог ожидать. Именно поэтому я решил поучаствовать и в другом челлендже в жанре HighLoad: подсчёт uint8. В настоящее время я занимаю всего лишь 13 место в списке лидеров, проигрываю первому месту около 7%, но уже узнал немало интересного. В этом посте я полностью опишу моё решение, в том числе, удивительный паттерн считывания из памяти. Используя его, можно примерно до 30% (по сравнению с обычным последовательным доступом) повысить скорость передачи в контексте одноядерных рабочих нагрузок, ограниченных размером кэша. По-видимому, этот метод малоизвестен.

Как и в других постах автора, программа настроена для следующих входных характеристик высоконагруженной системы: Intel Xeon E3-1271 v3 @ 3,60 ГГц, ОЗУ 512 МБ, Ubuntu 20.04. В ней используется только AVX2, а AVX512 не используется.

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

В большинстве современных приложений с ИИ в той или иной форме внедрена технология RAG (генерация с дополненной выборкой). Сейчас она у всех на слуху — о ней даже написали страницу в Википедии! Не знаю, ведёт ли кто-нибудь статистику, как быстро термин обычно дозревает до собственной статьи в Википедии, но термин RAG определённо должен быть где-то в топе этого рейтинга.

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

То приложение, разработкой которого мой друг занимался пару последних недель, работает с обширными данными из интернет-магазина: это описание различных товаров, инвойсы, отзывы, т. д. Вот с какой проблемой он столкнулся: оказалось, RAG не слишком хорошо обрабатывает некоторые запросы, но с большинством запросов справляется отлично.

За последние пару лет я успел заметить одну выраженную черту разработчиков, привыкших действовать в области традиционного (детерминированного) программирования: им очень сложно перестроиться на осмысление задач в статистическом контексте, а именно так и следует подходить к программированию приложений с большими языковыми моделями, суть которых — это статистика. Статистика «хаотичнее» традиционной информатики и подчиняется иным правилам, нежели алгоритмы обычной computer science. К чему я клоню: статистика — это по-прежнему математика, но очень своеобразная математика.  

Недавно мне довелось работать над новым алгоритмом приближённого поиска ближайших соседей, который называется RaBitQ. Автор этого алгоритма уже предоставил достаточно скоростную реализацию на C++. Я попытался переписать этот алгоритм на Rust (ещё один случай «а почему бы не переписать на Rust»). Однако, я обнаружил, что моя реализация гораздо медленнее оригинальной. Далее я расскажу, как шаг за шагом доработал её производительность.