> С другой стороны бинарный поиск в отсортированном списке - так себе затея,
> т.е. это tradeoff.
> Вот в жизни не поверю, что у них число вставок-удалений превышает число
> поисков.

Да даже если и превышает, ну будет массив указателей на строки размером на 10-30 строк, там вставка не будет сильно медленней, чем в списках. Из-за высокой локальности оно может ещё и быстрее оказаться.

> возможно, меньшая фрагментация памяти - возможность pre-alloc/pool блоков одинакового
> размера. при высокой нагрузке это может быть важно.

Почитал про Pool Allocator, спасибо за место, где в связном списке больше смысла, чем в простом массиве. Но не могу понять по коду nginx, чанки ли там или просто список сам по себе.

> Выгода от связного списка есть, только если он intrusive, как в ядре линуховом.

А какая? Есть какая информация в духе "вот тут мы заменили X на linked list -- и стало слегка/гораздо быстрее", может в LKLM где-нибудь?

>> Раз перешли на них, должна быть хорошая причина, о которой я не догадываюсь
> Теперь структуры данных привели к одному виду.

Но зачем было в принципе список использовать? Почему не перейти к массивам? Почему в принципе был выбран именно список? А то вдруг он выбран давным-давно и теперь все хотели бы заменить, но обратная совместимость и не чини что работает.