hubertf's NetBSD Blog
Send interesting links to hubert at feyrer dot de!
[20080904] Speeding up operations with directory hashing
While working on UDF, Reinoud Zandijk has added routines to speed up directory operations. Remember that in FFS, directories are list of struct dirent entries that are stored one after another. This makes lookup sequential, deleting leaves holes, and inserting needs to check for possible holes. In other words: it's suboptimal. The proper solution would be to move some tree-based directory format, but that's not around the corner - file systems like SGI's XFS have that, and anyone's welcome to do the work on FFS.

Another option to mitigate the suboptimal on-disk format is to use in-memory caching and fast lookup, which is just what Reinoud did. His runs of the "postmark" benchmark show some impressive speedups:

What Old New
File create: 2/s 208/s
File create alone: 4/s 230/s
File create + transaction: 1/s 318/s
File read: 1/s 330/s
File append: 1/s 336/s
File delete: 2/s 208/s
File delete alone: 9/s 970/s
File delete + transaction: 1/s 348/s
Data read: 3 kb/s 283kb/s
Data written: 14kb/s 1150kb/s

See the commit log for more information.

P.S.: Someone please add wikipedia pages for FFS/UFS!

P.P.S.: Yes, this has been in UFS/FFS as "dirhash" for some time

[Tags: ]

Disclaimer: All opinion expressed here is purely my own. No responsibility is taken for anything.

Access count: 27790414
Copyright (c) Hubert Feyrer