Бесплатные материалы

Почему Go-ассемблер и векторизация могут быть полезны: идея для ускорения

Когда речь заходит о производительности в Go, большинство разработчиков полагаются на стандартные библиотеки и встроенные инструменты оптимизации. Но компилятор Go не всегда генерирует оптимальный машинный код. В таких случаях можно взять дело в свои руки и использовать ассемблерные инструкции для ускорения критически важных участков.
Привет! Меня зовут Игорь Панасюк, я работаю в Яндекс, преподаю в ИТМО, а также в свободное время выступаю на конференциях, делюсь опытом в соцсетях и помогаю развитию Go-сообщества, веду Telegram-канал и YouTube-канал. В этой статье по мотивам моего доклада для Golang Conf мы разберём, как с помощью Go-ассемблера можно ускорять код, используя векторные инструкции и аппаратные оптимизации.
Ассемблер может показаться сложным и пугающим, но он открывает большие возможности для работы с низкоуровневыми оптимизациями. Готовы разобраться, как это работает? Тогда погнали!

Мотивация

func SliceContainsV0(s []uint8, target uint8) bool {

return slices.Contains(s, target)

}

func SliceContainsV1(s []uint8, target uint8) bool
Есть две функции:
  1. slideContainsV0 — просто обёртка над стандартной функцией.
  2. slideContainsV1 — написанная на ассемблере.
Запустим бенчмарк и увидим, что функция v1 быстрее примерно в 14 раз. Казалось бы, странно — ведь вызвали функцию из стандартной библиотеки.
Давайте разбираться, почему так. Но сначала выясним, как программа на Go компилируется.

С помощью чего ускоряем

Есть pipeline компиляции, который можно посмотреть командой: GOSSAFUNC=main go tool compile -S -S main.go
Этой командой можно запустить pipeline и посмотреть все этапы компиляции. Компилятор разбивает наш код на Go на lexemes.
/Users/igorwalther/Goland Projects/golangconf-2024
func main() {
    println("Hello, GolangConf-2024!")
}
Далее строится так называемое абстрактное синтаксическое дерево (AST).
. BLOCK tc(1) # main.go:4:9
. BLOCK-List
. . CALLFUNC Walked tc(1) # main.go:4:9
. . CALLFUNC-Fun
. . . NAME-runtime.printlock Class:PFUNC Offset:0 Used F
. . CALLFUNC Walked tc(1) # main.go:4:9
. . CALLFUNC-Fun
. . . NAME-runtime.printstring Class:PFUNC Offset:0 Used
. . CALLFUNC-Args
. . . LITERAL-"Hello, GolangConf-2024!\n" string tc(1) #
. . CALLFUNC Walked tc(1) # main.go:4:9
. . CALLFUNC-Fun
. . . NAME-runtime.printunlock Class:PFUNC Offset: 0 Used
После этого компилятор преобразует его в так называемое Intermediate Representation — своё внутреннее представление, которое принимает одну из форм, называемую SSA.
b1:
  v2 (?) = SB <uintptr> : SB
  v1 (?) = InitMem <mem>
  v4 (+4) = CALLstatic <mem>
      {AuxCall{runtime.printlock}} v1
  v5 (4) SelectN <mem> [0] v4
  v14 (4) = MOVDaddr <*uint8> {go:string."Hello, GolangConf-2024!\n"} v2 : R0
  v13 (4) MOVD const <int> [24] : R1
  v7 (4) CALLstatic <mem>
      {AuxCall{runtime.printstring}} [16] v14 v13 v5 :
      <>
  v8 (4) = SelectN <mem> [0] v7
  v9 (4) = CALLstatic <mem>
      {AuxCall{runtime.printunlock}} v8
  v10 (4) = SelectN <mem> [0] v9
  v11 (+5)= MakeResult <mem> v10
Ret v11 (5)
{go:string."Hello, GolangConf-2024!\n"}
Скажу вкратце, что это называется noding. Компилятор на этой стадии применяет разные оптимизации — escape analysis, девиртуализацию, inlining и так далее. Подробнее читайте тут.

