Hacker News Digest

Rust: «неразумная» скорость сортировки

• Сортировка в Rust быстрее C++ и Go благодаря LLVM, агрессивному векторизатору и ручным оптимизациям.
• Алгоритм: pdqsort (pattern-defeating quicksort) + векторизованный партиционер.
• Ключевые приёмы:
  • 128-битные SIMD-операции (SSE/AVX) для фильтрации элементов;
  • branchless-код, предикты, минимизация кэш-промахов;
  • специализированные пути для малых типов (u8, u16, u32, u64, f32, f64) и копируемых структур;
  • ручная развёртка циклов, инлайн, отказ от стандартных абстракций.
• Сравнение: на случайных u64 Rust ~2× быстрее libstdc++, ~3× быстрее Go; на почти отсортированных — ещё больше.
• Память: всё делается in-place, доп. буфер 1 КБ максимум.
• Сложность: O(n log n) в среднем, O(n log n) worst-case (pdqsort гарантирует).
• Код открыт, можно подсмотреть и перенести на другие языки.

• Универсальный лайфхак: «сначала отсортируй данные» — и задача часто сводится к O(log n).
• Но глобальная сортировка дороже с ростом объёма; иногда проще пересмотреть подход или использовать хэш-таблицу.
• Современные unstable-sort и foldhash настолько быстры, что ручные оптимизации часто проигрывают и требуют лишней памяти.
• Для 4 уникальных значений подсчёт или perfect-hash проще и быстрее полной сортировки; эксперимент ставит границы, а не решает продакшен-задачу.

FFmpeg/asm-lessons — репозиторий с уроками по ассемблеру для FFmpeg.
Цель: научиться писать высокопроизводительные рутины на x86-64, ARM и других архитектурах, ориентированные на мультимедиа-задачи.

Содержание (кратко):

• Уроки: от базовых инструкций до векторных расширений (SSE/AVX, NEON).
• Примеры: реализация IDCT, фильтров, цветового преобразования.
• Тесты: юнит-тесты и бенчмарки для сравнения C vs asm.
• CI: автоматическая проверка на x86-64 и ARM через GitHub Actions.

Как начать:

1. Клонируйте репо.
2. Установите nasm, yasm или llvm-mingw.
3. Соберите пример: make lesson01.

Полезные ссылки:

• Документация FFmpeg
• x86 SIMD
• ARM NEON

• Пользователи восхищаются масштабом FFmpeg и экономией вычислений даже при небольших улучшениях.
• Обсуждаются случаи, когда ручная сборка быстрее intrinsic’ов, и инструменты для поиска «горячих точек».
• Некоторые ждали более глубокой связи с FFmpeg, а не общее введение в ассемблер.
• Поднимаются вопросы портативности (пока только x86-64), необходимости математических подготовок и перегруженности NASM-макросами.
• Большинство соглашается: писать LLVM IR вручную нет смысла, проще использовать inline-assembly или векторные инструкции.

Как обогнать memcpy

Профилируя Shadesmar, увидел: при больших (>512 КБ) сообщениях 97 % времени уходит на memcpy между процессной и разделяемой памятью. Решил ускорить копирование.

---

Разбор memcpy

perf показал:
__memmove_avx_unaligned_erms — это memcpy через memmove, AVX, 32 байта за раз, поддержка не выровненных блоков и ERMS (железный цикл REP MOVSB).

• memmove выбран, т.к. допускает перекрытие.
• Для <4 КБ используется SSE2, иначе — REP MOVSB + AVX.
• Не-временные (NT) инструкции и prefetcht0 уменьшают кэш-промахи.

---

Способ 1: простой REP MOVSB

void _rep_movsb(void *d, const void *s, size_t n) {
  asm volatile("rep movsb"
               : "=D"(d), "=S"(s), "=c"(n)
               : "0"(d), "1"(s), "2"(n)
               : "memory");
}

Тот же цикл, что и в glibc, но без лишней логики.

• Часть выгоды даёт отказ от лишнего копирования: часто данные можно использовать на месте.
• Несколько участников отмечают, что без контроля кэшей и правильной сериализации бенчмарки теряют смысл.
• График в конце вызывает сомнения: скачки пропускной способности выглядят неправдоподобно.
• Для IPC обсуждают zero-copy через размещение данных сразу в shared memory (Iceoryx, Boost.Interprocess, DPDK).
• Большинство сходится к выводу: для обычных задач лучше довериться стандартному memcpy/std::memcpy, особенно в glibc.