Операция выполнена!
Закрыть
info@vsetut.pro
Стать автором
Вернуться

[Перевод] Структуры данных на практике. Глава 6: Стеки и очереди

05.03.2026 08:11:24 | Хабр
Хабы: Программирование, Клиентская оптимизация, Программирование микроконтроллеров, Процессоры

«Простота — требование, необходимое для обеспечения надёжности», — Эдсгер Дейкстра

Невидимая структура данных

В каждой программе используется стек — стек вызовов. Каждый вызов функции записывает в стек кадр, каждый возврат извлекает его. Он настолько фундаментален, что мы редко о нём задумываемся.

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

Однажды я отлаживал вылет прошивки во встраиваемой системе RISC-V. У системы был планировщик задач, использующий очередь для управления ожидающими задачами. При большой нагрузке система вылетала с переполнением стека.

Переполнение стека? Очередь должна была находиться в куче, а не в стеке.

Проблема заключалась не в самой очереди, а в том, как она была реализована. Для очереди использовался связанный список, и каждый вызов malloc() выполнял распределение из пула памяти, делившего пространство со стеком. Под нагрузкой очередь разрасталась, пул фрагментировался и рано или поздно стеку не оставалось места для роста.

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

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2026 - vsetut.pro