Hacker News Digest

• Исправления

  • Уточнено сообщение об ошибке с некорректной терминологией. (Louis Pilfold)
  • JS: устранён сбой при использовании echo в модуле с функцией process. (Peter Saxton)
  • Форматер: не переносит комментарий перед assert за него; корректно форматирует сообщения после echo/panic/todo/assert/let assert с комментарием перед ними; компилятор не генерирует неверный код для assert с пайпами на JS. (Giacomo Cavalieri)

• Форматирование битовых массивов

  • Трейлинг-Запятая управляет разбиением: с запятой — много строк; без — в одну строку.
  • Если несколько сегментов на строке и убрана завершающая запятая, форматер сохраняет сегменты по одному на строку. (Giacomo Cavalieri)

• Компилятор и генерация кода

  • echo поддерживает пользовательское сообщение: echo 11 as "lucky number" печатает контекст и значение в stderr. (Giacomo Cavalieri)
  • В сгенерированном JS doc-комментарии превращаются в JSDoc. (Giacomo Cavalieri)
  • Уменьшен размер кода case на JS. (Surya Rose)
  • Удаление неиспользуемого кода на этапе генерации (usage-based DCE). (Louis Pilfold)
  • Улучшена поддержка echo для списков символов, ошибок и циклических ссылок JS. (Louis Pilfold)
  • Улучшен внешний вид ошибок и предупреждений: контекстные метки выделяются иначе, чем источник проблемы. (Giacomo Cavalieri)
  • Подсказка при импорте с точкой вместо слеша, с примерами корректного синтаксиса. (Zij-IT)
  • Предупреждение при затенении импортированного имени верхнеуровневой константой/функцией. (Aayush Tripathi)
  • Улучшено сообщение об неизвестной переменной, если, вероятно, имелась в виду проигнорированная (_x → x), с подсказкой. (Giacomo Cavalieri)
  • Оптимизирован матчинг-паттернов на JS.

• Обсуждение посвящено релизу Gleam: многие хвалят дизайн языка, читаемость, статическую типизацию и паттерн-матчинг; приводят пример кода и делятся позитивным опытом использования в проектах.
• Есть ссылки на пост о версии 1.12.0 и доклад на YouTube; некоторые ждут дальнейшего созревания экосистемы и возможности шаринга кода между фронтендом и бэкендом.
• Критика: отсутствие интерфейсов/тайпклассов и оператора композиции; кому-то синтаксис и «Error -> Error» кажутся неэлегантными; snake_case непривычен после TypeScript.
• В ответ отмечают осознанную простоту языка и официальную позицию Gleam по отказу от тайпклассов.
• Существенная часть треда уходит в спор о «идеологичном» футере сайта (инклюзивность, антинацистская позиция, права транс-людей): часть считает это лишним, другие — важным для безопасности и качества сообщества.
• Подчеркивается, что Gleam — это не только язык, но и сообщество с явным кодексом поведения; отсутствие позиции тоже является позицией.
• Некоторые участники призывают вернуться к техническим темам релиза, чтобы не повторять одни и те же дискуссии.

Дэн Бертон, владелец Urban Trapping Wildlife Control в Салинасе, вскрыл дикого кабана и обнаружил «неоново‑синее, как черника» мясо. Он сообщил в округ Монтерей и Департамент рыбы и дичи Калифорнии (CDFW). Власти предупреждают охотников и трапперов: возможное загрязнение мясной ткани связано с поеданием животными антикоагулянтного родентицида дифацинола, широко применяемого в сельском хозяйстве против крыс, мышей и сусликов.

По данным CDFW, синий оттенок в мышцах и жире — повод не употреблять добычу (кабан, олень, медведь, гуси) и сразу сообщать о находке. Хищники и люди могут получить «вторичное воздействие», так как токсин сохраняется в органах и тканях отравленного животного. Обычно для токсической дозы требуется несколько кормлений, но возможны симптомы вроде вялости.

