This message generated a parse failure. Raw output follows here. Please use 'back' to navigate. From devnull@lkml.org Wed Jun 5 08:24:06 2024 Received: from spaans.ds9a.nl (adsl-xs4all.ds9a.nl [213.84.159.51]) by kylie.puddingonline.com (8.11.6/8.11.6) with SMTP id g8IMHRX15269 for ; Thu, 19 Sep 2002 00:17:27 +0200 Received: (qmail 1061 invoked from network); 18 Sep 2002 08:31:03 -0000 Received: from unknown (HELO spaans.ds9a.nl) (3ffe:8280:10:360:202:44ff:fe2a:a1dd) by mayo.ipv6.ds9a.nl with SMTP; 18 Sep 2002 08:31:03 -0000 Received: (qmail 15794 invoked by uid 1000); 17 Sep 2002 21:36:55 -0000 Received: (maildatabase); juh Received: (qmail 31160 invoked by alias); 15 Jul 2002 04:38:23 -0000 Received: (qmail 31157 invoked from network); 15 Jul 2002 04:38:23 -0000 Received: from unknown (HELO dipsaus.ds9a.tudelft.nl) (3ffe:8280:10:360:2a0:cff:fe14:9dde) by mayo.ipv6.ds9a.nl with SMTP; 15 Jul 2002 04:38:23 -0000 Received: (qmail 21384 invoked from network); 15 Jul 2002 04:38:23 -0000 Received: from unknown (HELO vger.kernel.org) (::ffff:209.116.70.75) by dipsaus.ds9a.tudelft.nl with SMTP; 15 Jul 2002 04:38:23 -0000 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Mon, 15 Jul 2002 00:33:18 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Mon, 15 Jul 2002 00:33:18 -0400 Received: from leibniz.math.psu.edu ([146.186.130.2]:18619 "EHLO math.psu.edu") by vger.kernel.org with ESMTP id ; Mon, 15 Jul 2002 00:33:17 -0400 Received: from weyl.math.psu.edu (weyl.math.psu.edu [146.186.130.226]) by math.psu.edu (8.9.3/8.9.3) with ESMTP id AAA05241; Mon, 15 Jul 2002 00:36:11 -0400 (EDT) Received: from localhost (viro@localhost) by weyl.math.psu.edu (8.9.3/8.9.3) with ESMTP id AAA20858; Mon, 15 Jul 2002 00:36:10 -0400 (EDT) X-Authentication-Warning: weyl.math.psu.edu: viro owned process doing -bs Date: Mon, 15 Jul 2002 00:36:10 -0400 (EDT) From: Alexander Viro To: Mathieu Chouquet-Stringer Cc: Thunder from the hill , linux-kernel@vger.kernel.org Subject: Re: IDE/ATAPI in 2.5 In-Reply-To: <20020714234457.A21658@shookay.newview.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=KOI8-R Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org X-Spam-Status: No, hits=-4.1 required=6.0 tests=IN_REP_TO,X_AUTH_WARNING version=2.31 X-Spam-Level: Lines: 52 On Sun, 14 Jul 2002, Mathieu Chouquet-Stringer wrote: > On Sun, Jul 14, 2002 at 09:38:16PM -0600, Thunder from the hill wrote: > > Hi, > > Hi, > > > Please time the erase! > > Had the same idea: :-) > mchouque - /tmp/joerg %/usr/bin/time rm -rf rock > 0.18user 6.10system 0:09.27elapsed 67%CPU (0avgtext+0avgdata 0maxresident)k > 0inputs+0outputs (139major+20minor)pagefaults 0swaps > /usr/bin/time rm -rf rock 0.18s user 6.10s system 67% cpu 9.277 total > > Not too bad if you think it took 1 hour something to create the > directory... No wonder - with FFS/ext2/ext3 adding files into directory takes linear scan of the entire thing (presuming that directory was originally empty) on each file. Removing them in the order they were added is much faster - removed entry is simply merged with the previous one in the same block. So you skip the already emptied parts fast - each of these blocks consists of a single (empty) entry. Then you get to the block containing the entry you are removing and either mark it unused (if it's the first one in block) or make the previous one (first in block) longer. You do only one name comparison (empty entries are recognized by zero inode number). So rm -rf is O(blocks * entries). Creating all that is O(entries^2) with much worse constant. FFS never had been intended to handle directories with huge amount of entries. Neiter are most of its derivatives, including ext2 and ext3 (and realistically it's not worth the extra complexity for most of applications). All of that is fs-specific and has nothing to the rest of kernel (or to the kind of kernel, actually - if you look at *BSD implementations of the same thing you'll find the same behaviour). If you change layout (as it had been done for several UFS variants and for htree variant of ext3) you can get faster algorithms. Whether it's practically interesting is a separate question, though - even if kernel side is fast, you still have userland side to deal with and it tends to behave quite badly when confronted with huge directories. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/