Bug #2375

Wishlist: tmpfs directory lookup optimization

Added by vsrinivas about 2 years ago. Updated about 2 years ago.

Status:ResolvedStart date:05/23/2012
Priority:NormalDue date:
Assignee:-% Done:

100%

Category:-
Target version:-

Description

tmpfs directories are structured as lists of directory entries; this leads to linear lookup costs. Directories with many files become fairly expensive to operate on.

http://leaf.dragonflybsd.org/~vsrinivas/tmpfs5.diff is a patch that introduces a 64-wide hash table (of lists) to speed up lookups. The patch is currently littered with debugging cruft and could benefit from cleaning.

http://leaf.dragonflybsd.org/~hofmann/tmpfs_rbtree.diff is a cleaner patch that uses an RB-tree, keyed on the name of the file in question.

Both approaches are solid improvements over the current lists, but could use some testing (benchmarking) to determine which is worth applying. The hash list patch has had many hours of fsstress testing; it now works well. The tree patches at the same points.

History

#1 Updated by Johannes.Hofmann about 2 years ago

Both, the hash based version and my initial tree based one have an issue with renames onto an existing file (e.g. touch a; touch b; mv b a; rm b).

A fixed tree based version is available at http://leaf.dragonflybsd.org/~hofmann/tmpfs_rbtree1.diff
This version also gets rid of the TAILQ and maintains directory entries only in the rb-tree.

I did some performance tests on real hardware with a minimal C-program (http://leaf.dragonflybsd.org/~hofmann/file_create.c) with following results:

tmpfs as in master (4018c6eddd):
hofmann@blob:/mnt/bla >time file_create 50000

real 1m16.594s
user 0m0.617s
sys 1m14.681s

tmpfs as in master (ae879fe6cd + tmpfs5.diff + compile fixes):
hofmann@blob:/mnt/bla >time /home/hofmann/test/file_create 50000

real 0m5.706s
user 0m0.359s
sys 0m5.211s

tmpfs_rb no tailq (4018c6eddd + tmpfs_rbtree1.diff):
hofmann@blob:/mnt/bla >time /home/hofmann/test/file_create 50000

real 0m3.396s
user 0m0.195s
sys 0m3.203s

#2 Updated by ftigeot about 2 years ago

  • Status changed from New to Resolved
  • % Done changed from 0 to 100

Pushed in commit 29ca4fd6da8bb70ae90d8e73ea3c47fda22491a7

Also available in: Atom PDF