git: use rb-tree for directory lookups

Francois Tigeot ftigeot at
Mon Jun 18 10:38:12 PDT 2012

commit 29ca4fd6da8bb70ae90d8e73ea3c47fda22491a7
Author: Johannes Hofmann <johannes.hofmann at>
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
      The rb-tree version was the faster of the two and thus becomes the
      choosen one.
    * See issue 2375 for details and performance numbers

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(-)

DragonFly BSD source repository

More information about the Commits mailing list