Переписать решение с Python на Go и получить ускорение в 35 раз — звучит приятно. Но можно ведь пойти дальше, вспомнить о возможностях современных процессоров и увеличить отрыв Go до 200 раз!

Привет, Хабр! Я — Игорь Вагулин, работаю тимлидом департамента IaaS в Cloud.ru, крупнейшем в России облачном провайдере IaaS- и PaaS-сервисов. Прогресс в производительности процессоров и видеокарт привел к тому, что мы можем использовать полный перебор там, где мы раньше обходились приближениями. Сегодня на примере алгоритма DRS-платформы Cloud.ru Evolution рассмотрим, как он может быть решен на разных версиях операций с плавающей точкой процессоров x86 и Arm, в чем сложности задействования SIMD-операций, почему это сложнее на Go и как это обойти. Статья написана по мотивам доклада для Golang Conf.

У нас есть все сервисы, какие только можно вообразить: S3, VM, Куберы, DBaaS, PaaS и т.д. Нас отличает от остальных облачных провайдеров наличие MLaaS. Можете к нам притащить нейронку, посадить на наши мощности, обучить ее и потом инференсить на наших мощностях.

Сегодня будем ускорять виртуализацию. 

Проблема неравномерности загрузки оборудования

Обычно облачные провайдеры закупают огромными партиями серверы, стойки и прочее оборудование. Затем собирают ЦОД по тысяче серверов и больше, загружают на них клиентскую нагрузку — создали VM-удалили, создали-удалили. Получается разброд: на одном сервере 10 VM, на другом — одна, на третьем — пусто. 

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

• VMware vCenter: Dynamic Resource Scheduler 

VMware вообще законодатель мод — с их легкой руки это и пошло.

• OpenStack: Watcher 

Это сервис оптимизации из состава платформы OpenStack (OpenStack — облачная платформа, Watcher — сервис в ее составе), который двигает VM по разнообразным моделям. 

• Kubernetes: Pod Scheduling Framework

В Kubernetes VM нет, но есть пользовательская нагрузка. Есть серверы, и нагрузку надо как-то оптимизировать. Фреймворк Pod Scheduling как раз способен по разным алгоритмам и целям двигать контейнеры. 

Оптимизаторы преследуют разные цели:

• Минимизация количества хостов

Может преследоваться цель по использованию минимального количества оборудования. У нас 1 000 серверов, разбросанные VM. Берем все, сгоняем на 10 серверов, а остальные 990 выключаем — получаем экономию электроэнергии. 

• Равномерное количество нагрузок

Можно минимизировать домен отказа. Например, у нас 10 тыс. VM и 1 тыс. серверов. На каждый из них расположим по 10 VM. Когда один сервак вышибет, что происходит достаточно регулярно в крупных парках, пострадает всего 10 VM. Скорее всего, будет затронут только один клиент. 

• Равномерная загрузка хостов

Сегодня как раз расскажу, как мы равномерную загрузку оборудования векторизовали и ускорили вычислительную.

Что такое неравномерная нагрузка

Предположим, у нас стоят 1 000 хостов, на них по 2−4 ядра. Если представим нагрузку на CPU числом от 0 до 1, у нас получится 1 000 float от 0 до 1. Математики дали хороший инструмент, который называется «стандартное отклонение». Рассчитывается оно следующим образом (здесь код на Go):

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

Когда количество хостов в ЦОД увеличивается, длина ряда растет, появляются операции над длинными векторами. Посмотрим, как это влияет на примере работы оптимизатора Watcher. 

Стратегия Workload Stabilization из OpenStack Watcher

В Watcher есть цель Workload Stabilization — равномерное распределение нагрузки. Она работает следующим образом: есть несколько серверов, на которых хаотично разбросаны VM, занято CPU. Алгоритм берет одну VM, смещает на рандомный хост и там подсчитывает стандартное отклонение. Если оно понизилось, значит, нагрузка распределена более равномерно, если нет — стало хуже.