• Обсуждение касается диких свиней с неоново‑синей окраской мяса, что, как отмечают многие, связано с поеданием родентицидов, содержащих синий трифенилметановый краситель для идентификации яда.
• Пользователи подчеркивают риск вторичного отравления: яды поражают не только крыс, но и хищников, домашних животных и людей через пищевые цепочки; приводятся личные трагические примеры.
• Отмечена высокая разрушительность и инвазивность диких свиней для сельского хозяйства, их сверхбыстрая репродукция и потому активные меры по контролю численности (лов, отстрел и др.).
• Критикуют кликбейтные заголовки; предлагают более информативные формулировки и уточняют, что в Калифорнии уже ограничивают/запрещают некоторые яды из‑за воздействия на дикую природу.
• Дискуссия затрагивает альтернативы ядам (например, программы “community cats”) и важность предупреждать соседей при использовании отрав.
• Уточняют, что синее мясо обнаружили при отлове и эвтаназии свиней по заказу агрофирмы; обычно мясо могли бы пожертвовать, но в таких случаях это опасно.
• Некоторые участники делятся ссылками, замечаниями о слабом качестве репортажа и шутками, но общий вывод: причина синевы известна — краситель в родентицидных приманках и связанные с этим экологические риски.

• Логотип Multics

• Домой

  • История »
    • Возможности
    • Мифы
    • Project MAC
    • Даты
    • Глоссарий
    • Проект истории
    • Последний сайт
  • Люди »
    • Истории
    • Фотографии
    • Юмор
    • Памятные вещи
  • Библиотека »
    • Статьи и доклады
    • Технические статьи
    • Документы разработки
    • Исходники
    • Симулятор
  • Сайты »
    • Хронология площадок
    • AFDSC (Пентагон, Вашингтон)
    • ASEA (Вестерос, Швеция)
    • Avon (Бристоль, Англия)
    • Bell Canada (2 площадки)
    • CISL (Кембридж, Массачусетс)
    • CNO (Миннеаполис, Миннесота)
    • DND-H (Галифакс, Канада)
    • DOCKMASTER (АНБ, Мэриленд)
    • FORD (Детройт, Мичиган)
    • GM (Детройт, Мичиган)
    • Майнц (Германия)
    • MIT (Кембридж, Массачусетс)
    • NWGS (ВМС США, 4 площадки)
    • OU (Рочестер, Мичиган)
    • PRHA (Сан-Хуан, Пуэрто-Рико)
    • RADC (Рим, Нью-Йорк)
    • RAE (Фарнборо, Англия)
    • STC (Лондон, Англия)
    • System-M (Финикс, Аризона)
    • Systeme X (Лувесьен, Франция)
    • UC/ACTC (Калгари, Канада)
    • USGS (3 площадки)
    • USL (Лафайет, Луизиана)
    • VPI (Блэксберг, Вирджиния)
  • О сайте »
    • Изменения
    • Новости
    • Ссылки
    • Галерея
    • Карта сайта

• Поиск

• Меню: История: Возможности | Мифы | Project MAC | Даты

• Участники обсуждают влияние Multics на современную вычислительную технику: от безопасности и архитектуры до наследия в текущих проектах (например, STOP, происходящий от SCOMP/STOP).
• Делятся воспоминаниями об использовании Multics в британских университетах в 80-х: система считалась быстрой, апгрейды памяти были ощутимыми, доступ через терминалы и JANET, позитивный опыт работы.
• Мнения расходятся: одни критикуют «всеобъемлющесть» дизайна и сложность (в контраст к UNIX), другие подчёркивают сильные стороны Multics — кольца защиты, строгие политики доступа (MAC/ACL), сегментную память и отсутствие переполнений буфера.
• Отмечают ограниченную портируемость Multics к немногим мэйнфреймам, несмотря на теоретическую переносимость.
• Ссылаются на полезные ресурсы: мифы о Multics, оценка безопасности B2, страницы по безопасности данных (AIM/MAC), «Три вопроса» для анализа багов, меморабилии, хронологии и список недавних изменений.
• Обсуждают спад активности оригинальных установок (последние закрытия около 2000 г.), эмулятор DPS8M и печальные новости об уходе участников проекта.
• Несколько комментаторов переосмыслили роль UNIX после знакомства с историей Multics и более ранними идеями (Xerox PARC), видя в Multics самостоятельную и богатую идеями систему, а не только «предтечу UNIX».

