Миф о RAM — это верование о том, что память современного компьютера напоминает идеальную память с произвольным доступом. Кэш люди считают оптимизацией для малых данных: если они умещаются в L2, то будут обрабатываться быстрее; если нет, то тут уж ничего не поделаешь.

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

groups = [[] for _ in range(n_groups)]

for element in elements:

groups[element.group].append(element)

Он и в самом деле линеен (то есть асимптотически оптимален), и мы всё равно должны выполнять доступ к произвольным индексам, так что кэш здесь нам ни в чём бы не помог.

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

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

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

«Очевидный» выбор для этой задачи — Python, но Python API не так уж чудесен, а из-за динамической типизации мне понадобится слишком много времени на отладку. Поэтому я попробовал Java. Я знаю её API назубок; по крайней мере, то, что касается коллекций, файлов, regex и так далее. Java статистически типизируемая, поэтому я защищён от глупостей ещё на ранних этапах кодинга. А её среды разработки просто потрясающие.

Что вы говорите? Действительно ли я хочу создавать отдельный файл POM и иерархию src/main/java для каждого скрипта? Хм.

Нет, я этого не делаю. К счастью, современная Java и её инструменты этого не требуют. Давайте разбираться!

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

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

Всё вроде должно быть просто

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

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

В последнее время я думала о том, что всё, происходящее в терминале — это та или иная комбинация

Работы операционной системы

Работы шелла

Работы эмулятора терминала

Работы той программы, которая у вас запущена (например, top, vim или cat)

Первые три (операционная система, шел и эмулятор терминала) — это достаточно известные переменные: если вы пользуетесь bash в GNOME Terminal Linux, то можете более-менее представлять, как всё это взаимодействует, а часть их поведения стандартизирована POSIX.

Но четвёртый элемент («программа, которая у вас запущена») как будто бы может делать ЧТО УГОДНО. Как узнать, что будет из себя представлять поведение программы?

Пользователи играют в игры на устройствах с разными размерами экранов, так что при разработке игр очень важен адаптивный пользовательский интерфейс (User Interface, UI). Продуманный адаптивный UI обеспечивает идеальный внешний вид на любом экране. В Godot Engine есть широкий выбор настроек и нодов, упрощающих создание адаптивного UI.

В этом туториале вы научитесь пользоваться такими настройками и нодами. К концу туториала вы будете знать, как сделать UI адаптивным, и реализуете переключение между полноэкранным и оконным режимами.

Sega Channel — это сервис games-on-demand, предоставлявший абонентам кабельного телевидения ежемесячный доступ к библиотеке из примерно пятидесяти игр для Sega Genesis за помесячную оплату (обычно 10-15 долларов, в зависимости от поставщика услуг кабельного телевидения). Он работал с июня 1994 года (общий доступ по всем США включили в декабре 1994 года) по июнь 1998 года. Абонентам предоставлялся картридж-адаптер, подключавший их консоль Genesis к линии кабельного телевидения. При включении консоли картридж искал сигнал Sega Channel, а затем скачивал меню игр. Этот процесс обычно занимал примерно двадцать секунд. Затем пользователь выбирал игру и примерно минуту ждал, пока она загрузится в ОЗУ адаптера. Далее игра работала точно так же, как картридж из магазина. Отключение системы или нажатие кнопки меню на адаптере удаляло скачанную игру, но данные сохранений игры оставались в нём, пока пользователь не скачивал другую игру. Наряду с продававшимися в рознице играми в Sega Channel был раздел «Test Drives», в нём пользователи могли играть в урезанные по времени или контенту версии игр, которые позже выпускались в розничную продажу. Кроме того, было несколько игр, доступных только через Sega Channel, хотя по большей мере это были проекты, в качестве которых Sega или издатель были не уверены, а потому не хотели выпускать их на физических картриджах. Успех Sega Channel был довольно умеренным, на пике популярности на него были подписаны примерно 250 тысяч абонентов.

В последнее время я часто видел обсуждения репозитория сравнения языков. В нём CRuby был третьим снизу, обгоняя по скорости только R и Python.

Автор репозитория @BenjDicken создал забавную визуализацию производительности каждого из языков. В одной из визуализаций из визуализаций Ruby по бенчмаркам Ruby оказывается третьим с конца.

Помните сравнение потребления памяти для асинхронного программирования на популярных языках 2023 года?

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

Давайте снова проведём бенчмарки и изучим результаты!

Сейчас ведётся много споров и дискуссий о будущем C++.

Не только на Reddit и одном оранжевом веб-сайте, но и совершенно точно на официальных заседаниях комитета по стандарту C++.

Абсолютное состояние (языка C++)