Я выдрал из OpenStack Watcher кусок и запустил его на сгенерированной модели с такими параметрами: 1 000 хостов, 10 000 VM, рандомная CPU. Если запустить алгоритм на эту модель, то он будет считать 16 минут — не очень приятно.

Например, в облаке VMWare по умолчанию оптимизатор работает с периодом 1 минута. То есть 1 000 хостов он, в принципе, никогда не успеет обработать. Поэтому там используется разнообразная оптимизация. Алгоритм OpenStack Watcher берет не все хосты, а половину, и хаотично их выбирает.

К чему приводит использование эвристик в OpenStack Watcher? К графикам настоящей пользовательской нагрузки на проде (48 хостов, обычная стойка). На схеме ниже синим выделена нагрузка VM на хостах. Мы запустили алгоритм с эвристиками (сверху) и без эвристик (внизу):

Даже визуально можно оценить, что алгоритм с эвристиками предлагает плохой вариант — на хосте был ноль нагрузки, он перегрузил зачем-то вдвое. Хост уже прилично нагружен, он какую-то VM засунул, которая вообще выбилась очень сильно за среднее. Без эвристик алгоритм тютелька в тютельку распределяет нагрузку.

Надо найти выход из положения. Язык Python для тех, кто не торопится — давайте хотя бы на Go напишем.

Переписали на Go обычный алгоритм, все то же самое: бежим по всем source-нодам и VM, двигаем на destination хосты и подсчитываем квадратичные отклонения.

Ситуация стала лучше — на 1 000 хостов алгоритм работает 33 секунды, 25 млн итераций с 500 нагруженных хостов. Мы пытаемся сдвинуть 5 000 VM на 500 хостов — получается Standard Deviation 25 миллионов итераций. 

В профилировщике видим, что 90% времени (30 с) занимает как раз подсчет стандартного отклонения. Значит, нужно что-то делать с этой функцией. Так мы уже в минуту укладываемся, но если VM или хостов будет больше, время закончится. 

Решение есть, но сначала небольшое отступление. 

Процессорные фичи для преодоления разрыва с памятью

Последние 40 лет есть неприятная тенденция в hardware: скорость процессоров растет очень быстро, а скорость памяти — гораздо медленнее. Если в 80-х мы могли каждый такт ходить и забирать из памяти данные, то сейчас можем это сделать один раз из тысячи тактов примерно. 

На графике отображена скорость.

Изготовители железа придумывают разнообразные ухищрения:

• Многоуровневое кеширование

Оно появилось на i486, там было 8КБ кеширования. Сейчас у нас трехуровневый кеш, несколько сотен мегабайт, и это все где-то кешируется. 

• Суперскалярность

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

• Векторные инструкции

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

Эксперимент

Покажу, какое ускорение дают новые команды.

Я переписал на C код для вычисления стандартного отклонения. Просто там компилятор помощнее и возможны разнообразные компиляторные оптимизации, которые Go-компилятор не умеет. 

Функция computeDeviationForLoad вычисляет стандартное отклонение. В ней два раза используется функция Sum, которая просто все элементы в вектор складывает. Здесь всего четыре поколения, начнем с первого. 

Первое поколение инструкций работы с вещественными числами X87 появилось в 1980 году. X86 был 16-битный процессор с ограниченным количеством операций. Тогда втискивали X87 в свободное окно в X86, у них не хватало бит под функции с двумя операндами, поэтому он такой аккумуляторный. Тут ассемблерный код с одним операндом — это очень неудобно для современных процессоров, потому что у них регистровые файлы размером с Техас. А тут — регистровая модель, которая может грузить только в первый регистр, и потом надо как-то их ренеймить. 

Если мы так это все скомпилируем под X86, получится 83 секунды — примерно втрое медленнее, чем на Go. Так что если вы компилируете на 32 битах, убедитесь, что у вас нормально используется арифметика вещественных чисел.

Для X86−64 у нас минимальный общий деноминатор — SSE. На всех 64-битных процессорах он есть, поэтому по дефолту все генерят код в SSE. 

