[Перевод] Структуры данных на практике. Глава 6: Стеки и очереди
«Простота — требование, необходимое для обеспечения надёжности», — Эдсгер ДейкстраНевидимая структура данныхВ каждой программе используется стек — стек вызовов. Каждый вызов функции записывает в стек кадр, каждый возврат извлекает его. Он настолько фундаментален, что мы редко о нём задумываемся.Но когда нам нужен собственный стек или очередь, крайне важно правильно выбрать реализацию.Однажды я отлаживал вылет прошивки во встраиваемой системе RISC-V. У системы был планировщик задач, использующий очередь для управления ожидающими задачами. При большой нагрузке система вылетала с переполнением стека.Переполнение стека? Очередь должна была находиться в куче, а не в стеке.Проблема заключалась не в самой очереди, а в том, как она была реализована. Для очереди использовался связанный список, и каждый вызов malloc() выполнял распределение из пула памяти, делившего пространство со стеком. Под нагрузкой очередь разрасталась, пул фрагментировался и рано или поздно стеку не оставалось места для роста.Как же мы устранили проблему? Заменили очередь на основе связанного списка кольцевым буфером — очередью на основе массива фиксированного размера, получив при этом отсутствие динамического распределения, предсказуемое использование памяти и десятикратный рост скорости. Читать далее
03:45
03:24
15:50