После этого компилятор генерирует ассемблер и машинный код.
      # /Users/igorwalther/GolandProjects/golangconf-2024/main.go
      00000 (3) TEXT main.main(SB), ABIInternal
      00001 (3) FUNCDATA $0, gclocals·g2BeySu+wFnoycgXfElmcg==(SB)
      00002 (3) FUNCDATA $1, gclocals·g2BeySu+wFnoycgXfElmcg==(SB)
v4    00003 (+4) PCDATA $1, $0
v4    00004 (+4) CALL runtime.printlock(SB)
v14   00005 (4) MOVD $go:string."Hello, GolangConf-2024!\n" (SB), R0
v13   00006 (4) MOVD $24, R1
v7    00007 (4) CALL runtime.printstring (SB)
v9    00008 (4) CALL runtime.printunlock (SB)
b1    00009 (5) RET
      00010 (?) END
Основная идея в том, что компилятор одновременно умный и в то же время глупый. Он не всегда может эффективно сгенерировать ассемблерный код. Тогда можно написать вручную свой код, который будет отрабатывать быстрее. Пока не понятно, что это будет за код, как его писать, но идея такая.
В наших компьютерах есть регистры. Если говорить более научным языком, это статические ячейки памяти. Они дороже динамической ячейки, потому что в них шесть транзисторов, а в динамической ячейке только один. Можно рассматривать регистр как быструю память около процессора. На современных системах приняты регистры в 8 байт.
Но на самом деле есть расширение, подразумевающее, что на железе есть расширенные регистры — не 8 байт, а 16 или 32 байта.
Представьте, что у вас таких регистров не один, а от двух до пяти. Используя их, можно делать разные прикольные вещи.
Для них нам пригодится классификация архитектур под названием таксономия Флинна. Она помогает понять, как обрабатываются данные в процессорах. Одной из видов архитектур по этой классификации является SIMD (Single Instruction stream / Multiple Data stream). Это вычислительная система с одиночным потоком команд и множественным потоком данных. Это означает, что одна инструкция может сразу обрабатывать несколько потоков данных одновременно. Для этого используются специальные векторные регистры, которые позволяют выполнять операции не над одним значением, а сразу над целой группой чисел. Такой подход значительно ускоряет вычисления, особенно в задачах, связанных с обработкой изображений, математическими расчётами и машинным обучением.

В Go нет intrinsic SIMD-функций

Разработчики, работающие с C++ и другими языками, где есть intrinsic-функции, могут напрямую вызывать оптимизированные инструкции, которые компилятор понимает и эффективно преобразует в машинный код. Это позволяет получить максимальную производительность без написания ассемблерных вставок.
К сожалению, в Go таких возможностей пока нет. Стандартный компилятор из Go toolchain не умеет автоматически генерировать такие оптимизированные инструкции. Это ограничение усложняет низкоуровневую оптимизацию и требует написания кода на ассемблере вручную.
Существует несколько причин, по которым эта функция до сих пор не реализована. Официально разработчики Go объясняют это сложностью создания поддержки для всех архитектур в существующем компиляторе. На данный момент у них просто не получилось реализовать это на должном уровне.
Ещё один комментарий от команды разработчиков звучал так: «Это было бы здорово, но сейчас есть более важные задачи». Другими словами, они признают, что такая возможность могла бы улучшить язык, но пока не является приоритетной.
Недавно Go исполнилось 15 лет, и в официальном блоге разработчики отметили, что активно работают над тем, чтобы встроенная поддержка подобных функций появилась в будущем. Их цель — сделать это нативно, красиво и удобно для пользователей. На момент написания этой статьи уже вышел Go 1.24, где SIMD инструкции были использованы в новой swiss-map.
«We’re looking at how to support the latest vector and matrix hardware instructions»

© The Go Blog: Austin Clements
В будущих итерациях и релизах Go, возможно, intrinsic-функции станут частью стандартного функционала языка, и их можно будет использовать «из коробки» без необходимости писать дополнительный код. Но пока нам нужно другое решение.

Идея оптимизации

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

$go:string.”Go ассемблер?”(SB)

Роб Пайк на одной из конференций сказал, что если вы знаете ассемблер, то понимаете, как работает компьютер в целом, но чуть лучше:
«Also, perhaps most important: it is how we talk about the machine. Knowing assembly, even a little, means understanding computers better»

