Warum verwendet der Linux-Kernel die Datenstrukturen, die er ausführt?

Question

Der Linux-Kernel verwendet eine verknüpfte Liste für TCP und eine RB-Struktur für die Prozessplanung.

In Bezug auf die algorithmische Effizienz sind diese sinnvoll. Sie werden eine Reihe von Paketen nacheinander erhalten, so dass O (1) Einfügen am Ende der Liste nett ist.

Bei der Prozessterminierung verwendet der Completely Fair Scheduler einen Rot-Schwarz-Baum mit O (1) Zeit, um Aufgaben auszuwählen.

Soweit ich weiß, sind diese beiden nicht 'flach' implementiert - die verkettete Liste ist eine Gruppe von Knoten mit Zeigern zu anderen Knoten, genau wie der Baum. Das bedeutet, dass die Lokalität für diese Strukturen, soweit ich weiß, schlecht sein sollte.

Von dem, was ich gesehen habe Cache überwiegt oft algorithmische Effizienz.

Gibt es etwas über den Datensatz, für den Linux programmiert ist, der die algorithmische Effizienz dieser Strukturen die Cache-Effizienz anderer überwiegt?

Habe ich etwas falsch verstanden? Hat jemand profiliert?

Answer 1

Ich habe eine teilweise Antwort für die Verwendung von verknüpften Listen, und ich glaube, Sie werden einige interessante Informationen in this page about the CFS scheduler finden, insbesondere erwähnt, wie ein rot-schwarz-Baum has good worst-case time for operations such as insert, search, and delete, die tatsächlich scheint eine sehr wünschenswerte Eigenschaft für einen Scheduler .

Ich wette, dass ja der Kernel eine Menge Profiling gesehen hat und diese Datenstrukturen scheinen in der realen Welt gut zu funktionieren.

This blog post hat einige nette Daten über die Verwendung der verketteten Kernel-Listen. Diese Daten wurden anscheinend über 3 Tage bei normalem Gebrauch gesammelt, indem die Zähler jeder Operation durchgeführt wurden.

+--------------------+-----------+ 
|  Operation  | Frequency | 
+--------------------+-----------+ 
|  Empty Test  | 45%  | 
|  Delete  | 25%  | 
|  Add   | 23%  | 
| Iterate Start | 3.5%  | 
| Iterate Next  | 2.5%  | 
|  Replace  | 0.76%  | 
| Other Manipulation | 0.0072% | 
+--------------------+-----------+ 

Wie Sie Operationen tatsächlich Zugriff auf Elemente machen einen winzigen 6% der insgesamt fast die Hälfte, während das Einfügen und Löschen summieren sich sehen. Dies ist ein Anwendungsfall, bei dem verknüpfte Listen viel sinnvoller erscheinen. Beachten Sie, dass die Daten im gesamten Kernel gesammelt wurden, nicht speziell im TCP-Code, sodass die Gründe für eine verknüpfte Liste nicht bei jeder Verwendung identisch waren, sondern die aggregierten Daten deuten darauf hin, dass es sich insgesamt um sinnvolle Entscheidungen handelt.

Ich denke, es ist auch wichtig zu bedenken, dass das Design des Kernels in der Lage sein muss, von den kleinsten eingebetteten Geräten zu Supercomputern mit riesigen Datenmengen zu skalieren, wobei die algorithmische Effizienz die Caching-Probleme deutlich überwiegt .