From: Kyle Rawlins <rawlins@...>
Date: 2002-06-21T07:18:09+09:00
Subject: Re: (quite OT) Are Unix tools just slow?


--0eh6TmSyL6TZE2Uz
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Thu, Jun 20, 2002 at 01:29:10PM +0900, Chris Gehlker wrote:
> This depends entirely on the file system. There are systems where a
> directory is just a node in a tree. There are other systems in which the
> directories are just special files that are actually stored in disk secto=
rs
> like any other file. In these latter systems, walking the file system will
> involve opening, reading and closing each directory which in turn involves
> moving heads and waiting for the disk to revolve.

It seems that there is some misconception of what it means for something to=
 be
stored in a tree (B*-tree really).  In HFS the B*tree is a tree on disk.  W=
hen
traversing the tree (if it is traversed on disk) random access is required,
regardless of whether the nodes are considered files.  That is, the odds of=
 the
children of any given node being contiguous to it or each other is quite sm=
all,
and the odds of any leaf nodes being contiguous on disk (despite being next=
 to
each other in the tree) is also quite slim.  Relations in the tree are stor=
ed
by numeric links to other locations in the segment of disk containing the t=
ree.
Seeking, moving heads, etc is still required for the most part.  The minimum
size of this tree for a filesystem of 100,000 files is 50MB, since the mini=
mum
node size is 512 bytes.

The difference between other filesystems is entirely dependent on granulari=
ty
of caching in each fs, and probably many other things, not just how the
directory structure is stored.  The optimisation goals are by and large the
same, so will just take a different form.  There are cases in other OSs whe=
re
an entire tree will be retained in memory (if it is exported via NFS on lin=
ux,
for example).

If this B*tree is really cached entirely in memory all the time the speed i=
s a
different story, and I know very little about how HFS+ is implemented, so c=
an't
speak to this aspect.

references:
http://developer.apple.com/techpubs/mac/Files/Files-99.html#HEADING99-0
http://developer.apple.com/technotes/tn/tn1150.html

--=20
http://mas.cs.umass.edu/~rawlins
--
rather like a fairy land, isn't it...

--0eh6TmSyL6TZE2Uz
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)

iD8DBQE9ElSencsSsHSBypARArXyAJ9Wz4x4D8+ilhYmsmUsRrk1KVf5dgCfcVEG
bgQhIP16CH9KoDNk8p01mZc=
=iZgW
-----END PGP SIGNATURE-----

--0eh6TmSyL6TZE2Uz--