Date: Thu, 21 Jun 2012 17:01:50 +0300 From: Gleb Kurtsou <gleb.kurtsou@gmail.com> To: freebsd-fs@freebsd.org Subject: [RFC] tmpfs RB-Tree for directory entries Message-ID: <20120621140149.GA59722@reks>
next in thread | raw e-mail | index | archive | help
Hello, Here is patch for CURRENT replacing directory entry linked list with RB-Tree in tmpfs. Performance improvement varies for different workloads, it may be negligible for directories with small number of files or due to VFS name caching. http://people.freebsd.org/~gleb/tmpfs-nrbtree.1.patch This patch is unrelated to similar changes recently committed to DragonFly: https://bugs.dragonflybsd.org/issues/2375 http://gitweb.dragonflybsd.org/dragonfly.git/commitdiff/29ca4fd6da8bb70ae90d8e73ea3c47fda22491a7 My patch uses name hashes instead of comparing entries by file name, moreover it reuses the same hash value as directory entry offset and eliminates possible issue of duplicate directory offsets on 64-bit archs. In other words it makes VOP_READDIR on large directories faster for non-zero offsets. I'm willing to commit the patch and would appreciate if people actively using tmpfs give it a try. Thanks, Gleb. ** file_create test from DragonFly PR % time ~/file_create 10000 x tmpfs-file_create-rb + tmpfs-file_create-orig +------------------------------------------------------------------------+ | + | |x + | |xx + | |xx + +| |A| | | |MA_| | +------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 5 0.112 0.14 0.119 0.1234 0.012116105 + 5 2.551 2.734 2.551 2.5886 0.081309901 Difference at 95.0% confidence 2.4652 +/- 0.0847787 1997.73% +/- 68.7023% (Student's t, pooled s = 0.0581296) ** test1 -- create 5000 files, rename some of them, remove files time sh ~/test1.sh x tmpfs-test1-rb + tmpfs-test1-orig +------------------------------------------------------------------------+ | x x x + +++ | ||___MA_____| | | |_____________A______M______|| +------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 4 5.893 6.091 5.932 5.9535 0.093289871 + 4 6.49 7.006 6.987 6.8655 0.25058931 Difference at 95.0% confidence 0.912 +/- 0.327153 15.3187% +/- 5.49514% (Student's t, pooled s = 0.189074) test1.sh: #!/bin/sh for i in `jot 5000`; do echo $i > longername$i; done ls >/dev/null for i in `jot 899 100`; do mv longername$i longername1$i; done ls >/dev/null for i in `jot 899 100`; do mv longername2$i longername3$i; done ls >/dev/null for i in `jot 5000`; do rm longername$i 2>/dev/null; done
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20120621140149.GA59722>