© GopherCon 2016: Rob Pike
И это правда. Только ради этого стоит хотя бы немного разобраться в ассемблере. Выделю несколько важных фактов о Go-ассемблере, которые нужно вспомнить, чтобы понять о чём я буду рассказывать дальше:
Изначально он создавался, чтобы написать runtime Go. Go-ассемблер используется в стандартной библиотеке в пакете для математики, криптографии и runtime. Изначально ассемблер был введен именно для runtime — это такой legacy Plan 9.
Платформозависимый (примеры на arm64). Если посмотреть на синтаксис ассемблера, становится понятно, что это платформозависимый язык. Но Go-ассемблер уходит корнями в Plan 9, который изначально подразумевался как платформонезависимый. В итоге сейчас это не так, для каждой архитектуры синтаксис отличается. Например, код для arm64 будет отличаться. Поэтому сегодня будут примеры на arm64 для удобства запуска. Но инструкции всё равно будут похожие, при желании их легко переписать для своей архитектуры.
Имеет нестандартный синтаксис. Go-ассемблер имеет довольно нестандартный синтаксис, особенно если сравнивать его с популярными ассемблерами, такими как NASM. Основные отличия заключаются в другом порядке аргументов и немного изменённой структуре инструкций. Эти особенности связаны с историческим наследием операционной системы Plan 9, на основе которой Go-ассемблер и был разработан.
Если вам интересно, почему Go-ассемблер устроен именно так, а не иначе, рекомендую посмотреть доклад Филиппа Кулина, где подробно объясняется, какие принципы закладывались в язык и чем они отличаются от традиционного подхода. Также рекомендую посмотреть доклад, где я подробно разбираю синтаксис Go ассемблера
А теперь давайте обсудим, наконец, инструкции для работы с векторными регистрами.

SIMD-инструкции

Представим, у нас есть два векторных регистра v0 и v1. Они в Go-ассемблере так и называются.
Мы можем сделать с регистрами ряд действий, например, сложить. Получим другой векторный регистр с ожидаемым значением.
Одна из инструкций, которую будем сегодня использовать, это инструкция VMOV.
Инструкция VMOV позволяет переносить данные из векторного регистра в обычный. Представьте, что у вас есть векторный регистр, содержащий несколько значений, и вам нужно извлечь одно из них для дальнейшей работы.
  1. Вызываем команду VMOV.
  2. Указываем, из какого векторного регистра (например, v0) берём значение.
  3. Определяем, как именно воспринимать этот регистр. В архитектуре ARM это делается через точку: например, .S означает, что мы рассматриваем содержимое как 4 отдельных числа по 4 байта (Single Precision Value).
  4. Выбираем конкретный элемент, обращаясь к нему по индексу (например, v0[0]).
История с Single Precision (одинарной точностью) берёт своё начало из стандарта IEEE 754, который определяет форматы представления чисел с плавающей запятой в компьютерах. Аналогично, Double Precision (двойная точность) также следует этому стандарту, но использует больше бит для хранения значений, что позволяет работать с более высокой точностью и диапазоном чисел.
Есть таблица синтаксиса регистров:
​​Если вам нужно разделить векторный регистр на 2, 4, 8 или 16 частей, вы можете использовать соответствующие суффиксы. Эта возможность тоже основана на стандарте IEEE-754 и позволяет трактовать содержимое регистра как набор меньших элементов. По сути, это способ разбить данные на удобные для обработки фрагменты, не меняя их значения. Можно представить это как разметку памяти, позволяющую работать с отдельными частями регистра.
Ещё нам понадобится инструкция свёртки со сложением.
У нас есть векторный регистр, содержащий несколько значений. Мы хотим свести их к одному числу, просуммировав все элементы внутри регистра. Итоговое значение сохраняется в другом векторном регистре, поскольку сумма может быть слишком большой, чтобы уместиться в обычный скалярный регистр.
Эта операция называется свёрткой (reduction) — мы последовательно складываем элементы и получаем итоговый результат. Такой подход удобен, когда нам нужно быстро агрегировать данные, например, в вычислениях статистики или линейной алгебре.
Для double precision (двойной точности) процесс работает аналогично: числа с плавающей запятой просто обрабатываются с большей точностью.
Не нужно бояться суффиксов .D, .S. Они просто дают возможность разбить регистр на фрагменты.
Мы уже научились выполнять свёртку, сложение и другие бинарные операции. Теперь нам нужно научиться загружать данные из памяти в векторный регистр и, выгружать их обратно.
Для этого существует удобная инструкция VLD1 (Vector Load 1). Она позволяет загрузить значения из памяти в векторный регистр. Единица в названии говорит о том, что существуют другие версии этой инструкции:VLD2, VLD3, VLD4, которые позволяют загружать сразу несколько блоков данных в разные регистры. Но пока сосредоточимся на VLD1, она загружает один блок данных из памяти в один векторный регистр.
При использовании VLD1 нужно указать три вещи:
  1. Адрес в памяти, откуда будем загружать данные.
  2. Векторный регистр, в который загрузим эти данные.
  3. Типизацию через точку, чтобы задать способ интерпретации данных (например, как 16 байт).