Far better to promote device controls than service ID checks.* It allows parents to decide what age to allow kiddo to see certain content, not the state.* It allows others to restrict content too. E.g. a gambling addict who doesn't want to see gambling content.* It has no risk of

Google представила Jules — асинхронного ИИ-агента для программирования — для всех пользователей, завершив публичную бету. Агент выполняет задачи в фоновом режиме: пишет и рефакторит код, правит баги, настраивает пайплайны и документирует изменения, не требуя постоянного участия разработчика. Это помогает параллелить работу, ускорять итерации и снижать контекстные переключения.

Jules интегрируется с инструментами разработчиков, может брать на себя длинные задачи, делить их на шаги, сообщать о прогрессе и запрашивать уточнения только при необходимости. Доступен через Google Labs и ориентирован на повышение продуктивности как отдельных инженеров, так и команд, позволяя запускать больше экспериментальных веток и быстрее проводить ревью.

• Пользователи жалуются на запутанные подписки Google: разные продукты (Jules, Gemini App/CLI, Code Assist) разбросаны между Workspace и GCP, цены и доступ скрыты или требуют согласий и биллинга.
• Опыт с Jules противоречивый: часть считает его слабее Claude Code, Copilot/Claude Sonnet и Gemini CLI (низкое качество кода, проблемы в монорепо, зацикливание, отсутствие кнопки STOP, баги UI), другие довольны асинхронным форматом и считают удобным для пачек задач, тестов и сайд‑проектов.
• Замечены регрессии: лимит задач на бесплатном плане снизили с 60 до 15; качество, по словам некоторых, упало после увеличения дневных лимитов на раннем превью.
• Пользователи хотят интеграции с GitHub (issues, комментирование PR для фидбэка), явного просмотра публичных улучшений кода и лучшей связности с Gemini CLI/Actions.
• Есть путаница в позиционировании: что такое «асинхронный кодовый агент», чем Jules отличается от Gemini CLI и с кем он конкурирует (Claude Code, Codex, Crush).
• Критика брендинга/UX: «детский» лендинг, слабый контраст, плохой пиксель‑арт; общее ощущение, что UI отстает от возможностей модели.
• Итоговое восприятие: интерес к формату асинхронных агентов есть, но текущая реализация Jules часто уступает Claude Code по скорости/качеству и стабильности; пользователи просят прозрачные тарифы и единый продуктовый опыт.

Это вторая часть серии о разработке Tyr — современного GPU‑драйвера на Rust для ядра Linux с поддержкой Arm Mali на CSF.

Разберем, как работают GPU‑драйверы, на примере VkCube — простого приложения на Vulkan, рисующего вращающийся куб. Простота сцены помогает понять путь данных и команд от приложения к GPU.

UMD и KMD

• UMD (usermode) реализует API вроде Vulkan/OpenGL/OpenCL и преобразует команды приложений в низкоуровневые команды для GPU. В нашем случае это panvk из Mesa.
• KMD (kernel mode) соединяет UMD с железом: инициализирует устройство, управляет памятью, очередями, планированием и уведомлениями. В нашем случае это Tyr, нацеленный попасть в основное дерево Linux.

Что делает UMD

• Подготавливает данные: геометрию, текстуры, машинный код шейдеров, матрицы трансформаций.
• Просит KMD разместить их в памяти GPU, создает VkCommandBuffer с командами отрисовки, настраивает состояние конвейера, указывает, куда писать результат, и как получать сигнал о завершении.

Про шейдеры

• Это полноценные программы на GPU. Для VkCube им нужны хотя бы геометрия, цвета и матрица вращения, чтобы расположить и раскрасить куб и крутить его.

Что делает KMD

