Технологии

Алгоритм, который пережил три эпохи: как код 1957 года до сих пор работает в современном Linux

В 1957 году вышло второе издание книги "The Preparation of Programs for an Electronic Digital Computer" (Подготовка программ для электронного цифрового компьютера). Сегодня о ней мало кто помнит за пределами круга историков вычислительной техники. Однако один из фрагментов этой книги — несколько строк математических выкладок — продолжает работать в ядре операционной системы Linux и других современных проектах. Речь идёт об алгоритме подсчёта единичных битов в машинном слове, известном как population count (подсчёт населения) или Hamming weight (вес Хэмминга).

Что такое вес Хэмминга и зачем его считать

Любое число в памяти компьютера представлено последовательностью битов — нулей и единиц. Весом Хэмминга (Hamming weight) называется количество единичных битов в этой последовательности. Например, для числа 23 (двоичное представление: 10111) вес Хэмминга равен 4, поскольку четыре бита установлены в единицу.

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

Как отмечается в научной работе Wojciech Muła, Nathan Kurz и Daniel Lemire "Faster Population Counts Using AVX2 Instructions" (Более быстрый подсчёт населения с использованием инструкций AVX2, 2016, процитирована 93 раза): *"Быстрая и широко используемая функция сложения в виде дерева для вычисления population count была приписана Кнутом учебнику 1957 года Уилкса, Уилера и Гилла"* (источник: arxiv.org, статья 1611.07612).

Рождение алгоритма: первая книга по программированию

Книга Уилкса, Уилера и Гилла — сокращённо WWG (по первым буквам фамилий авторов) — была первой в мире книгой по программированию. Её первое издание вышло в 1951 году и шесть лет распродавалось тиражом, который по современным меркам показался бы смехотворным. Как сообщает издание Communications of the ACM (статья "In Praise of 'Wilkes, Wheeler, and Gill'" by Martin Campbell-Kelly, 2011): "На момент публикации WWG в мире было очень мало цифровых компьютеров. EDSAC, на котором основана книга, был первым в мире компьютером, предоставившим практические вычислительные услуги исследователям" (источник: cacm.acm.org, Communications of the ACM).

Книга описывала методы программирования для компьютера EDSAC (Electronic Delay Storage Automatic Calculator — электронный автоматический вычислитель с запоминающим устройством на линиях задержки), созданного в Кембриджском университете под руководством Мориса Уилкса.

На страницах 191–193 второго издания Дональд Б. Гиллис (Donald B. Gillies) и Джеффри С. П. Миллер (Jeffrey C. P. Miller) предложили метод, который Дональд Кнут (Donald Knuth) позже назовёт "Gillies-Miller method for sideways addition" (метод Гиллиса-Миллера для бокового сложения) (источник: Chessprogramming wiki, статья "Population Count").

Как работает битовая магия

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

  1. Сначала каждый бит «складывается» с соседним — результат помещается в 2-битовую группу
  2. Затем соседние 2-битовые группы суммируются в 4-битовые
  3. 4-битовые группы суммируются в 8-битовые (байты)
  4. В конце одно умножение собирает сумму всех байтов в старший байт результата

Вот как выглядит этот алгоритм на языке Си для 64-битных чисел (из исходного кода ядра Linux, файл `lib/hweight.c`):
unsigned long __sw_hweight64(__u64 w)
    {
        w -= (w >> 1) & 0x5555555555555555ul;
        w = (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul);
        w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful;
        return (w * 0x0101010101010101ul) >> 56;
    }
Всего 12 арифметических операций включают одно умножение — но для процессоров, где умножение выполняется за один такт (а для современных x86-процессоров это именно так), скорость оказывается впечатляющей. Как отмечается в статье на портале Habr: *"Очевидно, что битовая алхимия применяется вовсе не для того, чтобы блистать на собеседовании, а с целью существенного ускорения программ"* (источник: Habr, статья "Обстоятельно о подсчёте единичных битов", автор Zealint, 2016).