Пример: если мы указываем адрес R0, а регистр V0, то VLD1 возьмет 16 байт из памяти по адресу R0 и загрузит их в V0.
Проще говоря, эта инструкция — аналог продвинутого MOV, но для векторных регистров. Мы переносим блок данных из памяти в регистр, чтобы потом быстро работать с ним внутри процессора.
Название VLD1 намекает, что загружается один векторный регистр. Но в архитектуре ARM есть и другие варианты: VLD2 — загружает данные сразу в два векторных регистра (например, V0 и V1), VLD3 — загружает данные в три, VLD4 — в четыре. А вот VLD5 не существует, потому что архитектура не предусматривает загрузку данных в пять регистров за раз. Основная идея в том, что можно сразу загружать большие объёмы данных из памяти в векторные регистры. Это особенно полезно, если мы работаем с массивами, матрицами или большими блоками чисел, которые потом будем обрабатывать с помощью векторных инструкций.
Мы научились загружать данные из памяти в регистр. Давайте научимся, наоборот, загружать их из регистра в память.
Инструкция vector store:
Инструкция VST1 (Vector Store 1) работает по той же логике, что и VLD1, но в обратном направлении — она перемещает данные из векторных регистров в память.
Как это работает:
  • Указываем адрес памяти, куда будем записывать данные.
  • Выбираем векторные регистры, откуда берутся данные.
  • Определяем формат данных (например, 16 байт на регистр).
Если мы используем два регистра (V0 и V1), то получаем, что в памяти окажутся сразу четыре значения — первые два из V0, вторые два из V1.
Это понятно интуитивно: так же, как мы загружали данные пакетами с помощью VLD, теперь мы можем их выгружать пакетами.
Хороший вопрос: если у нас есть два набора данных, как определить, есть ли среди них совпадения?
Здесь есть два возможных подхода:
  1. Атомарное определение совпадения – просто узнать, есть ли хотя бы одно совпадение среди элементов.
  2. Более детальное сравнение – определить, какие элементы совпали и где именно.
Векторные инструкции позволяют сравнивать сразу целые блоки данных, но важно понимать, как интерпретировать результат.
Важнейшая операция, которой сегодня будем пользоваться — сравнение двух векторных регистров.
Операция работает следующим образом:
Когда нам нужно сравнить два набора данных, удобно использовать векторное сравнение. В Go-ассемблере для этого применяется инструкция VCMEQ (Vector Compare Equal).
Что делает VCMEQ:
  • Берёт два векторных регистра.
  • Проводит побайтовое или поэлементное сравнение (в зависимости от размера данных).
  • Записывает результат в битовую маску:
Если элементы совпали — соответствующий блок битов будет 1.
Если не совпали — биты в соответствующем будут 0.
Эта операция особенно полезна, если мы ищем определённый элемент в массиве или сравниваем два набора данных. После этого мы можем сжать результат (например, с помощью VADDV) и быстро понять, было ли хоть одно совпадение.
Когда выполняется векторное сравнение, результат представляется в виде битовой маски: Единицы ставятся в тех позициях, где элементы совпали (true). Нули — там, где элементы различаются (false).
Эта маска позволяет анализировать совпадения без явного перебора элементов.
1. Простая проверка наличия совпадений:

  • Применяем VADDV (vector reduce add), которая суммирует все значения в маске.
  • Если сумма больше нуля, значит, хотя бы одно совпадение есть.