• Выделяет и отображает память, изолируя процессы в отдельных контекстах/VM.
• Принимает работу от UMD, ставит в аппаратные очереди, отслеживает зависимости и завершение.
• Планирует выполнение на массово параллельном, асинхронном железе, соблюдая порядок и справедливое распределение ресурса между клиентами.
• Инициализирует устройство: тактирование, питание, стартовые процедуры; обеспечивает совместный и честный доступ приложений к GPU.

Ключевой вывод

• Основная сложность — в UMD, который переводит высокоуровневые API в команды GPU. Но KMD обязан предоставить надежные примитивы: память, очереди, синхронизацию, планирование и разделение ресурсов, чтобы UMD было реально реализовать.

Интерфейс драйвера

• На основе этих задач KMD экспонирует минимальный набор операций: запрос сведений об устройстве, создание/уничтожение VM, привязка/отвязка памяти к VM, получение состояния VM, отправка работ в очереди и механизмы уведомлений — тот же API, что у C‑драйвера Panthor для того же железа.

• Обсуждение статьи о драйвере GPU: часть читателей хвалит материал, но считает его слишком коротким и ждёт продолжения/второй части.
• Уточняют, что речь идёт о драйвере panthor для Mali CSF (на RK3588), а не panfrost; один из комментаторов отмечал баги в Firefox на RK3588, ему ответили про соответствующий драйвер.
• Спор о фокусе: одни подчёркивают важность того, что это один из первых GPU-драйверов Linux на Rust; другие критикуют кликбейт заголовок и считают, что нужно акцентировать Mali CSF, а не Rust.
• Техническая дискуссия: вопрос о целесообразности uring_cmd вместо ioctl; ответы поясняют, что из-за природы асинхронных очередей GPU дополнительная CPU-очередь мало что даст, а интерфейс драйвера следует ожиданиям Mesa.
• Отмечают, что текущая часть охватывает в основном границу пользователь/ядро и управление очередями/буферами; «основное действие» — выполнение команд GPU — ожидается в следующих частях.
• Дополнительно подчёркивают сложность современных GPU-драйверов и их объём в ядре Linux, что оправдывает выбранные подходы и терминологию.

• За 3 месяца мы масштабировали «мышление» Qwen3-4B: выше качество и глубина рассуждений. Представляем Qwen3-4B-Thinking-2507:

  • Существенно лучше на задачах логики, математики, науки, кода и академических бенчмарках.
  • Улучшены общие навыки: следование инструкциям, инструменты, генерация текста, согласование с предпочтениями.
  • Расширено понимание длинного контекста: 256K.
  • Версия с увеличенной длиной «мышления» — рекомендуем для сложных задач.

• Обзор модели:

  • Тип: Causal LM; Этапы: пре-/посттренировка.
  • Параметры: 4.0B (без эмбеддингов 3.6B); Слоёв: 36; GQA: 32 Q / 8 KV.
  • Контекст: 262 144 токенов.
  • Поддерживается только режим «thinking»; enable_thinking=True не нужен. Шаблон чата добавляет <think> автоматически; нормален вывод, содержащий только </think>.
  • Подробности: блог, GitHub, документация.

• Производительность (избранное):

  • Знания: MMLU-Pro 74.0; MMLU-Redux 86.1; GPQA 65.8.
  • Рассуждения: AIME25 81.3; HMMT25 55.5; LiveBench 71.8.
  • Код: LiveCodeBench v6 55.2; CFEval 1852; OJBench 17.9.
  • Алайнмент: IFEval 87.4; Arena-Hard v2 34.9; WritingBench 83.3.
  • Агенты: BFCL-v3 71.2; TAU1/2 — лучшие в ряде доменов.
  • Мультиязычность: MultiIF 77.3; PolyMATH 46.2.
  • Примечания: выигрыш на Arena — GPT-4.1; для сложных задач — вывод до 81 920 токенов, иначе 32 768.