Похоже, мы находимся в следующей ситуации:

Evolution Working Group (EWG) языка C++ как раз достигла консенсуса по внедрению P3466 R0 - (Re)affirm design principles for future C++ evolution:

Это означает отсутствие поломок ABI, сохранение совместимости компоновки с кодом на C и предыдущими версиями C++.

Также это означает отсутствие «виральных аннотаций» (например, аннотаций времени жизни).

Удвоение усилий по множеству несовместимых задач, например, отсутствия поломок ABI и принципа zero overhead.

Плохо это или хорошо, но это (в буквальном смысле) удвоение усилий по развитию текущей траектории языка C++.

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

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

Одна из проблем заключается в том, что для преобразования перехваченных сырых данных печати в растровое изображение требуется достаточно долгая настройка. В каком-то оборудовании применяется HP PCL, в другом — Encapsulated Postscript (EPS), а если повезёт, то вывод будет в стандартном растровом формате наподобие PCX.

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

Возможно, пост будет не очень полезен остальным людям, но, может, кому-то он пригодится при гуглении… Как всегда, я работаю с Linux, что сказывается на ПО.

Этот проект начинался как обучающий: я хотел углубить свои знания в машинном обучении, и в частности в TensorFlow. В конечном итоге мне хотелось получить работающую в браузере модель машинного обучения, которая смогла бы надёжным образом (с точностью не менее 80%, а предпочтительно >90%) решала капчу 4Chan. Я достиг этих целей и расскажу в статье, каким образом мне это удалось!

Код я опубликовал на GitHub.

Недавно я закончил создание пасьянса для Nintendo E-Reader. Мне удалось уместить его на одной карте, и это практически полнофункциональная версия игры. Я очень доволен тем, что получилось.

Что такое E-Reader?

E-Reader — это периферийное устройство для Game Boy Advance, выпущенное компанией Nintendo в 2002 году. Сканируя карты, где есть полоска с кодом из точек, можно загружать мини-игры, дополнительные уровни, анимации и так далее.

В своём последнем посте я говорил об одной загадке: все большие языковые модели (LLM) ужасно играют в шахматы. Все, за исключением gpt-3.5-turbo-instruct, которая по какой-то причине умеет играть на уровне продвинутого любителя. И это несмотря на то, что этой модели больше года и она намного меньше новых моделей. Что происходит?

Я предложил четыре возможных объяснения:

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

Теория 2: по какой-то причине gpt-3.5-turbo-instruct обучали на большем объёме шахматных данных.

Теория 3: в некоторых архитектурах LLM есть нечто магическое.

Теория 4: существует «конкуренция» между разными типами данных, поэтому чтобы LLM могла хорошо играть в шахматы, большая доля данных должна быть информацией о шахматных партиях.

В Интернете нашлось ещё множество других теорий. Самые распространённые из них:

Теория 5: OpenAI жульничает.

Теория 6: на самом деле LLM не могут играть в шахматы.

Я провёл новые эксперименты. Хорошие новости — ошибались все!

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

BM25, или Best Match 25 — это широко используемый алгоритм полнотекстового поиска. Среди прочего, он по умолчанию применяется в Lucene/Elasticsearch и SQLite. В последнее время в рамках «гибридного поиска» часто начали комбинировать полнотекстовый поиск и поиск по схожести векторов. Мне захотелось понять, как работает полнотекстовый поиск и в частности BM25, поэтому в этой статье я постараюсь разобраться в этом.

В процессе разработки UI для игр Forza Horizon 3 и Forza Motorsport 7 я имел возможность поработать с потрясающими акриловыми матовыми элементами дизайна.

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

Хэш-функции — невероятно красивые математические объекты. Они могут отображать произвольные данные на небольшую область выходных данных фиксированного размера таким образом, что отображение оказывается детерминированным, хоть и кажется случайным. Такая «детерминированная случайность» невероятно полезна для широкого спектра применений, например, для хэш-таблиц, контрольных сумм, алгоритмов Монте-Карло, распределённых алгоритмов без коммуникаций и так далее.

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

Для затравки скажу, что в этой статье объясняется, как генерировать за секунду тысячи подобных строк:

cityhash64("orlp-cityhash64-D-:K5yx*zkgaaaaa") == 1337 murmurhash2("orlp-murmurhash64-bkiaaa&JInaNcZ") == 1337 murmurhash3("orlp-murmurhash3_x86_32-haaaPa*+") == 1337 farmhash64("orlp-farmhash64-/v^CqdPvziuheaaa") == 1337

Также я покажу, как можно создавать очень специфичные пары строк, которые можно произвольно конкатенировать таким образом, что при конкатенации k строк любая из 2k комбинаций будет иметь одинаковый хэш вне зависимости от использованного для хэш-функции порождающего значения (seed):

