From owner-freebsd-bugs Sat Aug 31 14:59:52 2002 Delivered-To: freebsd-bugs@freebsd.org Received: from mx1.FreeBSD.org (mx1.FreeBSD.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id D7A5A37B400 for ; Sat, 31 Aug 2002 14:59:49 -0700 (PDT) Received: from salmon.maths.tcd.ie (salmon.maths.tcd.ie [134.226.81.11]) by mx1.FreeBSD.org (Postfix) with SMTP id C243F43E65 for ; Sat, 31 Aug 2002 14:59:48 -0700 (PDT) (envelope-from dwmalone@maths.tcd.ie) Received: from walton.maths.tcd.ie by salmon.maths.tcd.ie with SMTP id ; 31 Aug 2002 22:59:47 +0100 (BST) Date: Sat, 31 Aug 2002 22:59:47 +0100 From: David Malone To: Mike Harding Cc: freebsd-bugs@FreeBSD.org Subject: Re: misc/42167: du uses linear search for duplicate inodes - very slow! Message-ID: <20020831215946.GB34455@walton.maths.tcd.ie> References: <200208310300.g7V30AUT094327@freefall.freebsd.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200208310300.g7V30AUT094327@freefall.freebsd.org> User-Agent: Mutt/1.3.25i Sender: owner-freebsd-bugs@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org On Fri, Aug 30, 2002 at 08:00:10PM -0700, Mike Harding wrote: > Here's a unified diff, for perusal by the merely curious... the general > approach is to replace the single unordered list with HASHSIZE unordered > lists. The hashing function is a simple divide, which should be > sufficient as inodes should be very evenly distributed (sequential, > no?). The use of 'abs' below may be unnecessary if ino_t is guaranteed > to be unsigned, I am unaware of convention here... I wonder if it would be better to use something like a heap or some sort of tree, rather than a fixed size hash table? David. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-bugs" in the body of the message