• Быстрый старт:

  • Нужен свежий transformers (иначе KeyError: 'qwen3').
  • Пример кода: загрузить AutoTokenizer/AutoModelForCausalLM, применить chat template, сгенерировать до 32 768 новых токенов, выделить «thinking»-часть до токена </think> (ID 151668) и основное содержимое.
  • Для продакшна: sglang>=0.4.6.post1 или vllm>=0.8.5; можно поднять OpenAI-совместимый сервис.

• Обсуждают малый открытый модель Qwen3-4B (в т.ч. «Thinking/Instr»), её доступность в LM Studio и на Hugging Face, возможность запуска на ПК, Mac (mlx 4–8 бит) и даже на слабом железе; полный контекст 262k токенов может требовать десятки ГБ RAM.
• По отзывам: модель быстрая, компактная и по многим бенчмаркам заметно улучшена; в ряде метрик приближается к старой 30B MoE-версии при ~7,5× меньшем размере, но новая 30B-A3B всё же сильнее.
• Практический опыт: хороша в анализе задач, но встречаются галлюцинации в предложениях/советах.
• Идёт сравнение с Gemma 3n: на общих тестах (напр. AIME, LiveCodeBench) Qwen3-4B-Thinking показывает значительно более высокие результаты.
• Обсуждают надёжность метрик: многие бенчмарки оцениваются GPT‑4.1; возникают вопросы о возможной адаптации моделей под «угодные» ответы и нехватке ручного аудита.
• Для «народных» оценок советуют LM Arena, Artificial Analysis, OpenRouter stats и r/LocalLlama, но подчёркивают ограниченную надёжность толпы.
• Вопросы пользователей: как соотносится контекст и RAM; варианты для iPhone/Apple Silicon; ссылки на готовые gguf и mlx-сборки предоставлены.

Представьте, вы пишете проект и вам нужна библиотека — назовем ее libpupa.

Вы находите текущую версию 1.2.3 и добавляете в зависимости: "libpupa": "1.2.3" Автор libpupa 1.2.3 в свою очередь зависел от liblupa версии 0.7.8 и записал это: "liblupa": "0.7.8" То есть libpupa 1.2.3 навсегда зависит от liblupa 0.7.8. Алгоритм разрешения зависимостей простой и детерминированный: берем версии верхнего уровня, затем версии их зависимостей, и так далее. Достаточно указать только верхние уровни — транзитивные получатся одинаковыми всегда. Зачем отдельный lockfile?

Но люди изобрели lockfile из‑за диапазонов версий. Диапазоны делают сборку зависимой от времени: сегодня вы получите liblupa 0.7.8, через 10 минут — 0.7.9. Это определяется не при публикации, а при сборке: вы можете подтянуть версию, которой не существовало на момент выпуска libpupa 1.2.3. Откуда автор libpupa знает, что будущая 0.7.9 не сломает его код? Семантическое версионирование — это лишь намек, не гарантия.

И смешно то, что эти диапазоны все равно «замораживают» в lockfile, и вы не получаете предполагаемой пользы. «Перегенерируй lockfile и обновись» — это ничем не отличается от обновления верхнеуровневых зависимостей. «Lockfile решает конфликты версий?» — нет: библиотека либо работает с новой версией, либо нет; запись «0.7.*» не помогает — все равно нужно выбрать рабочую версию.

«Но раз lockfile существует, значит, нужен!» — не обязательно. Пример: Maven. Экосистема Java 20 лет обходится без lockfile, при этом тянет сотни библиотек — и все детерминировано.

Вывод: lockfile усложняет без достаточных причин. Менеджеры зависимостей могут работать без него.

UPD: В Maven при конфликте транзитивных зависимостей выбирается версия, ближайшая к корню. Это детерминированно и позволяет переопределять версии. Если вышла d 2.1 с патчами безопасности, добавьте ее в корень — она и будет выбрана, не дожидаясь обновлений у всех. Если автоматически брать самую большую версию, вы потеряете возможность переопределения.

