Allocator course

allocator_course.md

Allocator course

Нюансы

Курс будет с акцентом на Linux. Да мы возможно обсудим некоторые нюансы macOS/Windows, и вероятно часть задач можно будет сдать под ними.

Но в целом стоит понимать, что поддержка не Linux-а как платформы будет минимальна.

Можно воспользоваться WSL, также будет поддержка docker образа и сдачи домашек в нем.

Пререквизиты

В идеале вы прошли курс по C++ и операционным системам, или обладаете аналогичными знаниями.

Но не думаю, что возникнут проблемы, если у вас не было операционных систем, но вы прочитали cpumemory.pdf (всего 100 страниц, не поленитесь).

Так или иначе мы повторим некоторые из пререквизитов, как и что из них будет рассказываться, будет зависеть от средней подготовки студентов.

План лекций

Кратко повторим/узнаем то, что требуется для понимания курса

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

Лекции 1-2

• Про оперативную память, кеши, различие между SMP и NUMA архитектурой
• Про virtual memory, то как процесс операционной системы видит свою память и как это работает
• Про интерфейсы операционной системы для выделения памяти: mmap/unmap/etc и brk/sbrк
• Про global, static, stack, heap memory
• Про интерфейсы системного аллокатора такие как malloc/free/etc и operator new/delete/etc

Лекции 2-3

• Про выравнивание
• Про интерфейсы в языке new/delete expression
• Умные указатели
• Про std::allocator
• Про std::pmr::polymorphic_allocator

Узнаем про классические подходы к реализации однопоточных аллокаторов

Не для исторической справки, а потому что как раз они чаще всего и пишутся разработчиками под конкретные кейсы.

Лекция 4-5

• Про фрагментацию на уровне аллокатора
• bump arena
• fixed size pool
• free list и его различные имплементации

Лекция 5-6

• buddy
• slab
• Посмотрим примеры из linux kernel

Про проблемы связанные с многопоточностью, конкурентным доступом к аллокатору

Лекция 7

• Про сложность, проблемы при: thread local, mutex, spinlock, lockfree реализации
• Про классический подход на примере lfalloc

Посмотрим на системные аллокаторы

Лекция 8-10

• ptmalloc2 -- glibc, прежде всего проблемы которые в нем есть, и почему они не будут исправлены
• jemalloc -- FreeBSD libc, использующийся во множестве проектов Facebook и других компаний, про то как и какие проблемы ptmalloc2 он решает
• mimalloc -- достаточно простой, но эффективный системный аллокатор Microsoft
• tcmalloc -- аллокатор Google, интересен прежде всего тем что некоторые подходы значительно отличаются

Лекция 11

• Про GC и то какие подходы к аллокации используются там

Остальное может варьироваться от ваших желаний

К тому же некоторые лекции могут оказаться дольше и это как раз время про запас

В целом можно поговорить

• про то как IO подсистема работает с оперативной памятью
• про подходы к аллокациям и работе с памятью в render в частности и GPU в целом
  • stagging buffer
  • zombie list
  • аллокаторы buddy/slab/free-list
  • проблемы синхронизации
• особенности Windows? 🤮

Домашки

На языке C++, ревью выборочное/по просьбе, в целом в зависимости от моей загруженности и количества человек на курсе.

В остальном автоматическая проверка с открытыми тестами, санитайзерами, разными компиляторами, fuzzing-ом, все лишь бы верить, что в вашем коде нет багов. За улучшение тестов доп баллы.

1. На понимание первых лекций
2. Потыкать std::allocator, std::pmr, контейнеры с SSO оптимизацией
3. Не системные однопоточные аллокаторы на базе классических алгоритмов
4. Системный аллокатор, будут бенчмарки. Постепенно вы должны приблизить свою реализацию по производительности к одному из 4 системных аллокаторов (ptmalloc2, jemalloc, mimalloc, tcmalloc, а также моя собственная реализация, чтобы было честно) в конкретном тесте.
5. Если я успею сделать, будет опциональная домашка, написать GC для простого самописного интерпретируемого языка.

1, 2, 3 -- это темы, не конкретные задания, каждая их них будет включать набор домашек на не более чем вечер по обьему.

4 -- это задание которые предполагается что будет доступно вам в течение всего семестра и с получением новых знаний вы должны улучшать свои результаты в нем.

Оценивание

• На тройку нужно будет просто сделать все задания так, чтобы они прошли тесты.
• На четыре нужно будет сделать все + сделать в задании 4 что-то разумное, не в 100 раз хуже чем худший из рассмотренных аллокаторов в конкретном тесте.
• На отлично все то же самое, но вероятно хочется чтобы ваша реализация была хуже, уже не более чем в 2-10 раз, я думаю конкретные цифры могут отличаться от теста и тд, и в целом это не строгий критерий.

Экзамен

Вероятно он будет сразу после 11 лекции, в идеале хотелось бы чтобы вы к нему не готовились. Потому что хочется понять, что осталось не понятым.

Также могу пообещать, что по его результатам никому оценка снижена не будет. Но может быть повышена не более чем на 1 балл.

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