Re: (quite OT) Are Unix tools just slow?

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 sectors
> 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.  When
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 small,
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 stored
by numeric links to other locations in the segment of disk containing the tree.
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 minimum
node size is 512 bytes.

The difference between other filesystems is entirely dependent on granularity
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 where
an entire tree will be retained in memory (if it is exported via NFS on linux,
for example).

If this B*tree is really cached entirely in memory all the time the speed is a
different story, and I know very little about how HFS+ is implemented, so can'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

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