Опубликовано: Mon, 11 May 2026 07:47:42 GMT
Канал: Все статьи подряд / Программирование микроконтроллеров / Хабр

«Задача абстракции — не быть расплывчатой, а создать новый семантический уровень, на котором можно достичь абсолютной точности», — Эдсгер ДейкстраВзрывной рост количества промахов кэшаПри определении топологии сети для обхода 500 коммутаторов нашей системе требовалось 37,5 миллисекунды. Вроде бы это не так медленно, если не учитывать количество промахов кэша: 8,5 миллиона. При 500 узлах это 17 тысяч промахов на узел.Структура данных была фундаментально неподходящей для этой задачи.Работа инструмента была простой: определение топологии сети при помощи обхода графа соединённых устройств. У каждого коммутатора было до 48 портов, а нам нужно было при помощи поиска в ширину найти все доступные устройства из начальной точки.Реализация была как по учебнику — список смежности со стандартным BFS. В случае сети из 500 коммутаторов (в среднем по 12 соединений у каждого) статистика была такой: 8,5 миллиона промахов кэша на 500 узлов. Это 17 тысяч промахов кэша на узел!Я переписал этот код, реализовав графовое представление, учитывающее кэш. Результаты: код стал в 3,75 раз быстрее, а количество промахов кэша уменьшилось в 7 раз.В этой главе мы поговорим об эффективном описании и обходе графов. Читать далее]]>

https://habr.com/ru/articles/1030626/