a = "xx0rlpx!xxsXъВ" b = "xxsXъВxx0rlpx!"
murmurhash2(a + a, seed) == murmurhash2(a + b, seed)
murmurhash2(a + a, seed) == murmurhash2(b + a, seed)
murmurhash2(a + a, seed) == murmurhash2(b + b, seed)
a = "!&orlpՓ" b = "yǏglp$X"
murmurhash3(a + a, seed) == murmurhash3(a + b, seed)
murmurhash3(a + a, seed) == murmurhash3(b + a, seed)
murmurhash3(a + a, seed) == murmurhash3(b + b, seed)

Упаковка 2D-прямоугольников в прямоугольники большего фиксированного размера необходима в большинстве мультимедийных проектов. В программировании GPU изменение текстур (binding) — затратный процесс. Поэтому при рендеринге текста не стоит использовать по одной текстуре на глиф, вместо этого желательно упаковать глифы в единую текстуру, называемую атласом. В 2D-играх содержащие спрайты атласы называются листами спрайтов (spritesheet). Листы спрайтов также используются для веб-сайтов, потому что скачивать один большой файл удобнее, чем по одному файлу на каждый значок/логотип.

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

Самым ценным ресурсом из найденных мной стал превосходный обзор Юкки Йулянки. В нём описано четыре типа алгоритмов и их практическая оценка. Выделяются из них два:

MAXRECTS если вы знаете заранее, какие прямоугольники будете упаковывать («офлайн-упаковка»)

SKYLINE если не знаете («онлайн-упаковка»)

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

Именно поэтому я остановился на алгоритме skyline. Он применяется в stb_rect_pack.h, fontstash, а значит, и в nanovg.

В этой статье объяснён алгоритм skyline и представлена его реализация. Реализация доступна онлайн и в общественном достоянии (UNLICENSE).

Пользователь Twitter @tthirtle спросил, почему установка Windows 95 проходит через три операционные системы: MS-DOS, Windows 3.1, а уже потом Windows 95. Почему не перейти от MS-DOS сразу к Windows 95?

Ещё один хороший вопрос: почему в установке Windows 95 используется три разных UI. DOS, Win3.x и Win9x?

— Thomas (@tthirtle) July 7, 2024

Установка Windows 95 может быть апгрейдом с трёх начальных точек: MS-DOS, Windows 3.1 или Windows 95. (Да, можно проапгрейдить Windows 95 до Windows 95. Это может понадобиться для того, чтобы восстановить повреждённую систему и сохранить при этом данные.)

Один из вариантов решения — написать три версии установки Windows 95: одна для установки из MS-DOS, другая для установки из Windows 3.1 и третья для установки из Windows 95.

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

Из Википедии: фактор автобуса (англ. bus factor, либо truck factor) проекта — это мера сосредоточения информации среди отдельных членов проекта; фактор показывает количество участников проекта, после потери которых (в оригинале — «попадания» которых под автобус или грузовик, варианты: увольнения, заболевания, рождения у них ребёнка, наступления несчастного случая и других форс-мажорных обстоятельств) проект не сможет быть завершён оставшимися участниками.

Мотивация

Во всех компаниях, где я работал (в строительстве и разработке ПО), в тот или иной момент времени возникал вопрос «фактора автобуса» в управлении разработкой проектов.

Инженеру-строителю вычислить его было крайне сложно, потому что наша отчётная документация была сильно распределена между сотрудниками и существовал дефицит документации. Единственный раз, когда это стало очевидно, случился после увольнения одного из сотрудников — спустя полгода возник срочный запрос RFI (запрос информации) по чьему-то пакету расчётов (хотя официальный пакет должен быть подписан инженером-проектировщиком, а не инженером, непосредственно отвечающим за расчёты). После таких инцидентов нам обещали улучшить документацию, но это неизбежно отходило на второй план, когда все участники группы переходили на новые проекты даже без итогового совещания. Я был свидетелем того, как в долговременных проектах инженерный состав менялся на 100%, поэтому это ужасный антипаттерн.

В разработке ПО можно провести множество параллелей, но по природе нашей работы поставка выпущенного кода — это единственный способ измерения фактора автобуса. По крайней мере, именно её изучали многие исследователи, в том числе и в научной статье, имеющей большое количество цитирований (156, согласно Google Scholar!) с момента её публикации в 2016 году (препринт выпустили в 2015 году). Ша отправил мне статью, а после того, как мы обнаружили её исходные данные и исходный код, это стало идеальным проектом на выходные, который бы позволил, как минимум, получить представление об интересных метриках open source.