From owner-freebsd-fs@FreeBSD.ORG Thu Jun 21 14:01:54 2012 Return-Path: Delivered-To: freebsd-fs@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 8F0D4106564A for ; Thu, 21 Jun 2012 14:01:54 +0000 (UTC) (envelope-from gleb.kurtsou@gmail.com) Received: from mail-ey0-f182.google.com (mail-ey0-f182.google.com [209.85.215.182]) by mx1.freebsd.org (Postfix) with ESMTP id 1965C8FC0C for ; Thu, 21 Jun 2012 14:01:53 +0000 (UTC) Received: by eabm6 with SMTP id m6so321238eab.13 for ; Thu, 21 Jun 2012 07:01:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:subject:message-id:mime-version:content-type :content-disposition:user-agent; bh=SWs/ElDSHh/CH2JqlPKIUwDZ/n7p0dfEJ7pf0IP6pP0=; b=r+OlNtkEAlo+8yzztgHV2354VASLlYPfyZEb5LjcUMVhpwwelecxj/bYTyXPPqMzGP o1MLcOMII7+68wdGCt7vOx8tzu5r9YPUW4yaU8NXIM+Rih9WsE+cgULQPIRQQVm0cU6E ff+AeVAM0EhX88Yndljt0CVUiItjcn2NMLllayvaW1ontPtLZ6/ORRYVpCkhVpOeeqzd zXDobTXihw4V6qAVwinqAlt0mGQhZuAWScJCa2qd/yAIgM/SgBZokNesAL/kV+DBNBg0 ag5PLHtYyMnvMowAahKK+XhQMfxtT1F0N59vZ4Rfedixs7BxAK+32kxYMDBrFMPf7edk 7/vw== Received: by 10.152.105.173 with SMTP id gn13mr26525922lab.20.1340287312889; Thu, 21 Jun 2012 07:01:52 -0700 (PDT) Received: from localhost ([78.157.92.5]) by mx.google.com with ESMTPS id b3sm18632818lbh.6.2012.06.21.07.01.51 (version=SSLv3 cipher=OTHER); Thu, 21 Jun 2012 07:01:51 -0700 (PDT) Date: Thu, 21 Jun 2012 17:01:50 +0300 From: Gleb Kurtsou To: freebsd-fs@freebsd.org Message-ID: <20120621140149.GA59722@reks> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Subject: [RFC] tmpfs RB-Tree for directory entries X-BeenThere: freebsd-fs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Filesystems List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 21 Jun 2012 14:01:54 -0000 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