Инструкция POPCNT: аппаратный прорыв

В 2008 году компания Intel представила набор инструкций SSE4.2, в который вошла команда POPCNT (Population Count), выполняющая подсчёт единичных битов аппаратно за один такт. Вслед за Intel аналогичную поддержку добавила AMD.

В 2010 году в ядро Linux был включён патч разработчика Борислава Петкова (Borislav Petkov) с комментарием: *"Добавление поддержки аппаратной версии функции веса Хэмминга — popcnt, присутствующей в процессорах, которые сообщают о ней через CPUID. На процессорах без такой поддержки мы возвращаемся к программным версиям из lib/hweight.c"* (источник: Linux-Kernel Archive, lkml.iu.edu, патч "x86: Add optimized popcnt variants", 2010).

Синтетические тесты показали, что аппаратная инструкция POPCNT почти в три раза быстрее программной реализации на процессорах семейства AMD Family 10h (источник: там же).

Почему старый код не уходит

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

Первая причина — обратная совместимость. Далеко не все процессоры в мире поддерживают POPCNT. Как отмечается в обсуждениях на Linux-Kernel Archive (март 2025 года): некоторые архитектуры — ARM (без POPCNT), MIPS, старые модели RISC-V, а также процессоры x86, выпущенные до 2008 года — не имеют аппаратной поддержки. Для них программная реализация остаётся единственным вариантом.

Вторая причина — универсальность дистрибутивов. Большинство сборок ядра Linux предназначены для запуска на широком спектре процессоров. Как писал разработчик ядра Ингве Молнар (Ingo Molnar) в дискуссии о патчах POPCNT (Linux-Kernel Archive, март 2025): "-march=native может быть полезен для локальных экспериментов, но не достигнет 99.999% пользователей Linux". Поэтому ядро использует механизм ALTERNATIVE — при загрузке системы проверяется наличие инструкции POPCNT, и если она доступна, вызов программной функции заменяется на аппаратную инструкцию.

Третья причина — новые архитектуры. Развитие открытой архитектуры RISC-V и появление новых встраиваемых систем регулярно создаёт ситуации, когда аппаратная поддержка POPCNT отсутствует, но требуется эффективный программный подсчёт.

Современные дискуссии: 2025–2026 годы

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

Март 2025 года. Урос Бижяк (Uros Bizjak) из словенской компании, разрабатывающей компиляторы, предложил серию патчей для оптимизации файла `arch_hweight.h`. Изменение заключалось в замене директивы `asm()` на `asm_inline()` — эта, на первый взгляд, незначительная правка позволила уменьшить размер кода ядра на 171 байт и улучшить инлайнинг инструкций POPCNT.

Апрель 2025 года. Нэйтан Ченселлор (Nathan Chancellor) из команды LLVM поднял вопрос о добавлении в ядро Linux функций `__popcountsi2` и `__popcountdi2`. Проблема заключалась в том, что компилятор Clang начал автоматически заменять некоторые конструкции с подсчётом битов вызовами библиотечных функций, но ядро Linux не линкуется со стандартными библиотеками времени выполнения.

В ответ на это Линус Торвальдс (Linus Torvalds) заметил:
"Как только у вас появляются накладные расходы на вызов функции — со всеми играми регистров и прочим, — вы почти наверняка выиграете от простых безусловных битовых операций"* (источник: lkml.indiana.edu, переписка апреля 2025 года). Это высказывание подтверждает, что даже в эпоху аппаратных инструкций компактная программная реализация сохраняет актуальность.
Февраль 2026 года. В подсистему BPF (Berkeley Packet Filter — фильтр пакетов Беркли) добавлена поддержка 64-битных битовых операций, включая `bpf_popcnt64()`. JIT-компилятор BPF теперь умеет встраивать инструкцию POPCNT непосредственно в генерируемый машинный код на архитектуре x86_64 (источник: Linux-Kernel Archive, патч "bpf, x86: Add 64-bit bitops kfuncs support for x86_64", февраль 2026).