• Обсуждение крутится вокруг необходимости lock-файлов и версионирования: одни считают, что фиксированные версии и детерминированные алгоритмы достаточно, другие настаивают, что lock-файлы критичны для воспроизводимости и безопасности.
• Приводят примеры из экосистем Maven/Java, Go (MVS), Cargo/Rust, .NET, Scala: у каждого свои компромиссы; даже при детерминированном резолве сеть/репозитории делают сборки недетерминированными без lock-файлов и хэшей.
• Аргументы за версии-диапазоны: автоматическое получение патчей безопасности без вмешательства авторов верхнеуровневых библиотек; но это ломается при конфликтующих транзитивных зависимостях и несовместимых API/ABI.
• Много комментариев о том, что lock-файлы особенно нужны приложениям (прод, стейджинг, аудит), а для библиотек — меньше, но всё равно полезны из-за пересборок и целостности (хэши артефактов).
• Подчёркивают проблемы разных языков: в компилируемых — типы из разных версий несовместимы; в JS Node могут сосуществовать несколько версий, но это не решает безопасность/детерминизм.
• Некоторые отмечают, что главная путаница — не в lock-файлах, а в культуре семвера, централизованных репозиториях и UX инструментов; предлагают BOM/snapshot-подходы и периодические обновления с тестами/реновейтом.
• Отдельная ветка критикует дизайн сайта с анимированными иконками, мешающими чтению.

Введение

Я часто использую отладчик, но привык и к выводной отладке, особенно в юнит-тестах. Хотелось улучшить её и чаще подключать отладчик.

Улучшение выводной отладки

Главная проблема — «шум»: в цикле интересна одна итерация, а печатается всё. Или удобнее читать форматированную структуру, но приходится раскидывать print’ы по коду. В Zig тесты используют error’ы, значит можно печатать только при падении теста через errdefer:

