Ответ 1
У меня есть частичный ответ на использование связанных списков, и я считаю, что вы найдете интересную информацию в этой странице о планировщике CFS, в частности он упоминает, как красно-черное дерево has good worst-case time for operations such as insert, search, and delete, которое действительно кажется очень желательным свойством для планировщика.
Я бы пообещал, что да, ядро провело довольно много профилирования, и эти структуры данных, похоже, хорошо работают в реальном мире.
В этом сообщении в блоге есть интересные данные об использовании связанных с ядром списков. Эти данные, по-видимому, собирались в течение 3 дней обычного использования, сохраняя при этом счетчики каждой операции.
+--------------------+-----------+
| Operation | Frequency |
+--------------------+-----------+
| Empty Test | 45% |
| Delete | 25% |
| Add | 23% |
| Iterate Start | 3.5% |
| Iterate Next | 2.5% |
| Replace | 0.76% |
| Other Manipulation | 0.0072% |
+--------------------+-----------+
Как вы можете видеть, что операции, фактически получающие доступ к элементам, составляют 6% от общей суммы, в то время как вставка и удаление составляют почти половину. Это пример использования, когда связанные списки начинают иметь гораздо больше смысла. Обратите внимание, что данные были собраны по всему ядру, а не только по TCP-коду, поэтому логическое обоснование для связанного списка может быть не одинаковым при каждом его использовании, но совокупные данные говорят о том, что все они были разумными.
Я думаю, что также важно иметь в виду, что дизайн ядра должен иметь возможность масштабировать от самых маленьких встроенных устройств до суперкомпьютеров, обрабатывающих огромные объемы данных, и в этот момент эффективность алгоритмического анализа может серьезно перевесить проблемы кэширования.