Re: HFS problems

[jd-wong@cs.uiuc.edu (wong james d)]

nathan@visi.com (Nathan Mates) writes:

>   My gut feeling on it is that someone had _way_ too much academic
>background and required fancy data structures when they designed
>it. Or, it was designed by committee. In any case, it is NOT a model
>for simple, understandable, and reliable data structures. Even a
>sorted linear list of files would have provided 90% of the performance
>(you have to update the directory on disk _anyways_ when writing;
>moving a list around in memory to insert a filename is dirt cheap, and
>writing a few directory blocks is trivial) at a HUGE savings.

There's nothing particularly complex, incomprehensible, or unreliable
about B*-Trees as used in HFS; they can provide _significant_
performance advantages over simple lists for large amounts of
data (O(n) vs. O(lg n)).  In fact, several modern high-performance
file systems use B-trees or similar data structures; SGI's XFS
comes to mind immediately.

Don't condemn b-trees based on GS/OS's flawed implementation.
Sophisticated data structures will become more and more important as
the amount of data machines need to manage grows.  In this regard,
HFS was ahead of its time.

>   Another thing they did wrong was the 32MB per partition
>problem. Sure, they get around it by having large blocks, but on a 1GB
>drive, the smallest file eats 32K of disk space. Ouch. Macs had
>processors very capable of 32-bit math from the start, and when they
>got around to making HFS, drives >32MB were either available or very
>much on the horizon. Using 32-bit block numbers and 0.5K or 1.0K
>blocks would have been the far better solution for the long run.

A couple of points:

1) You're assuming UNIX-like utilization of the file system (ie, a
multitude of very small files).  It's not clear that this sort of
model holds for personal computers in general, let alone Macs.  With
that in mind, it's not necessarily true that relatively large block
sizes (2-4K, perhaps) are the show-stopper they are in the UNIX world.

2) HFS borrowed heavily from the original Macintosh file system, MFS
(probably simply to maximize the amount of code they could re-use).
This is probably why block numbers are only 16 bits long.  It's 
unfortunate, really, that Apple hasn't yet produced a better file
system...

-- 
Jim Wong (jd-wong@uiuc.edu)