Переключаем компиляторные флажки, говорим, что у меня есть SSE, начинает компилироваться такой код. Видно, что начинает использоваться addss, начинают использоваться XMM-регистры — это признак SSE. Он 64-битный код начал компилировать, я его переключил. 

Go генерирует примерно то же самое, что C, если ему разрешить по дефолту использовать SSE. Он тоже использует addss, не использует векторизацию по дефолту. 

Все еще шагаем по 8 байтов (по одному float) — но почему, где наши векторные инструкции? Ведь SSE же векторный!

Почему у нас нет SIMD-инструкций

Чтобы у нас была векторизация компилятора с автоматическим указателем векторизации, нужны два компиляторных трюка. 

Первый — Loop unrolling, — это просто один цикл, мы складываем числа одно за другим. Для векторных инструкций нужно, чтобы там было хотя бы 4 числа, то есть минимальный размер регистра — 4. Компилятор может у вас под ногами переписывать код в такое выражение. Он будет по 4 шага прыгать, но зато в цикле делать 4 операции.

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

Но это только в теории, потому что размер регистров ограничен. Если вы работаете с большими и маленькими числами одновременно, то от порядка складывания зависит, будете ли вы накапливать ошибку или нет. Стандарт работы с вещественными числами IEEE 754 запрещает накопление ошибки и перестановку операндов.

Нам надо все это компилятору разрешить и сказать ему: «Векторизуй, плевать мне на ошибку округления, считай во весь опор этот ffast-math. В любом порядке считай». Тогда он начинает использовать XMM-регистры.

Как видите, loop на Ассемблере вырос в 4 раза. Он юзает сразу 8 регистров, в каждом регистре помещается по четыре 32-битных floats (они бывают 32, 64 и 80 бит, 32 самые короткие). Всего на 1 000 floats надо 32 итерации, время — 10 сек.

В следующем поколении AVX2 регистры уже 256-битные. Тоже можно сказать: «Юзай AVX», чисел становится больше, итераций меньше, время уже 5,5 сек.

В AVX512 уже 512-битные регистры. В здоровенные ZMM регистры помещается уже по 16 чисел. Надо всего 8 итераций, чтобы 1 000 floats сложить.

У AVX512 сложная судьба. Его Intel сначала выкатил в Core 13 или 14, потом вкатил обратно, потому что начал выпускать гибридные процессоры, где есть быстрые и медленные ядра, а медленные ядра AVX512 не умеют. Так что давайте целиться в AVX2, в 5,5 сек.

Казалось бы, в чем проблема заюзать все это благолепие на Go…

Проблемы векторизации Go

• dumb slice zeroing is faster than normal

На баг-трекере Golang человек пишет: «Парни, пытаюсь в IP 10 последних байтов занулить. Если я просто 10 последних присвоений делаю, то это работает в 5 раз быстрее, чем если циклом пройдусь. Можете починить свой компилятор?». Ему отвечают, что для этого нужна серьезная переработка, funroll-loops, большие преобразования на AST-дереве. 

И правда: unrolled looping потребовал полной переработки внутреннего представления AST-дерева, с которого кодогенерация происходит.

• add package for using SIMD instructions 

Вторая проблема — нет простого доступа к SIMD-операциям.

В Rust недавно добавили пакет SIMD. Там можно написать на высокоуровневом языке. Со слайсами пишем, и он под ARM, под X86 генерит сразу векторизованный код. Под это есть баг-трекер: «Парни, сделайте как в Rust!» — «Боженька, надо же будет это поддерживать, архитектур много, а нас мало. Нет, извините, приходите послезавтра».

Решение

Есть отличный заход — cgo. Пишем функцию на C, зовем ее cgo, и вроде бы должна векторизация сработать. По умолчанию он компилирует дефолтными флажками компилятор O2, и там никакого благолепия не будет. Но если мы добавим все наши заклинания: «Плевать на ошибки, давай мне всю скорость, которая у тебя есть, дорогой друг!», то получим примерно 7 сек. Уже близко к тому, что на C++ мы получили, но где-то 20% замедление.

