[linux-l] mbox/Maildir/tar

Rocco Rutte pdmef at gmx.net
Mi Nov 28 10:42:14 CET 2007


Hi,

* Oliver Bandel wrote:
>Zitat von Rocco Rutte <pdmef at gmx.net>:
>> * Oliver Bandel wrote:

>> Bei ext3 mit dir_index macht z.B. Inode-Sortierung das Parsen bei 
>> mutt "mal eben" um Faktor 12-13 schneller, wenn man die Mails nicht 
>> im header cache hat. D.h. der Seek-Overhead ist wirklich extrem.

>Böse, böse.
>Das hätte ich nicht gedacht.
>Daß ext3 etwas langsamer als ext2 ist, hatte ich noch in Erinnerung.
>Daß das aber solche Erscheinungen gibt, war mir neu.
>habe aber ext3 bisher nur selten in gebrauch.

Das hat mit ext3 per se erstmal nichts zu tun. Siehe "dir_index": Wenn 
man explizit nach einem Feature fragt, muss man auch mit den 
Konsequenzen leben...

>> Directory hashing ist ja ganz sinnvoll, um Files schneller zu finden.
>> Aber mit B+-Bäumen (oder war das B*?) hat man im Prinzip eine einfach
>> verlinkte Liste mit einem Baum zum schnellen Zugriff "oben drüber".
>> Das müsste doch reichen. Statt dessen muss man jetzt alle Anwendungen
>> anpassen, die größere Mengen Files aus einem readdir()-Lauf
>> verarbeiten
>> wollen. :(

>hmhhhh... ich kenne den genauen Aufbau von ext3 nicht im Detail.
>Ich dachte durch Baumstruktur wäre das trotz Journalling noch recht
>schnell... hmhhh was meintest Du mit den Listen in Deiner Aussage da
>oben? hmhh, muss mir das ext3-Format wohl mal anschauen.

Der Baum wird benutzt, um zu einem Pfad die Datei möglichst schnell 
zu finden. Wenn das FS pro Verzeichnis eine verlinkte Liste hat und sich 
darin 10k Einträge befinden, dauert es lange; mit einem Baum oder z.B. 
Hashing hat geht das in O(log(n))/O(1) statt O(n) (bitte nicht schlagen 
wenn das nicht stimmt. :)

Um Seeking zu verhindern, muss man Daten in der Reihenfolge lesen 
wie sie auf der Platte stehen, also in der Regel nach Inode sortiert. 
Nach Inode sortieren muss man aber selbst machen, weil u.U. das FS bei 
readdir() eine beliebige Reihenfolge der Files liefert.

Gut, keine beliebige sondern meist nicht nach Inode. Wenn man einen Baum 
hat dann evtl. direkt schon alphabetisch sortiert, oder nach dem Hash 
des Dateinamens bei Hashtabellen.

MfG, Rocco



Mehr Informationen über die Mailingliste linux-l