2. Анализ позиций совпадений:

  • Можно использовать маску для фильтрации или индексирования, например, чтобы определить, в каких конкретно местах произошло совпадение.
Этот метод быстрее обычных циклов, потому что обрабатывает сразу целый блок данных, а не по одному элементу за итерацию.
Также нам сегодня понадобится инструкция дупликации. Мы хотим получить из одного обычного регистра векторный регистр, размножив значения.
Мы используем VDUP (Vector Duplicate), чтобы скопировать одно значение во все ячейки векторного регистра.
  1. Берём значение из R0.
  2. Копируем его во все четыре слота векторного регистра V0.
То есть одно и то же число заполняет весь регистр, создавая однородный вектор.
Это полезно, когда нужно сравнивать целый массив с одним значением. Или если нужно выполнять массовые вычисления с одним коэффициентом, например, умножить все элементы на одно число.
То же самое с double precision:
На самом деле, расширений и инструкций существует очень много.
​​Я продемонстрировал работу с ассемблером на ARM64, но аналогичные принципы применимы и к другим архитектурам, например, x86. У разных платформ есть свои расширения. В x86 доступны расширенные векторные регистры вплоть до 512 бит (например, в AVX-512). Это в четыре раза больше, чем 128-битные регистры, которые я использовал в примерах. Чем больше регистр — тем больше данных можно обработать за одну инструкцию, а значит, выше потенциальное ускорение.

Что понадобится

Нам понадобятся векторные инструкции из Go-ассемблера:
  • VADD (vector addition);
  • VDUP (vector duplicate);
  • VADDV (vector reduce add);
  • VLD1 / VST1 / VMOV (vector load1 / vector store1 / vector mov);
  • VCMEQ (vector compare equal);
Кроме векторных инструкций, есть и обычные, которые часто встречаются в ассемблерном коде Go.
  • MOVD (MOV double word)
На ARM64 одно машинное слово — это 4 байта, и MOVD используется для перемещения двойного слова (8 байт). Это стандартная инструкция для загрузки или сохранения данных. Различные способы адресации позволяют гибко управлять данными и оптимизировать доступ к памяти.
  • LDP (load pair aka двойной MOV)
Более прокачанная версия на arm64. Сегодня буду ей пользоваться, потому что она компактней. Обычно, чтобы загрузить два значения, нужно два MOV. LDP позволяет сделать это одной инструкцией. А ещё работает быстрее, так как загружает сразу двойной объём данных.
  • ADD / SUB
Сложение/вычитание, чтобы инкрементировать или увеличивать счетчики, двигать указатели и так далее.
  • B (branch), CBZ, CBNZ (compare branch not/zero)
Инструкции управления — как реализовать циклы. В ассемблерном коде есть инструкции управления, на arm это ходовые branch, compare branch not/zero, на amd64 — jump, jump zero и так далее. Идея везде одна и та же, а нейминг отличается.
  • CMP (compare)
Инструкцию compare можно сравнить с инструкцией test — позволяет сравнить два значения, поменять регистр флагов, чтобы потом сделать какое-то разветвление.
В следующей части статьи разберём в примерах, как всё это использовать.
Читать далее
https://igoroutine.courses/free-materials/e1btztez01-vektorizatsiya-i-simd-v-go-uskorenie-poi

Дополнительные материалы

Исходный код
https://github.com/IgorWalther/golangconf-2024
Asm go.dev quick guide
https://go.dev/doc/asm
Summary of Go assembler
https://www.quasilyte.dev/blog/post/go-asm-complementary-reference/
Почему Golang такой странный / Филипп Кулин (Дремучий лес)
https://www.youtube.com/watch?v=ql-uncsqoAU
Go Assembler: ускорение кода гомоморфного хэширования в N раз /Евгений Стратоников (Neo SPCC)
https://www.youtube.com/watch?v=foCV6nn4rkc
GopherCon 2016: Rob Pike - The Design of the Go Assembler
https://www.youtube.com/watch?v=KINIAgRpkDA
Binary Search SIMD optimization
https://clement-jean.github.io/simd_binary_search_tree/
Computer Science Продвинутый Go