Посмотрим в Go-профилировщике

Мы там ничего не увидим — он заканчивается на runtime.cgocall (вызов функции cgo). Но если запустим системный профилировщик perf (он в Linux по умолчанию), скомпилируем код фрейм-пойнтерами, то он уже сможет все отследить. 

Здесь есть cgocall и другие запчасти (overhead): runtime.exitsyscall и runtime.entersyscall. Они примерно 20% дают. Если функция cgo достаточно быстрая, я ее тут зову миллион раз в секунду, этот overhead виден уже невооруженным глазом.

Мы можем использовать Ассемблер Go, он поддерживает и AVX2, и AVX512. Но наверно нам не хотелось бы туда спускаться. 

В сети какой-то добряк уже запаковал для нас эти ассемблерные функции. В библиотеке vek есть 2 публичных пакета vek и vek32 под float 64 и float 32. В них есть набор разнообразных операций: сложение, вычитание, умножение векторов, перемножение матриц. Все основные математические операции со слайсами можно делать со всей скоростью без всяких накладных расходов. 

Библиотека выглядит примерно так:

С кода на C++ сгенерирован Ассемблер, который потом с помощью Python перегоняется в AVX для Go. В папке avx2 лежат уже обработанные Python AVX2-функции, которые перегнали из cpp. 

В основной папке лежат fallback для go-функций для процессоров, где нет поддержки AVX2.

Так выглядит функция Sum, с которой мы упражнялись. Берутся cpu-флаги (HasAVX2 и HasFMA), и их использует либо быстрая функция, либо медленная. 

Вставляем эту функцию в наш ComputeDeviationForNodes (подсчет среднего, сложение, вычитание) и получаем те самые 5,5 секунд, которые у нас были на C++.

Смотрим профилировщик. Видно, как он использует наши ускоренные функции — победа!

Сводные результаты

Мы начинали с 16 минут на Python, простой вариант на Go дал примерно 33 сек, а с AVX2 получили 5,5 сек — в 6 раз быстрее, чем стандартный вариант на Go. До 200 не дотянули, но близко.

Выводы 

• Используйте виртуализацию от проверенных производителей

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

• Использование современных наборов команд и уменьшенной точности позволяет достичь 5–30-кратной производительности при тех же данных и оборудовании.

В библиотеке vek есть таблица с ускорением относительно стандартной Go-реализации. Функция Sum в 5 раз ускоряется, а And — в 139 раз.

• Go не векторизует автоматически. 

Но решение есть. Ищите горячие места в коде и применяйте описанные выше подходы.

Бонус: то, что вам может пригодиться

Использованные материалы:

• библиотека векторных инструкций для Go:
  https://github.com/viterin/vek

• ссылки на исходники примеров  расчета стандартного отклонения во всех вариациях (на Go, на C, на CUDA):
  https://github.com/ivagulin/go-stddev
  https://github.com/ivagulin/cpp-stddev
  https://github.com/ivagulin/rocm-stddev 

• доки по оптимизатору VMWare по DRS — здесь описаны разные проблемы с размещением VM:
  https://www.vmware.com/docs/vsphere6-drs-perf
  https://www.vmware.com/docs/drs-vsphere7-perf 

• исходники стратегий OpenStack:
  https://github.com/openstack/watcher/tree/master/watcher/decision_engine

• описание scheduling framework K8s — горячая тема о правильном распределении нагрузок, потому что Kubernetes, в том числе, используют для размещения нагрузок от AI:
  https://kubernetes.io/docs/concepts/scheduling-eviction/

А чтобы узнать больше полезного о Go-мире, приходите на Golang Conf 2026 в апреле! Все подробности — по ссылке. Участие можно принять как очно, так и в онлайн-формате. Вас ждет концентрация пользы, нетворкинга и нестандартных решений!