Кейс (кратко): дать студентам две реализации одного алгоритма (быстрая сортировка) — рекурсивную и итеративную — и попросить найти причину сбоев на больших входных данных. Ниже — конкретный код, анализ возможных ошибок (stack overflow, UB, неэффективные аллокаторы), набор тестов и метрики/инструменты для локализации.
1) Код: рекурсивная (с тонкой ошибкой)
```cpp
// quick_rec.cpp — потенциально buggy
#include #include
void quick_rec(std::vector& a, std::size_t l, std::size_t r) {
if (l >= r) return;
std::size_t i = l, j = r;
int pivot = a[l + (r - l) / 2]; // выбор среднего
while (i <= j) {
while (a[i] < pivot) ++i;
while (a[j] > pivot) --j;
if (i <= j) {
std::swap(a[i], a[j]);
++i; if (j==0) break; --j; // защита от underflow в unsigned — но тут может быть ошибка
}
}
if (j > l) quick_rec(a, l, j);
if (i < r) quick_rec(a, i, r);
}
void quick_rec_start(std::vector& a){
if (a.empty()) return;
quick_rec(a, 0, a.size() - 1);
}
```
Заметки по этому варианту:
- Частая ошибка: вызов `quick_rec(a, 0, a.size()-1)` без проверки на пустой вектор приводит к `r = SIZE_MAX` для пустого `a` — OOB и UB. (проверьте вызов `quick_rec_start` — у меня есть проверка, но студенты часто её забывают).
- Рекурсия в худшем случае (на уже отсортированных данных при плохом pivot) даёт глубину $O(n)$ — риск переполнения стека (stack overflow) при больших $n$.
- Использование `std::size_t` и операций `--j` без аккуратной проверки может привести к underflow (wrap) и доступу по огромному индексу — UB.
2) Код: итеративная (эквивалент, без рекурсии)
```cpp
// quick_iter.cpp
#include #include #include #include
void quick_iter(std::vector& a) {
if (a.empty()) return;
std::stack<std::pair> st;
st.emplace(0, a.size() - 1);
while (!st.empty()) {
auto [l, r] = st.top(); st.pop();
if (l >= r) continue;
std::size_t i = l, j = r;
int pivot = a[l + (r - l) / 2];
while (i <= j) {
while (a[i] < pivot) ++i;
while (a[j] > pivot) --j;
if (i <= j) { std::swap(a[i], a[j]); ++i; if (j==0) break; --j; }
}
if (l < j) st.emplace(l, j);
if (i < r) st.emplace(i, r);
}
}
```
Почему итеративная версия стабильнее:
- Нет глубокой системной рекурсии — стек мы контролируем в куче (std::stack), что уменьшает риск системного stack overflow.
- Всё ещё возможен худший случай по времени $O(n^2)$, но не системный crash от глубины вызовов.
3) Возможные источники UB и проблем (на что обратить внимание)
- Подстановка индексов unsigned без корректной проверки (underflow): при `j==0` и `--j` получится большой индекс — OOB.
- Вызов с `r = a.size()-1` при пустом массиве: `a.size()-1` это $SIZE\_MAX$ — UB при доступе.
- Глубокая рекурсия (глубина до $n$) → stack overflow (особенно при $n\gtrsim 10^5$ в типичной среде).
- Некорректный pivot, приводящий к сильно несимметричным разбиениям и худшему случаю.
- Неэффективные аллокаторы: если реализация делает копирование подмассивов (например, `std::vector` slice в рекурсии), то на большом $n$ расход памяти и количество аллокаций растут; возможен `std::bad_alloc`.
- Использование указателей/итераторов на элементы, которые могут быть инвалидацированы при перестановках (реже для вектора при swap элементов, но важно для container-reallocation).
4) Набор тестов (обязательные кейсы)
- Малые массивы: $n=0,1,2$.
- Рандом: $n=10^3,10^5,10^6$ случайных чисел.
- Уже отсортированы Ascending и Descending (патологично для quicksort).
- Много одинаковых элементов (например, все элементы = 0).
- Непосредственно вход, приводящий к краху: бенчмарки для постепенного увеличения $n$ (binary search по размеру).
Примеры генераторов (псевдо):
- sorted: for i in [0..n-1] a[i]=i
- reversed: a[i]=n-i
- duplicates: a[i]=42
- random: uniform distribution
5) Метрики и инструменты для локализации
- Воспроизводимость:
- Сбор минимального входа, который вызывает падение (уменьшать $n$ бинарным поиском).
- Сбор времени выполнения: замер wall-clock и CPU с `std::chrono`.
- Память:
- peak RSS: `getrusage(RUSAGE_SELF, &ru)` или чтение `/proc//status` (VmPeak).
- стек: `ulimit -s` и изменение `ulimit -s` для воспроизведения (падение при малом стеке подтвердит stack overflow).
- Инструменты отладки UB:
- Скомпилировать с Sanitizers: `-fsanitize=address,undefined -g -O1` — быстро выявляют OOB, use-after-free, UB.
- ASan/UBSan отчёты укажут точную строку.
- Профилирование аллокаций:
- valgrind --tool=massif (для peak heap), massif-visualizer.
- jemalloc или tcmalloc с включённым профайлером allocs/count.
- LD_PRELOAD или библиотека для подсчёта malloc/free.
- Отслеживание глубины рекурсии:
- вставить глобальные счётчики: current_depth++/-- и track max_depth (atomics если параллельно).
- Лог крашей:
- gdb backtrace при SIGSEGV: `gdb --args ./a.out` + run, bt.
- core dump (`ulimit -c unlimited`) и анализ core в gdb.
- Проверка на underflow/overflow индексов:
- Включить дополнительные assert’ы: `assert(l <= r && r < a.size());`
- Компиляторные предупреждения `-Wall -Wextra -Wshadow`.
6) Пошаговая методика локализации проблемы (рекомендация студентам)
1. Запустить тесты на маленьких $n$ — убедиться, что логика верна.
2. Запустить проблемный вход (большой) под ASan/UBSan — читать отчёт.
3. Если падение — посмотреть bt в gdb, проверить глубину стека и значения индексов.
4. Если ASan не показал (например, stack overflow без OOB), уменьшать стек `ulimit -s` и повторять чтобы воспроизвести; добавить счётчик рекурсии чтобы узнать max depth.
5. Если подозрение на аллокации — запускать massif / jemalloc profiling, смотреть peak heap и количество аллокаций.
6. Минимизировать вход бинарным поиском по размеру, чтобы получить минимальный reproducer.
7) Примеры конкретных метрик для записи в отчёт студентов
- Время выполнения (ms): замер для каждого входа (rand, sorted, reversed).
- Peak RSS (MB): через /proc или getrusage.
- Max recursion depth (целое): вставленный счётчик.
- Количество malloc/free и total allocated bytes (через профайлер).
- ASan/UBSan отчёт (файл).
8) Короткие советы по исправлению
- Всегда проверять пустой контейнер перед `size()-1`.
- Для рекурсивного quicksort: рекурсивно вызывать сначала на меньшей части, затем на большей — чтобы ограничить дополнительную глубину (tail recursion optimization): всегда рекурсировать на меньшем фрагменте, а обрабатывать больший итеративно/в цикле.
- Использовать итеративную реализацию или явно контролируемый стек для больших n.
- Для pivot: медиана из трёх или рандомизация, чтобы избежать худших разбиений.
- Добавить assert’ы и компиляцию с Sanitizers в CI.
Заключение (одно предложение): предложите студентам найти и исправить баги, применяя шаги выше: воспроизвести, запустить sanitizers, измерить глубину рекурсии и память, минимизировать reproducer — это учит практической отладке UB, проблем со стеком и неэффективных аллокаторов.