Недавно на Хабре появилась функция "Объяснить код с SourceCraft", реакция на которую была неоднозначна из-за довольно странного решения сделать эту функцию обязательной, а не опциональной. Мусолить эту тему особо желания нет, а вот пройтись по существу хотелось бы, потому что как мы все знаем LLMки довольно хороши в коде, который уже миллион раз был выложен в открытый доступ, но вот со всякими редкими штуками есть проблемы, а еще они позвиздеть любят. В этой статье распишу как я прошёлся по сниппетам кода в двух своих статьях на хабре, попросил SourceCraft пояснить сломанные варианты этих сниппетов, и что из этого вышло. Спойлер: результат лучше, чем я предполагал, штука определённо полезная если использовать с умом.
Два универсальных SIMD алгоритма
Итак, врываемся сразу с двух ног с ручных SIMD оптимизаций - это топик для опытных разработчиков, работающих с нетипичными сценариями, требующих производительности, посмотрим чем нам здесь помогут нейронки. Начинаем со сниппета, который по сути представляет собой метаинформацию и его трудно назвать кодом, взят с общедоступного мануала от Intel
__m128i _mm_shuffle_epi8 (__m128i a, __m128i b)
#include <tmmintrin.h>
Instruction: pshufb xmm, xmm
CPUID Flags: SSSE3
Объяснение SourceCraftФункция __m128i _mm_shuffle_epi8 (__m128i a, __m128i b) является частью SIMD-инструкций (Single Instruction, Multiple Data) и предназначена для перемешивания упакованных 8-битных целых чисел в соответствии с маской, указанной в соответствующем 8-битном элементе второго параметра. Эта операция позволяет эффективно выполнять побайтовую обработку данных, используя параллельный просмотр таблицы.
Инструкция доступна начиная с набора инструкций SSSE3 и позволяет выполнять сложные вычисления над байтами, используя всего 4 бита для индексации. Это делает её полезной для реализации различных алгоритмов, таких как подсчёт побайтового попкаунта, подсчёт чётности и разворот битов числа.
Пример использования функции для подсчёта побайтового попкаунта демонстрирует, как можно эффективно использовать эту инструкцию для выполнения сложных вычислений над данными, упакованными в 128-битный регистр.
В целом всё по делу, верная вспомогательная информация. Есть кнопка "Подробнее в SourceCraft", давайте ка дадим неверное описание. Здесь и далее буду приводить примеры, которые сделаны наподобие того, что я увидел в чате SourceCraft при нажатии этой кнопки, а именно запрос в чат "Объясни этот сниппет кода <код с ошибками>" (я делаю запрос в тот же чат, поэтому успех нейронок может быть обусловлен тем, что у них есть контекст, может кто-нибудь попробует более сделать такой же эксперимент без контекста)
__m256i _mm_shuffle_epi8 (__m256i a, __m256i b)
#include <tmmintrin.h>
Instruction: pshufb xmm, xmm
CPUID Flags: NEON
Объяснение SourceCraftФункция `_mm_shuffle_epi8` — это SIMD-инструкция, которая выполняет побайтовую перестановку (shuffle) элементов в векторе. Она позволяет использовать один вектор как таблицу поиска для перестановки элементов другого вектора. Это особенно полезно для задач, таких как: - Таблицы lookup (поиск по таблице). - Перестановка байтов. - Упаковка/распаковка данных. - Реализация алгоритмов шифрования.
Функция принимает два параметра:
a — вектор, из которого берутся значения для перестановки.
b — вектор индексов, определяющий порядок перестановки.
Результат — вектор, где каждый байт определяется значением из a по индексу из b.
Параметры функции _mm_shuffle_epi8:
__m256i a — 256-битный вектор (32 байта), из которого берутся значения для перестановки. Каждый байт в этом векторе может быть выбран как результат.
__m256i b — 256-битный вектор (32 байта) индексов. Каждый байт в этом векторе определяет, какой байт из вектора a будет помещён в соответствующую позицию результата.
Особенности работы:
Если старший бит байта в векторе b равен 1, результат в этой позиции будет 0.
Индексация в векторе a происходит по модулю 16 для каждого 128-битного блока (в случае _mm256_shuffle_epi8).
Функция работает независимо с двумя 128-битными половинами вектора.
Инструкция pshufb (packed shuffle bytes) — это SIMD-инструкция процессора x86, реализующая функциональность _mm_shuffle_epi8. Она работает следующим образом:
Принимает два операнда: источник данных и маску индексов.
Для каждого байта в маске индексов:
Если старший бит установлен (бит 7 = 1), результат — 0.
Иначе используется младшие 4 бита маски как индекс для выбора байта из источника.
Инструкция выполняется параллельно для всех байтов в векторе.
Эта инструкция была добавлена в набор SSE3 и поддерживается большинством современных процессоров x86.
Флаг CPUID NEON в данном контексте указан как поддерживающий инструкцию pshufb. Однако это требует уточнения:
NEON — это SIMD-архитектура ARM, а не x86. Инструкция pshufb — это инструкция x86 SSE3.
Для x86 процессоров флаг CPUID, указывающий поддержку pshufb, — это SSSE3 (Supplemental Streaming SIMD Extensions 3).
В ARM NEON есть аналогичные инструкции для перестановки байтов, но они имеют другие названия (например, VTBL).
Вероятно, в сниппете есть ошибка — для инструкции pshufb на x86 должен указываться флаг SSSE3, а не NEON.
В описании было изменено две вещи: 128-битные типы были заменены на 256-битные, а в CPUID указан NEON. Первая часть была практически полностью проигнорирована, в какой-то момент указывается корректный интринсик _mm256_shuffle_epi8, являющийся частью AVX2, но на то, что здесь есть ошибка не указывается. А вот вторая подмена была найдена и корректно прокоментирована -- лайк, респект. Действительно аналогом pshufb в семействе ARM NEON является VTBL.
Идём дальше, здесь опять же псевдокод pshufb, взятый всё там же из мануала интел
FOR j := 0 to 15
i := j*8
IF b[i+7] == 1
dst[i+7:i] := 0
ELSE
index[3:0] := b[i+3:i]
dst[i+7:i] := a[index*8+7:index*8]
FI
ENDFOR
Объяснение SourceCraftДанный фрагмент кода представляет собой реализацию операции, выполняемой инструкцией PSHUFB. Эта инструкция позволяет выполнять параллельный просмотр таблицы, используя 4 бита в качестве индексов для выбора значений из массива `a` и записи их в массив `dst`.
Код выполняет следующие действия:
Инициализирует цикл, который проходит по всем элементам массива b.
Проверяет значение каждого элемента массива b: если старший бит равен 1, то соответствующий элемент в dst устанавливается в 0.
Если старший бит равен 0, то из первых четырёх бит элемента b формируется индекс, который используется для выбора байта из массива a. Этот байт затем записывается в dst.
Особенностью данного подхода является возможность представления любой операции над четырьмя битами, что может быть использовано для выполнения более сложных вычислений над байтами.
Ничего интересного, давайте ломать, меняем индексы меcтами, но не везде
FOR j := 0 to 15
i := j*8
IF b[i+7] == 1
dst[i:i+7] := 0
ELSE
index[0:3] := b[i+3:i]
dst[i:i+7] := a[index*8:index*8+7]
FI
ENDFOR
Объяснение SourceCraftОбщая цель сниппета — реализовать логику инструкции PSHUFB, которая используется для параллельного просмотра таблицы. Эта инструкция позволяет выбирать байты из массива `a` на основе индексов, хранящихся в массиве `b`, и записывать результат в массив `dst`.
Код обрабатывает 16 байтов (128 бит) данных, где каждый байт в массиве b используется как индекс для выбора соответствующего байта из массива a. Если старший бит байта в b равен 1, то соответствующий байт в dst устанавливается в 0. В противном случае, из первых четырёх бит байта в b формируется индекс, который используется для выбора байта из массива a.
Разберём каждую строку кода:
FOR j := 0 to 15 — начало цикла, который будет выполняться 16 раз (для обработки 16 байтов).
i := j*8 — вычисление смещения в битах для текущего байта. Поскольку каждый байт состоит из 8 бит, i указывает на начало текущего байта в битовом представлении.
IF b[i+7] == 1 — проверка старшего бита текущего байта в массиве b. Если он равен 1, то выполняется следующая строка.
dst[i:i+7] := 0 — установка всех битов текущего байта в массиве dst в 0.
ELSE — если старший бит не равен 1, то выполняется следующий блок кода.
index[0:3] := b[i+3:i] — извлечение первых четырёх бит текущего байта в массиве b и сохранение их в переменной index.
dst[i:i+7] := a[index*8:index*8+7] — использование значения index как индекса для выбора байта из массива a и записи его в соответствующую позицию в массиве dst.
FI — завершение условного оператора.
ENDFOR — завершение цикла.
Таким образом, код обрабатывает каждый байт в массиве b, проверяет его старший бит и либо устанавливает соответствующий байт в dst в 0, либо выбирает байт из массива a на основе первых четырёх бит и записывает его в dst.
Логика ветвления основана на значении старшего бита текущего байта в массиве b. Если этот бит равен 1, то соответствующий байт в массиве dst устанавливается в 0. Это означает, что байт в dst будет "занулен", и никакие данные из массива a не будут использованы.
Если старший бит равен 0, то из первых четырёх бит текущего байта в массиве b формируется индекс. Эти четыре бита интерпретируются как 4-битное число, которое используется для выбора байта из массива a. Затем выбранный байт записывается в соответствующую позицию в массиве dst.
Манипуляции с битами выполняются с использованием срезов, например, b[i+3:i] означает извлечение битов с позиции i до i+3. Это позволяет точно указать, какие биты использовать для формирования индекса. В данном случае, index[0:3] означает, что биты записываются в переменную index с позиции 0 до 3.
Предположим, у нас есть следующие массивы:
a = [0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x80, 0x90, 0xA0, 0xB0, 0xC0, 0xD0, 0xE0, 0xF0, 0x00]
b = [0x01, 0x80, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F]
Рассмотрим первый байт в массиве b (0x01). Его старший бит равен 0, поэтому мы извлекаем первые четыре бита (0001), что соответствует индексу 1. Затем мы выбираем байт из массива a по индексу 1 (0x20) и записываем его в dst.
Теперь рассмотрим второй байт в массиве b (0x80). Его старший бит равен 1, поэтому соответствующий байт в массиве dst устанавливается в 0.
Этот процесс повторяется для всех 16 байтов в массиве b, и в результате массив dst будет содержать либо 0, либо байты, выбранные из массива a на основе индексов, хранящихся в массиве b.
TL; DR чрезмерно подробно, на байт не повелся, но в общем наверно это ок так как псевдокод без явных правил.
std::array<uint8_t, 16> _mm_shuffle_epi8(const std::array<uint8_t, 16>& a,
const std::array<uint8_t, 16>& b) {
std::array<uint8_t, 16> result;
for (size_t i = 0; i < 16; ++i) {
if (b[i] & (1 << 7)) {
result[i] = 0;
} else {
result[i] = a[b[i] & 15];
}
}
return result;
}
Объяснение SourceCraftФункция `_mm_shuffle_epi8` написана на C++ и выполняет операцию перемешивания байтов из массива `a` в соответствии с управляющей маской, заданной массивом `b`.
Для каждого элемента массива b проверяется седьмой бит (самый старший). Если он равен 1, то соответствующий элемент результата устанавливается в 0. Если седьмой бит равен 0, то используются младшие четыре бита элемента b[i] в качестве индекса для выбора байта из массива a. Этот байт затем записывается в результат.
Этот код представляет собой неоптимизированный эквивалент SIMD-инструкции PSHUFB, которая позволяет эффективно выполнять побайтовую обработку данных, используя параллельный просмотр таблицы.
В последнем абзаце полностью отражена суть, ноль претензий.
std::array<uint8_t, 16> _mm_shuffle_epi8(const std::array<uint8_t, 16>& a,
const std::array<uint8_t, 16>& b) {
std::array<uint16_t, 16> result;
for (size_t i = 0; i < 32; ++i) {
if (b[i] & (1 << 3)) {
result[i] = 0;
} else {
result[i] = a[b[i] & 127];
}
}
return result;
}
Объяснение SourceCraftВ коде присутствуют следующие ошибки:
Несовместимость типов:
Сигнатура функции возвращает std::array<uint8_t, 16>
Но создается std::array<uint16_t, 16> (разные типы элементов)
Выход за границы массива:
Цикл итерируется 32 раза (i < 32)
Но массивы a и b содержат только 16 элементов
При обращении к b[i] при i >= 16 будет выход за границы массива
Некорректные битовые маски:
Проверяется 3-й бит вместо 7-го (1 << 3 вместо 1 << 7)
Используется маска 127 (7 бит) вместо 15 (4 бита) для индексации
Несовпадение размеров массивов:
Создается массив result из 16 элементов
Но возвращаемый тип указывает на массив из 16 uint8_t элементов
Подробное объяснение проблем:
Несовместимость типов:
std::array<uint8_t, 16> _mm_shuffle_epi8(...) // возвращает массив uint8_t
std::array<uint16_t, 16> result; // создается массив uint16_t
Это приведет к ошибке компиляции, так как типы не совпадают.
Выход за границы массива:
for (size_t i = 0; i < 32; ++i) { // 32 итерации
if (b[i] & ...) // b имеет только 16 элементов
}
При i >= 16 обращение к b[i] вызовет неопределенное поведение.
Некорректные битовые маски:
if (b[i] & (1 << 3)) // Проверка 3-го бита вместо 7-го
result[i] = a[b[i] & 127]; // 127 = 01111111 (7 бит) вместо 15 = 00001111 (4 бита)
Это изменяет семантику операции перемешивания.
Несоответствие размеров:
Если бы типы совпадали, массив из 16 элементов не мог бы содержать результат 32 операций.
Исправленная версия функции:
std::array<uint8_t, 16> _mm_shuffle_epi8(const std::array<uint8_t, 16>& a,
const std::array<uint8_t, 16>& b) {
std::array<uint8_t, 16> result;
for (size_t i = 0; i < 16; ++i) { // 16 итераций, соответствует размеру массивов
if (b[i] & (1 << 7)) { // Проверка 7-го бита (MSB)
result[i] = 0; // Обнуление если MSB установлен
} else {
result[i] = a[b[i] & 15]; // Выборка по индексу из младших 4 бит
}
}
return result;
}
Изменения:
Возвращаемый тип и тип result согласованы (uint8_t)
Цикл ограничен 16 итерациями
Восстановлена правильная битовая маска (7-й бит)
Восстановлена правильная маска индексации (4 младших бита)
Вот тут прямо хорошо, всё отловилось и в конце корректный код, впрочем скорее всего в обучении LLM моя статья тоже была.
// Таблица popcount для 4 бит
const __m128i lookup_popcount_4 = _mm_setr_epi8(
0, 1, 1, 2, // 0000, 0001, 0010, 0011
1, 2, 2, 3, // 0100, 0101, 0110, 0111
1, 2, 2, 3, // 1000, 1001, 1010, 1011
2, 3, 3, 4 // 1100, 1101, 1110, 1111
);
// Побайтовый popcnt
void popcount_16x8(const uint8_t* x, uint8_t* result) {
__m128i data = _mm_loadu_si128((__m128i const*)x);
const __m128i low_bits_mask = _mm_set1_epi8(0x0F);
// Popcount 4 нижних битов
__m128i low_bits = _mm_and_si128(data, low_bits_mask);
__m128i low_count = _mm_shuffle_epi8(lookup_popcount_4, low_bits);
// Popcount 4 верхних битов
__m128i high_bits = _mm_srli_epi16(data, 4);
high_bits = _mm_and_si128(high_bits, low_bits_mask);
__m128i high_count = _mm_shuffle_epi8(lookup_popcount_4, high_bits);
__m128i result_vec = _mm_add_epi8(low_count, high_count);
_mm_storeu_si128((__m128i*)result, result_vec);
}
Объяснение SourceCraftПредставленный код реализует алгоритм подсчёта количества установленных битов (popcount) для каждого байта в 128-битных данных с использованием SIMD-инструкций (Single Instruction, Multiple Data).
В коде используется таблица lookup_popcount_4, которая содержит предварительно вычисленные значения popcount для всех возможных комбинаций 4 бит. Алгоритм разделяет каждый байт на две части по 4 бита, использует таблицу для подсчёта количества установленных битов в каждой части и затем суммирует результаты.
Этот подход позволяет эффективно вычислять popcount для большого количества байтов параллельно, что может быть полезно в задачах, требующих обработки больших объёмов данных, например, в алгоритмах сжатия, криптографии или обработке изображений.
Опять же никаких претензий, не буду приводить "подробное" пояснение, но оно тоже корректное и полезное, правда довольно длинное. Давайте попробуем сделать какую-нибудь одну неочевидную ошибку.
// Таблица popcount для 4 бит
const __m128i lookup_popcount_4 = _mm_setr_epi8(
0, 1, 1, 2, // 0000, 0001, 0010, 0011
1, 2, 2, 3, // 0100, 0101, 0110, 0111
1, 2, 2, 3, // 1000, 1001, 1010, 1011
2, 3, 3, 4 // 1100, 1101, 1110, 1111
);
// Побайтовый popcnt
void popcount_16x8(const uint8_t* x, uint8_t* result) {
__m128i data = _mm_loadu_si128((__m128i const*)x);
const __m128i low_bits_mask = _mm_set1_epi8(0x0F);
const __m128i high_bits_mask = _mm_set1_epi8(0xF0);
// Popcount 4 нижних битов
__m128i low_bits = _mm_and_si128(data, low_bits_mask);
__m128i low_count = _mm_shuffle_epi8(lookup_popcount_4, low_bits);
// Popcount 4 верхних битов
__m128i high_bits = _mm_and_si128(data, high_bits_mask);
__m128i high_count = _mm_shuffle_epi8(lookup_popcount_4, high_bits);
__m128i result_vec = _mm_add_epi8(low_count, high_count);
_mm_storeu_si128((__m128i*)result, result_vec);
}
Здесь я заменил загрузку старших бит, вместо сдвига на 4 теперь применяется маска, т.е. мы действительно выделяем старшие биты, но они не сдвинуты!
Объяснение SourceCraftТаблица `lookup_popcount_4` остается неизменной:
const __m128i lookup_popcount_4 = _mm_setr_epi8(
0, 1, 1, 2, // 0000, 0001, 0010, 0011
1, 2, 2, 3, // 0100, 0101, 0110, 0111
1, 2, 2, 3, // 1000, 1001, 1010, 1011
2, 3, 3, 4 // 1100, 1101, 1110, 1111
);
Она содержит значения popcount для 4-битных чисел от 0 до 15. Индекс в таблице соответствует двоичному представлению числа.
Функция popcount_16x8:
Загрузка данных:
__m128i data = _mm_loadu_si128((__m128i const*)x);
Загружает 16 байт в вектор data.
Извлечение младших 4 бит:
const __m128i low_bits_mask = _mm_set1_epi8(0x0F);
__m128i low_bits = _mm_and_si128(data, low_bits_mask);
Маска 0x0F (00001111) оставляет только младшие 4 бита каждого байта. Результат low_bits содержит значения от 0 до 15, которые напрямую используются как индексы в таблице lookup_popcount_4.
Подсчёт битов в младших 4 битах:
__m128i low_count = _mm_shuffle_epi8(lookup_popcount_4, low_bits);
Извлекает popcount для младших битов каждого байта.
Извлечение старших 4 бит (новый способ):
const __m128i high_bits_mask = _mm_set1_epi8(0xF0);
__m128i high_bits = _mm_and_si128(data, high_bits_mask);
Маска 0xF0 (11110000) оставляет только старшие 4 бита каждого байта. Однако результат high_bits содержит значения вида abcd0000 (где abcd — старшие биты), которые не подходят в качестве индексов для таблицы lookup_popcount_4 (индексы должны быть от 0 до 15, т.е. 0000abcd).
Проблема с подсчётом битов в старших 4 битах:
__m128i high_count = _mm_shuffle_epi8(lookup_popcount_4, high_bits);
Эта строка некорректна. high_bits содержит значения от 0 до 240 (с шагом 16), что приведёт к неправильным результатам или нулям при использовании в _mm_shuffle_epi8. Таблица lookup_popcount_4 рассчитана на индексы от 0 до 15.
Для корректной работы необходимо преобразовать старшие 4 бита в индексы от 0 до 15. Это можно сделать двумя способами:
Сдвиг вправо на 4 бита (как в предыдущем примере):
__m128i high_bits = _mm_srli_epi16(data, 4); // Сдвигаем старшие биты в младшие
high_bits = _mm_and_si128(high_bits, low_bits_mask); // Оставляем только 4 бита
Использование маски и сдвига в таблице:
Если нужно оставить маскирование 0xF0, то индексы для таблицы должны быть скорректированы:
__m128i high_bits = _mm_and_si128(data, high_bits_mask);
high_bits = _mm_srli_epi16(high_bits, 4); // Сдвигаем старшие биты в младшие позиции
После этого high_bits будет содержать корректные индексы (0-15) для таблицы lookup_popcount_4.
Без этой корректировки функция popcount_16x8 будет работать некорректно.
И опять точное попадание, снимаю шляпу! Едем дальше
__m512i _mm512_gf2p8affine_epi64_epi8 (__m512i x, __m512i A, int b)
#include <immintrin.h>
Instruction: vgf2p8affineqb zmm, zmm, zmm, imm8
CPUID Flags: GFNI + AVX512F
Объяснение SourceCraftФункция _mm512_gf2p8affine_epi64_epi8 является частью набора инструкций GFNI (Galois Field New Instructions) и предназначена для выполнения аффинных преобразований в поле Галуа GF(2^8). Она принимает три аргумента: x, A и b, где x — вектор, A — матрица, а b — константа. Результатом функции является вектор, полученный в результате аффинного преобразования A * x + b.
Эта функция может быть использована для выполнения различных операций над байтами, таких как подсчёт побайтовой чётности, побайтовые сдвиги, циклические сдвиги и другие. Она может быть особенно полезна в контексте работы с кодами Рида-Соломона, Rijndael-шифрованием и другими алгоритмами, требующими операций в поле Галуа.
Использование этой функции позволяет оптимизировать выполнение операций в поле Галуа, что может привести к ускорению выполнения соответствующих алгоритмов.
Опять же всё по делу, разве что было бы неплохо Latex нормально обработать. Тут я думаю ломать ничего пытаться не буду, давайте сразу к последнем двум примерам
.LCPI0_1:
.byte 1
.byte 2
.byte 4
.byte 8
.byte 16
.byte 32
.byte 64
.byte 128
reverse_bits(unsigned long):
vmovq xmm0, rdi
vgf2p8affineqb xmm0, xmm0, qword ptr [rip + .LCPI0_1]{1to2}, 0
vmovq rax, xmm0
bswap rax
ret
Объяснение SourceCraftПредставленный фрагмент кода написан на языке ассемблера и использует SIMD-инструкции для выполнения операции побитового реверса 64-битного числа.
В начале кода определяется константа .LCPI0_1, которая представляет собой массив байтов с значениями 1, 2, 4, 8, 16, 32, 64, 128. Затем идёт функция reverse_bits, которая принимает на вход 64-битное число типа unsigned long.
Внутри функции происходит следующее:
Число загружается в регистр xmm0.
Применяется инструкция vgf2p8affineqb, которая выполняет аффинное преобразование в поле Галуа GF(2^8). В данном случае она используется для перестановки битов в каждом байте числа.
Результат сохраняется в регистр rax.
Инструкция bswap меняет порядок байтов в регистре rax, что приводит к полному развороту битов в числе.
Функция возвращает результат.
И опять всё точно, мне и самому было бы полезно когда я сам разбирал этот материал, потому что мне например долгое время был неочевиден пункт 4. И наконец последний пример из статьи
/* Бинарные матрицы 8x8 соответствующие умножению */
static uint64_t gfni_matrix[256];
const uint8_t irreducible_poly = 0x1b; // x^4+x^3+x+1
void InitGFNI() {
for (int16_t y = 0; y < 256; ++y) {
uint64_t mt = 0;
uint8_t row = y;
// На каждой итерации цикла вычисляется произведение y
// на очердной базисный вектор, результат записывается в mt
for (size_t i = 0, shift = 0; i < 8; ++i, shift += 8) {
mt |= ((uint64_t)row << shift);
row = (row << 1) ^ ((row >> 7) * irreducible_poly);
}
// Фактически в mt уже лежит нужная матрица, но порядок элементов
// в GF2P8AFFINEQB немного странный, нужно немного попереставлять биты
gfni_matrix[y] = 0;
for (size_t i = 0; i < 8; ++i) {
for (size_t j = 0; j < 8; ++j) {
gfni_matrix[y] |= ((mt >> (8 * i + j)) & 1) << (8 * j + (7 - i));
}
}
}
}
// Производит x[0..63] += y[0..63] * c
void FMA_64(uint8_t* x, const uint8_t* y, uint8_t c) {
__m512i c_matrix = _mm512_set1_epi64(gfni_matrix[c]);
auto x_reg = _mm512_loadu_epi8(x);
auto y_reg = _mm512_loadu_epi8(y);
x_reg = _mm512_xor_epi64(x_reg,
_mm512_gf2p8affine_epi64_epi8(y_reg, c_matrix, 0));
_mm512_storeu_epi8(x, x_reg);
}
Объяснение SourceCraftДанный фрагмент кода демонстрирует работу с бинарными матрицами и использование SIMD-инструкций для выполнения операций в поле Галуа GF(2^8).
Функция InitGFNI инициализирует массив gfni_matrix, который содержит бинарные матрицы размером 8x8, соответствующие умножению в поле Галуа. Для этого используется неприводимый многочлен irreducible_poly. Каждая матрица получается путём умножения элемента поля на базисные векторы и последующей перестановки битов для соответствия порядку элементов в инструкции GF2P8AFFINEQB.
Функция FMA_64 выполняет операцию FMA (fused multiply-add) для векторов x и y с использованием скаляра c. Она загружает соответствующие матрицы из gfni_matrix, применяет инструкцию GF2P8AFFINEQB для выполнения умножения и сложения в поле Галуа и сохраняет результат обратно в вектор x.
Этот код может быть полезен для реализации алгоритмов, работающих с полями Галуа, таких как кодирование Рида-Соломона или криптографические алгоритмы.
Вопросов нет, кратко и по делу, но вот с детализацией вопрос + даже в подробном пояснении ничего про блок кода, который после комментария "Фактически в mt уже ... ", давайте уберем его и спросим еще раз
/* Бинарные матрицы 8x8 соответствующие умножению */
static uint64_t gfni_matrix[256];
const uint8_t irreducible_poly = 0x1b; // x^4+x^3+x+1
void InitGFNI() {
for (int16_t y = 0; y < 256; ++y) {
uint64_t mt = 0;
uint8_t row = y;
// На каждой итерации цикла вычисляется произведение y
// на очердной базисный вектор, результат записывается в mt
for (size_t i = 0, shift = 0; i < 8; ++i, shift += 8) {
mt |= ((uint64_t)row << shift);
row = (row << 1) ^ ((row >> 7) * irreducible_poly);
}
}
}
// Производит x[0..63] += y[0..63] * c
void FMA_64(uint8_t* x, const uint8_t* y, uint8_t c) {
__m512i c_matrix = _mm512_set1_epi64(gfni_matrix[c]);
auto x_reg = _mm512_loadu_epi8(x);
auto y_reg = _mm512_loadu_epi8(y);
x_reg = _mm512_xor_epi64(x_reg,
_mm512_gf2p8affine_epi64_epi8(y_reg, c_matrix, 0));
_mm512_storeu_epi8(x, x_reg);
}
Объяснение SourceCraftВ этом коде объявлены две глобальные переменные:
static uint64_t gfni_matrix[256] - массив из 256 элементов типа uint64_t, который будет хранить бинарные матрицы 8x8. Каждая матрица соответствует операции умножения на определенный элемент поля Галуа GF(2^8). Поскольку элементов в GF(2^8) ровно 256 (от 0 до 255), массив имеет размер 256.
const uint8_t irreducible_poly = 0x1b - константа, представляющая неприводимый многочлен x^8 + x^4 + x^3 + x + 1 в виде байта. Этот многочлен используется для редукции результата умножения в поле Галуа, чтобы результат оставался в пределах 8 бит.
Комментарий указывает, что это неприводимый многочлен, но в комментарии ошибка - указан x^4+x^3+x+1, а на самом деле это x^8+x^4+x^3+x+1.
Тут SourceCraft явно сломался, отдельно отмечу, что в пункте два в переменной лежит именно то, что указано в комментарии без самого верхнего бита, отвечающего за , тут тоже путаница.
Век поиска кратчайшего решения задачи о кратчайшем пути
Итак, статья в большей степени про историю задачи, есть код на питоне, который приведен в большей степени для демонстрации концептов, а не для производительности, давайте смотреть
import osmnx
G = osmnx.graph_from_point((59.93893094417527, 30.32268115454809), dist=2500)
s = 365356365
t = 8518165879
shortest_path = osmnx.routing.shortest_path(G, s, t, weight='length')
osmnx.plot.plot_graph_route(G,
shortest_path,
route_color='g',
node_size=2,
node_color='red',
edge_color='b',
edge_linewidth=0.2,
bgcolor='white')
Объяснение SourceCraftДанный фрагмент кода на Python использует библиотеку OSMnx для работы с графиками и картографическими данными. Он выполняет следующие действия:
Создаёт граф G на основе географических данных, используя координаты точки (59.93893094417527, 30.32268115454809) и радиус 2500 метров.
Задаёт начальную (s = 365356365) и конечную (t = 8518165879) вершины для поиска пути.
Находит кратчайший путь между вершинами s и t в графе G, используя алгоритм поиска кратчайшего пути с параметром weight='length', что означает учёт длины рёбер при расчёте пути.
Визуализирует граф и найденный кратчайший путь с помощью функции plot_graph_route, где маршрут отображается зелёным цветом, узлы — красным, а рёбра — синим.
Этот код демонстрирует использование OSMnx для решения задачи поиска кратчайшего пути на графе, построенном на основе географических данных.
Всё верно и полезно, указал бы еще, что это центр Санкт-Петербурга -- высший пилотаж, но пока нет.
Дальнейшие пример буду прятать под спойлер
Scanning methodfrom collections import Counter
def relax(graph: Dict[int, Dict[int, float]],
u: int,
v: int,
distances: Dict[int, float],
prev: Dict[int, int],
labelled: Set,
stats: Counter = None):
if stats is not None:
stats["relax_calls"] += 1
if v not in distances or distances[v] > distances[u] + graph[u][v]:
if stats is not None:
stats["distance_updates"] += 1
distances[v] = distances[u] + graph[u][v]
prev[v] = u
labelled.add(v)
def scan(graph: Dict[int, Dict[int, float]],
node: int,
distances: Dict[int, float],
prev: Dict[int, int],
labelled: Set,
stats: Counter = None):
if stats is not None:
stats["scan_calls"] += 1
for other, length in graph[node].items():
relax(graph, node, other, distances, prev, labelled, stats)
# labelled.remove(node)
def scanning_method(graph: Dict[int, Dict[int, float]],
source: int,
target: int = None,
stats: Counter = None):
distances = {source: 0}
prev = dict()
labelled = {source}
while len(labelled) > 0:
u = labelled.pop()
if u == target:
break
scan(graph, u, distances, prev, labelled, stats)
return distances, prev
Представленный фрагмент кода на Python реализует метод сканирования (Scanning Method) для поиска кратчайших путей в графе. Этот метод является одним из подходов к решению задачи о кратчайшем пути и представляет собой итеративный процесс, в котором вершины графа помечаются и обрабатываются для нахождения оптимальных путей.
Функция relax отвечает за обновление расстояний до вершин при обнаружении более короткого пути. Она принимает граф, две вершины u и v, словарь расстояний distances, словарь предыдущих вершин prev, множество помеченных вершин labelled и счетчик stats. Если новое расстояние до вершины v через вершину u меньше текущего, то расстояние обновляется, а вершина v добавляется в множество помеченных.
Функция scan применяет функцию relax ко всем соседним вершинам текущей вершины node. Она также принимает граф, текущую вершину, словарь расстояний, словарь предыдущих вершин, множество помеченных вершин и счетчик stats.
Функция scanning_method является основной и реализует алгоритм сканирования. Она принимает граф, исходную вершину source, целевую вершину target (опционально) и счетчик stats. Алгоритм инициализирует начальные значения расстояний и предыдущих вершин, затем в цикле обрабатывает помеченные вершины, вызывая функцию scan, пока множество помеченных вершин не станет пустым или пока не будет достигнута целевая вершина.
Этот код интересен тем, что демонстрирует один из подходов к решению задачи о кратчайшем пути, который может быть полезен в различных приложениях, таких как логистика, сетевые потоки и другие задачи оптимизации.
Все верно описано, даже пояснен подсчет статистики. Но вот по сути к сожалению нет очень важного пояснения, которое присутствует в статье: большинство классических методов типа Дейкстры или Форда-Беллмана реализуют scanning method и различаются только в том, как выбирать очередную вершину для сканирования в случае возможности выбора из нескольких. В одном из следующих сниппетов как раз таким образом реализован алгоритм Дейкстры
def dijkstra(graph: Dict[int, Dict[int, float]],
source: int,
target: int = None,
stats: Counter = None) -> Tuple[Dict[int, float], Dict[int, int]]:
distances = {source: 0}
prev = dict()
labelled = {source}
while len(labelled) > 0:
u = min(labelled, key=lambda x: distances[x])
labelled.remove(u)
if u == target:
break
scan(graph, u, distances, prev, labelled, stats)
return distances, prev
Объяснение SourceCraftФункция dijkstra реализует алгоритм Дейкстры для поиска кратчайших путей в графе. Она принимает на вход граф, представленный в виде словаря смежности, исходную вершину и, опционально, целевую вершину и счётчик статистики.
Алгоритм работает следующим образом:
Инициализирует расстояния от исходной вершины до всех остальных как бесконечность, кроме расстояния до самой исходной вершины, которое равно нулю.
Создаёт два словаря: distances для хранения текущих расстояний от исходной вершины до каждой вершины, и prev для хранения предыдущей вершины на кратчайшем пути до каждой вершины.
Пока есть непосещённые вершины, выбирает вершину с минимальным текущим расстоянием, удаляет её из множества непосещённых и, если это целевая вершина, завершает работу.
Для выбранной вершины обновляет расстояния до её соседей и добавляет их в множество непосещённых, если они ещё не были посещены.
Функция возвращает два словаря: distances, содержащий расстояния от исходной вершины до каждой вершины, и prev, содержащий предыдущие вершины на кратчайших путях.
Опять же, алгоритм Дейкстры описан правильно, но почему-то ничего не сказано про использованную функцию scan, справедливости ради отмечу, что в подробном ответе это написано. Дальше есть сниппет с использованием OSM
def graph_from_osmnx(G):
graph = dict()
for n, adj in G.adjacency():
if n not in graph:
graph[n] = dict()
for e, eattr in adj.items():
for _, iattr in eattr.items():
if e not in graph[n] or graph[n][e] > iattr["length"]:
graph[n][e] = iattr["length"]
return graph
g = graph_from_osmnx(G)
distances, prev = dijkstra(g, s, t)
def print_route_and_visited(graph, source, target, distances, prev):
route = [target]
cur = target
while cur != source:
cur = prev[cur]
route.append(cur)
return osmnx.plot.plot_graph_route(G.subgraph(list(distances.keys())), list(reversed(route)), route_color='g', node_size=2, node_color='r', edge_color='b', edge_linewidth=0.2, bgcolor='white', close=True);
print_route_and_visited(G, s, t, distances, prev)
Объяснение SourceCraftДанный фрагмент кода на Python решает задачу поиска кратчайшего пути между двумя точками на графе с помощью алгоритма Дейкстры.
Функция graph_from_osmnx(G) преобразует граф G, полученный из библиотеки OSMnx, в формат словаря, где ключами являются вершины графа, а значениями — словари с соседними вершинами и длинами рёбер между ними.
Затем вызывается функция dijkstra(g, s, t), которая реализует алгоритм Дейкстры для поиска кратчайших путей от исходной вершины s до целевой вершины t в графе g. Результатом работы функции являются два словаря: distances, содержащий расстояния от исходной вершины до всех остальных вершин графа, и prev, содержащий предыдущие вершины на кратчайшем пути от исходной вершины до каждой из вершин графа.
Функция print_route_and_visited(graph, source, target, distances, prev) строит маршрут от исходной вершины source до целевой вершины target на основе полученных данных и визуализирует его с помощью функции plot_graph_route из библиотеки OSMnx.
В целом всё верно, разве что нет пояснения про то, что print_route_and_visited отрисовывает только те вершины, расстояния для которых были посчитаны, но в подробном ответе это есть.
def reversed_graph(graph: Dict[int, Dict[int, float]]) -> Dict[int, Dict[int, float]]:
rev_graph = {v: dict() for v in graph}
for v, adj in graph.items():
for u, l in adj.items():
rev_graph[u][v] = l
return rev_graph
def bidir_dijkstra(graph: Dict[int, Dict[int, float]],
source: int,
target: int = None,
stats: Counter=None):
rev_graph = reversed_graph(graph)
distances_f = {source: 0}
prev_f = dict()
distances_b = {target: 0}
prev_b = dict()
scanned_f = set()
scanned_b = set()
labelled_f = {source}
labelled_b = {target}
best = float("inf")
best_f = source
best_b = target
u = source
v = target
while len(labelled_f) > 0 or len(labelled_b):
if distances_f[u] < distances_b[v]:
if u in scanned_b:
break
labelled_f.remove(u)
scan(graph, u, distances_f, prev_f, labelled_f, stats)
for p, l in graph[u].items():
if p in distances_b and distances_f[u] + distances_b[p] + l < best:
best_f = u
best_b = p
best = distances_f[u] + distances_b[p] + l
scanned_f.add(u)
u = min(labelled_f, key=lambda x: distances_f[x])
else:
if v in scanned_f:
break
labelled_b.remove(v)
scan(rev_graph, v, distances_b, prev_b, labelled_b, stats)
for p, l in rev_graph[v].items():
if p in distances_f and distances_b[v] + distances_f[p] + l < best:
best_f = p
best_b = v
best = distances_b[v] + distances_f[p] + l
scanned_b.add(v)
v = min(labelled_b, key=lambda x: distances_b[x])
best_path = [best_f]
cur = best_f
while cur != source:
cur = prev_f[cur]
best_path.append(cur)
best_path = list(reversed(best_path))
cur = best_b
if cur != best_path[-1]:
best_path.append(cur)
while cur != target:
cur = prev_b[cur]
best_path.append(cur)
return distances_f, distances_b, prev_f, prev_b, best_path, best
Представленный код реализует двунаправленный алгоритм Дейкстры для поиска кратчайшего пути в графе. Он состоит из двух основных функций: reversed_graph и bidir_dijkstra.
Функция reversed_graph принимает на вход граф, представленный в виде словаря, и возвращает граф с обратными рёбрами. Это необходимо для работы двунаправленного алгоритма Дейкстры, который ищет пути одновременно из начальной и конечной вершин.
Функция bidir_dijkstra принимает на вход граф, начальную вершину и (опционально) конечную вершину и статистику. Она использует функцию reversed_graph для создания графа с обратными рёбрами и затем применяет алгоритм Дейкстры одновременно из начальной и конечной вершин, пока не найдёт кратчайший путь между ними.
Этот код интересен тем, что реализует оптимизированный алгоритм поиска кратчайшего пути, который может быть полезен в различных задачах, связанных с графами, например, в логистике или анализе социальных сетей.
Опять же, в подробном объяснении всё разжёвано, но тут стоит отметить такой момент. Обычно специалисты при рассказе про двунаправленного Дейкстру отмечают, что в нём нужно быть очень аккуратным в условии выхода -- в нём очень легко ошибиться, в статье этот момент разобран, в подробном ответе нейронки -- нет. Дальше идёт А*
import math
import geopy.distance
def geo_dist(graph, u, v):
coords_1 = (graph.nodes[u]['y'], graph.nodes[u]['x'])
coords_2 = (graph.nodes[v]['y'], graph.nodes[v]['x'])
return geopy.distance.distance(coords_1, coords_2).m
def a_star(graph: Dict[int, Dict[int, float]],
source: int,
target: int,
graphnx,
stats: Counter=None) -> Tuple[Dict[int, float], Dict[int, int]]:
distances = {source: 0}
prev = dict()
potentials = dict()
labelled = {source}
while len(labelled) > 0:
u = -1
best = -1
for v in labelled:
if v not in potentials:
potentials[v] = geo_dist(graphnx, v, target)
if u == -1 or distances[v] + potentials[v] < best:
best = potentials[v] + distances[v]
u = v
labelled.remove(u)
if u == target:
break
scan(graph, u, distances, prev, labelled, stats)
return distances, prev
distances, prev = a_star(g, s, t, G)
print_route_and_visited(G, s, t, distances, prev)
Объяснение SourceCraftПредставленный фрагмент кода на Python реализует алгоритм A* для поиска кратчайшего пути в графе.
Функция geo_dist вычисляет географическое расстояние между двумя узлами графа, используя их координаты.
Функция a_star реализует сам алгоритм A*. Она принимает ориентированный граф, исходный и целевой узлы, а также дополнительный граф graphnx для вычисления географических расстояний. Алгоритм использует потенциалы (оценки расстояния до цели) для оптимизации поиска кратчайшего пути.
Этот код интересен тем, что демонстрирует применение алгоритма A* для решения задачи о кратчайшем пути с учётом географических расстояний между узлами.
Ну и сразу приведу
подробное объяснениеФункция geo_dist(graph, u, v) вычисляет географическое расстояние между двумя узлами графа:
coords_1 = (graph.nodes[u]['y'], graph.nodes[u]['x']) - извлекает координаты (широта, долгота) первого узла
coords_2 = (graph.nodes[v]['y'], graph.nodes[v]['x']) - извлекает координаты (широта, долгота) второго узла
geopy.distance.distance(coords_1, coords_2).m - вычисляет расстояние между координатами и возвращает результат в метрах
Эта функция используется как эвристическая оценка расстояния между узлами в алгоритме A*.
В общем тут внезапно полный фейл. Пора закругляться, кажется, что лучше не будет, пробуем самый последний алгоритм
Алгоритм ALTdef alt(graph: Dict[int, Dict[int, float]],
source: int,
target: int,
landmark_distances,
stats: Counter=None):
rev_graph = reversed_graph(graph)
distances_f = {source: 0}
prev_f = dict()
distances_b = {target: 0}
prev_b = dict()
scanned_f = set()
scanned_b = set()
labelled_f = {source}
labelled_b = {target}
best = float("inf")
best_f = source
best_b = target
u = source
v = target
potentials = dict()
while len(labelled_f) > 0 or len(labelled_b):
if distances_f[u] < distances_b[v]:
if u in scanned_b:
break
labelled_f.remove(u)
scan(graph, u, distances_f, prev_f, labelled_f, stats)
for p, l in graph[u].items():
if p in distances_b and distances_f[u] + distances_b[p] + l < best:
best_f = u
best_b = p
best = distances_f[u] + distances_b[p] + l
scanned_f.add(u)
for x in labelled_f:
if x not in potentials:
potential_f = 0
potential_b = 0
for p in landmark_distances:
potential_f = max(potential_f, landmark_distances[p][target] - landmark_distances[p][x])
potential_b = max(potential_b, landmark_distances[p][x] - landmark_distances[p][source])
potentials[x] = 0.5 * (potential_f - potential_b)
u = min(labelled_f, key=lambda x: distances_f[x] + potentials[x])
else:
if v in scanned_f:
break
labelled_b.remove(v)
scan(rev_graph, v, distances_b, prev_b, labelled_b, stats)
for p, l in rev_graph[v].items():
if p in distances_f and distances_b[v] + distances_f[p] + l < best:
best_f = p
best_b = v
best = distances_b[v] + distances_f[p] + l
scanned_b.add(v)
for x in labelled_b:
if x not in potentials:
potential_f = 0
potential_b = 0
for p in landmark_distances:
potential_f = max(potential_f, landmark_distances[p][target] - landmark_distances[p][x])
potential_b = max(potential_b, landmark_distances[p][x] - landmark_distances[p][source])
potentials[x] = 0.5 * (potential_f - potential_b)
v = min(labelled_b, key=lambda x: distances_b[x] - potentials[x])
best_path = [best_f]
cur = best_f
while cur != source:
cur = prev_f[cur]
best_path.append(cur)
best_path = list(reversed(best_path))
cur = best_b
if cur != best_path[-1]:
best_path.append(cur)
while cur != target:
cur = prev_b[cur]
best_path.append(cur)
return distances_f, distances_b, best_path, best
Функция alt реализует алгоритм поиска кратчайшего пути в графе. Она принимает на вход граф, представленный в виде словаря, исходную и целевую вершины, а также дополнительные параметры.
Алгоритм использует двунаправленный подход: он одновременно ищет пути от исходной вершины к целевой и от целевой вершины к исходной. Это позволяет ускорить поиск кратчайшего пути.
В процессе работы алгоритм строит два дерева: одно для путей от исходной вершины, другое — для путей от целевой вершины. Он также использует потенциалы для оптимизации поиска. Потенциалы представляют собой оценки минимального расстояния от вершины до целевой вершины.
Когда алгоритм находит вершину, которая присутствует в обоих деревьях, он останавливается и возвращает кратчайший путь между исходной и целевой вершинами.
Опять фейл, никакой конкретной инфы о конкретно об алгоритме ALT, действительно каркас про двунаправленность и про то, что ищем кратчайшие пути -- верно, но по содержательной части пусто. Смотрим на подробности
Подробное объяснение SourceCraftrev_graph = reversed_graph(graph)
Создаётся обратный граф, где направления всех рёбер изменены на противоположные. Это нужно для обратного поиска от target к source.
distances_f = {source: 0}
prev_f = dict()
distances_b = {target: 0}
prev_b = dict()
scanned_f = set()
scanned_b = set()
labelled_f = {source}
labelled_b = {target}
distances_f и distances_b — словари текущих минимальных расстояний от source и до target соответственно.
prev_f и prev_b — словари предшественников для восстановления пути.
scanned_f и scanned_b — множества вершин, которые уже полностью обработаны.
labelled_f и labelled_b — множества вершин, до которых найдены пути, но ещё не обработаны.
best = float("inf")
best_f = source
best_b = target
Инициализация переменных для отслеживания лучшего пути: best — текущая минимальная длина пути, best_f и best_b — вершины, соединяющие прямой и обратный пути.
u = source
v = target
potentials = dict()
u и v — текущие вершины для обработки в прямом и обратном поиске. potentials — словарь потенциалов для вершин.
while len(labelled_f) > 0 or len(labelled_b):
Цикл продолжается, пока есть непросканированные вершины в любом из направлений.
if u in scanned_b:
break
Если текущая вершина u уже просканирована в обратном направлении, путь найден, и цикл прерывается.
labelled_f.remove(u)
scan(graph, u, distances_f, prev_f, labelled_f, stats)
Вершина u удаляется из множества непросканированных и обрабатывается функцией scan, которая обновляет расстояния до соседей.
for p, l in graph[u].items():
if p in distances_b and distances_f[u] + distances_b[p] + l < best:
best_f = u
best_b = p
best = distances_f[u] + distances_b[p] + l
Проверяются соседи u. Если для соседа p уже известно расстояние в обратном направлении, вычисляется возможная длина пути через u и p. Если она меньше текущей лучшей, обновляются best_f, best_b и best.
scanned_f.add(u)
Вершина u помечается как полностью обработанная.
for x in labelled_f:
if x not in potentials:
potential_f = 0
potential_b = 0
for p in landmark_distances:
potential_f = max(potential_f, landmark_distances[p][target] - landmark_distances[p][x])
potential_b = max(potential_b, landmark_distances[p][x] - landmark_distances[p][source])
potentials[x] = 0.5 * (potential_f - potential_b)
Для всех непросканированных вершин вычисляются потенциалы, если они ещё не вычислены. Потенциал используется для оценки расстояния от вершины до цели с учётом ориентиров.
u = min(labelled_f, key=lambda x: distances_f[x] + potentials[x])
Выбирается следующая вершина для обработки с минимальной оценкой distances_f[x] + potentials[x].
Аналогично прямому шагу, но с использованием обратного графа и вычислением потенциалов с противоположным знаком.
best_path = [best_f]
cur = best_f
while cur != source:
cur = prev_f[cur]
best_path.append(cur)
best_path = list(reversed(best_path))
Строится путь от source до best_f с использованием словаря prev_f.
cur = best_b
if cur != best_path[-1]:
best_path.append(cur)
while cur != target:
cur = prev_b[cur]
best_path.append(cur)
К пути добавляется путь от best_b до target с использованием словаря prev_b.
return distances_f, distances_b, best_path, best
Функция возвращает:
distances_f: расстояния от source до всех вершин.
distances_b: расстояния от всех вершин до target.
best_path: кратчайший путь от source до target.
best: длина кратчайшего пути.
Уже не такой фейл, но всё еще. Дело в том, что нет описания именно особенности ALT. Указанное описание подходит для двунаправленного A*, но вот что такого особенного происходит в ALT, а именно как вычисляются нижние оценки расстояний не указано, а в этом самая суть.
Я явно ожидал меньшего, но всё же видны очевидные границы применимости. В целом это определённо очень хороший инструмент. Но всё-таки как и отметили хабровчане то как это было внедрено оставляет вопросы. Раньше в рекомендациях авторам был пункт про рекламу своих каналов/блогов, что хорошим тоном является сделать ссылку в самом конце -- кому действительно интересно дочитает и подпишется, всё остальное обычно воспринимается в штыки, с чем я полностью согласен. И вот большая неубираемая красная кнопка с логотипом у каждого сниппета также навязчиво воспринимается, в общем пожалуйста сделайте с этим чот-нибудь! Ну и следуя рекомендации
ссылка на мой тг