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