Perché il kernel di Linux usa le strutture dati che fa?

Question

Il kernel Linux utilizza un elenco collegato per TCP e un albero RB per la pianificazione del processo.

In termini di efficienza algoritmica, questi hanno senso. Avrai un sacco di pacchetti uno alla volta, quindi l'inserimento di O (1) alla fine dell'elenco è bello.

Con la pianificazione dei processi, l'Utilissimo programma di pianificazione utilizza un albero nero rosso, con O (1) tempo per scegliere le attività.

Per quanto ne so nessuno di questi è implementato in modo "piatto" - la lista collegata è un gruppo di nodi con puntatori ad altri nodi, proprio come l'albero. Ciò significa che la località di queste strutture, per quanto ne so, dovrebbe essere povera.

Da quello che ho visto, la localizzazione della cache spesso supera l'efficienza algoritmica.

C'è qualcosa nel set di dati per cui è programmato Linux che renda l'efficienza algoritmica di queste strutture superiore all'efficienza della cache degli altri?

Sto fraintendendo qualcosa? Qualcuno ha profilato?

Answer 1

Ho una risposta parziale per l'uso di elenchi concatenati, e credo che troverete alcune informazioni interessanti in this page about the CFS scheduler, in particolare menziona come un albero rosso-nero has good worst-case time for operations such as insert, search, and delete che in effetti sembra una proprietà molto desiderabile per un programmatore .

Scommetto che, sì, il kernel ha visto un bel po 'di profilazione e quelle strutture dati sembrano funzionare bene nel mondo reale.

This blog post ha alcuni dati utili sull'utilizzo degli elenchi collegati del kernel. Questi dati sono stati raccolti apparentemente in 3 giorni di uso normale tenendo i contatori di ogni operazione eseguita.

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

Come si può vedere le operazioni effettivamente accedere agli elementi rappresentano una minuscola 6% del totale, mentre l'inserimento e cancellazione aggiungere fino a quasi la metà. Questo è un caso d'uso in cui le liste collegate iniziano ad avere molto più senso. Si noti che i dati sono stati raccolti attraverso l'intero kernel, non specificamente il codice TCP, quindi la logica di un elenco collegato potrebbe non essere stata la stessa ogni volta che è stata utilizzata, ma i dati aggregati suggeriscono che quelle erano scelte sensate nel complesso.

Penso che sia anche importante tenere presente che la progettazione del kernel deve essere in grado di scalare dai più piccoli dispositivi embedded ai supercomputer che gestiscono enormi quantità di dati, a quel punto le efficienze algoritmiche possono iniziare a superare di gran lunga i problemi di caching .