Что говорят цифры

Количественные оценки производительности программной реализации POPCNT дают представление о её эффективности. В бенчмарке, опубликованном на GitHub в рамках обсуждения issue #46188 репозитория Go (язык программирования, разработанный в компании Google), алгоритм Уилкса-Уилера-Гилла показал следующие результаты на процессоре Intel Core i9-9980HK (частота 2.40 ГГц):

  • Стандартная реализация (параллельное суммирование): 3.09 наносекунды на операцию
  • Алгоритм Уилкса-Уилера-Гилла: 2.80 наносекунды на операцию

Прирост производительности составил около 10% (источник: GitHub, golang/go, issue #46188, бенчмарки автора). Позднее это привело к предложению заменить существующую реализацию в стандартной библиотеке Go.

Применение вне ядра: от шахмат до биоинформатики

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

  1. Шахматные программы используют 64-битные битовые доски (bitboard) — каждая клетка доски представлена одним битом, а population count позволяет мгновенно оценить количество возможных ходов фигуры (источник: Chessprogramming wiki);
  2. Криптография — вес Хэмминга применяется при анализе шифротекстов для оценки их энтропии;
  3. Структуры данных — HAMT (Hash Array Mapped Trie — хэш-массив на основе префиксного дерева) использует population count для вычисления индексов в разреженных массивах, что позволяет существенно экономить память (источник: Vaibhav Sagar, "You Won't Believe This One Weird CPU Instruction!", 2019);
  4. Биоинформатика — расстояние Хэмминга применяется для сравнения генетических последовательностей.

Эволюция через десятилетия

История алгоритма подсчёта единичных битов необычна тем, что он периодически «исчезал» и «возвращался» в обиход. Как отмечается в сообществе Retrocomputing Stack Exchange (обсуждение "Are there any articles elucidating the history of the POPCOUNT instruction?", 2017): "Инструкция popcount была добавлена в системы по запросу Агентства национальной безопасности США для криптоанализа... Любопытно, что popcount, по-видимому, исчез из наборов инструкций между серединой 1970-х и серединой 2000-х годов" (источник: retrocomputing.stackexchange.com).

Сегодня POPCNT поддерживается большинством распространённых архитектур: x86 (начиная с 2008 года), ARM (через инструкцию CNT в ARMv8), RISC-V (как опциональное расширение). Компиляторы GCC и LLVM/Clang научились автоматически распознавать программные реализации подсчёта битов и заменять их аппаратными инструкциями.

Заключение

Алгоритм, опубликованный в 1957 году на страницах книги, тираж которой распродавался шесть лет, сегодня работает в миллиардах устройств под управлением Linux — от серверов до маршрутизаторов и встраиваемых систем. Это один из тех редких случаев, когда инженерное решение оказывается настолько элегантным, что переживает несколько поколений аппаратуры и остаётся востребованным спустя почти семь десятилетий.

Параллельное сосуществование программной реализации 1957 года и современных аппаратных инструкций POPCNT в одном и том же ядре Linux — не просто дань обратной совместимости. Это свидетельство того, что некоторые фундаментальные задачи имеют решения, которые не устаревают со временем. Алгоритм Гиллиса-Миллера (Gillies-Miller), описанный в первой книге по программированию, остаётся работоспособным и эффективным в мире, где компьютеры стали в триллионы раз быстрее EDSAC.
Использованные источники: Linux-Kernel Archive (lkml.iu.edu, lkml.indiana.edu), Wikipedia, Chessprogramming wiki, Communications of the ACM (cacm.acm.org), Habr (habr.com), GitHub (репозиторий golang/go), arxiv.org (статья 1611.07612), vaibhavsagar.com.
2026-07-08 22:43 Цифра