test { errdefer std.debug.print("{f}", .{ast}); // ... }

Так контекст появляется только при ошибке, без засорения лога.

Запуск тестов в отладчике

Просто запустить seergdb или gdb -tui неудобно: тестовые бинарники лежат в zig-cache. Трюк из ziggит: build.zig может запускать команды и передавать путь артефакта:

// seergdb — GUI фронтенд для gdb const debugger = b.addSystemCommand(&.{ "seergdb", "--run", "--" }); debugger.addArtifactArg(exe_unit_tests);

const debug_step = b.step("debug", "Run unit tests under debugger"); debug_step.dependOn(&debugger.step);

Это запускает правильный бинарник. Но отладчик сработает лишь на брейкпоинте или панике, тогда как раннер тестов «проглатывает» ошибки.

Комбинация трюков

Добавим @breakpoint через errdefer:

test { errdefer @breakpoint(); }

Так мы попадаем в точку ошибки, видим контекст и вывод std.testing.expect*. Минус: при zig build test отчёт показывает падение всего шага тестов, а не отдельных кейсов. Нужна возможность включать брейкпоинты выборочно.

Условная компиляция

Через build options пробрасываем флаг, решающий, вызывать ли @breakpoint в тестах.

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

const std = @import("std");

pub fn build(b: *std.Build) void { const target = b.standardTargetOptions(.{}); const optimize = b.standardOptimizeOption(.{});

const lib = b.addModule("zig-test-patterns", .{
    .root_source_file = b.path("src/root.zig"),
    .target = target,
    .optimize = optimize,
});

const options = b.addOptions();
options.addOption(bool, "debugger", false);
lib.addImport("config", options.createModule());

const mod_tests = b.addTest(.{ .root_module = lib });
const run_mod_tests = b.addRunArtifact(mod_tests);

const test_step = b.step("test", "Run tests");
test_step.dependOn(&run_mod_tests.step);

}

В коде тестов:

const std = @import("std"); const config = @import("config");

test "errdefer @breakpoint()" { errdefer if (config.debugger) @breakpoint(); return error.FixMe; }

test "no breakpoint" { return error.FixMe; }

zig build test — без брейкпоинтов. Но менять значение флага так — значит пересобирать build.zig. Добавим опцию прямо в систему сборки:

var options = b.addOptions(); const use_debugger = b.option( bool, "debugger", "Enables code intended to only run under a debugger", ) orelse false; options.addOption(bool, "debugger", use_debugger);

Теперь можно переключать поведением командой:

zig build -Ddebugger test

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

• Участники хвалят согласованность базовых конструкций Zig: минимализм синтаксиса и мощь comptime позволяют элегантные решения без излишней сложности.
• Особый интерес вызвал errdefer: многие отмечают, что это упрощает тесты и отладку; звучит мнение, что такую возможность «стоит иметь каждому языку».
• Обсуждают практики отладки: полезны советы по интеграции дебаггера в build.zig, что избавляет от ручного поиска исполняемого файла в кэше.
• Поднимается вопрос об ошибках без полезной нагрузки в Zig: при парсинге (например, JSON) типовые ошибки вроде UnexpectedToken недостаточно информативны; интересуются паттернами передачи дополнительного контекста.
• Есть замечание о смешении стилей именования (camelCase в stdlib vs snake_case у автора), что может сбивать с толку.
• Отмечают эстетику сайта и блога: шрифты (Berkeley Mono), цветовую схему и ретро-оформление — «как в старых DOS-играх».
• Проводится параллель с D: аналогичная идея реализована через scope(failure), что подчеркивает общность концепции.

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

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

Команда исследователей предложила новый алгоритм, который обходится без сортировки и работает быстрее всех «сортирующих» методов, преодолев сорокалетний барьер. Роберт Тарьян назвал результат поразительным.

Графы описывают вершины и ребра с весами (длина, время и т.п.). Задача: по данному источнику найти кратчайшие пути до всех вершин. Алгоритм Дейкстры (1956) идет «волной» наружу: зная оптимальные пути к ближайшим, находит пути к дальним. Но конечный результат — упорядоченный набор кратчайших расстояний, и потому скорость ограничена сортировкой. В 1984 году Тарьян с соавтором улучшили Дейкстру до этого предела: чтобы ускориться дальше, нужно избегать сортировки.

В конце 1990-х — начале 2000-х Торуп и другие обошли барьер для частных случаев, вводя ограничения на веса. Обобщить техники на произвольные веса не удавалось, и прогресс застопорился. Ран Дуань не согласился с пессимизмом и стремился сломать барьер для всех графов — и прошлой осенью добился цели.

Идея Дуани (созревшая к 2021 году): вместо того чтобы на каждом шаге сканировать всю «границу» уже исследованной области, как делает Дейкстра (что со временем замедляет ход), группировать соседние граничные вершины в кластеры и рассматривать по одному представителю из каждого. Это уменьшает число кандидатов и может вести не к ближайшей вершине — значит, зависимость от сортировки исчезает. Главная трудность — доказать, что кластеризация действительно ускоряет процесс на каждом шаге и в сумме.

За следующий год Дуань проработал идею и к осени 2022-го был уверен, что технические барьеры преодолимы.

• Обсуждение вокруг нового алгоритма SSSP с детерминированной сложностью O(m log^(2/3) n), который улучшает Дейкстру на разреженных графах; ссылку дали на arXiv: 2504.17033.
• Участники отмечают, что выигрыш зависит от структуры графа: для дорожных сетей обычно m ≈ c·n (c ~ 4–6 для ориентированных), что даёт O(n log^(2/3) n); для очень плотных графов (m ~ n^2) преимущество может исчезать.
• Возникают вопросы о сравнении логарифмических степеней, применимости к задачам вроде TSP с почти полными графами, и сохранении гарантии глобального минимума как у Дейкстры.
• Некоторые считают алгоритм сложнее Дейкстры, но отмечают теоретическую значимость прорыва и отсутствие «фancy math», что делает результат удивительным.
• Обсуждают возможные гибриды с рандомизацией и практическое влияние на реальные графы (улицы, геймдев).
• Есть скепсис о «позднем открытии» и комментарии про то, что практики могли бы дойти до подобных идей, но не оформляют их академически.
• Вспоминают вклад классиков (Тарjan и др.) и проводят аналогию с TimSort: практичная оптимизация поверх классики.