git: use rb-tree for directory lookups

Francois Tigeot ftigeot at crater.dragonflybsd.org
Mon Jun 18 10:38:12 PDT 2012


commit 29ca4fd6da8bb70ae90d8e73ea3c47fda22491a7
Author: Johannes Hofmann <johannes.hofmann at gmx.de>
Date:   Tue May 22 23:37:55 2012 +0200

    use rb-tree for directory lookups
    
    * 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.
    
    * This patch uses a rb-tree keyed on the name of the searched file to
      speed up lookups
    
    * Besides this rb-tree implementation, a hash version was also tested.
      Both gave solid performance enhancements compared to the previous tmpfs
      implementation.
      The rb-tree version was the faster of the two and thus becomes the
      choosen one.
    
    * See issue 2375 for details and performance numbers
      https://bugs.dragonflybsd.org/issues/2375

Summary of changes:
 sys/vfs/tmpfs/tmpfs.h        |   23 +++++++++++-------
 sys/vfs/tmpfs/tmpfs_subr.c   |   43 ++++++++++++++++++++++++-----------
 sys/vfs/tmpfs/tmpfs_vfsops.c |    4 +-
 sys/vfs/tmpfs/tmpfs_vnops.c  |   50 ++++++++++++++++++++++-------------------
 4 files changed, 72 insertions(+), 48 deletions(-)

http://gitweb.dragonflybsd.org/dragonfly.git/commitdiff/29ca4fd6da8bb70ae90d8e73ea3c47fda22491a7


-- 
DragonFly BSD source repository





More information about the Commits mailing list