Re: HFS problems

[nathan@visi.com (Nathan Mates)]

In article <5126ge$f5b@vixen.cso.uiuc.edu>,
wong james d <jd-wong@cs.uiuc.edu> wrote:
>nathan@visi.com (Nathan Mates) writes:
>Of course, doing binary search doesn't have the nice locality properties
>that B-trees do -- you've pretty much got to keep the whole directory
>in memory..

   Oh, and with a B-tree you shouldn't? Any time you traverse it,
you'd rather just thrash the disk looking for each entry in turn?  Can
we spell glacial? Real Operating systems designed for power have had
this wonderful innovation for quite a long time. Called swap. Very
useful thing, that. Too bad the first Mac implementations were so slow
that most casual users avoided it like the plague it was.

   If your filesystem doesn't keep large chunks of the directory
cached in memory (with all changes being flushed to disk for safety),
you're asking for pretty slow performance. As I said earlier, disk i/o
is the glacial part, so you should optimize around it. Keeping your
directory structure (be it B-Tree, sorted linear, or organized
according to the bits in the file) in memory (ram+swap) is by far the
best performance option. Sure, it might get swapped out for
infrequently accessed parts of the disk, but then it's no worse than
keeping it purely on disk.

   Sure, b-trees and hammering on the disk may be fine when you can
spare no more than 0.5-2K for one directory entry. However, any system
that tries to sell itself as having enough power and performance for
businesses and heavy-duty publishing and doing that is pennywise and
poundfoolish.

>>   Basically, if you assume files are of a random size, the last block
>>of a file will be, on average, 50% empty. Thus, a quick estimate of
>>the space wastage is roughly 0.5* block size * number of files. Thus,
>>a 1GB disk (32K chunks) and 3000 files will likely have 48MB wasted,
>>or roughly 5% of the drive. That formula is related to only the block
>>size and number of files; lots of files in general causes wastage, NOT
>>merely small files.

>But the larger your files are, the less you're affected by this sort
>of fragmentation.  I don't want to make any wild claims, but I'd guess
>that the average file size on Mac systems is considerably larger
>than the typical file on a UNIX system.  Thus, you can get the same
>overall utilization with larger allocation blocks if your usage patterns
>are right.

   If you bother to think about that, my formula already takes that
into account, as well as counting for small files. Something called
the _average_. The maximum number of files you can fit on a disk is
the disk size divided by the average size. (Minus filesystem overhead,
etc).  Sure, a few big files on your average mac may eat a good chunk
of the HD (such as the 25MB file Duke Nukem 3D dropped on my pentium's
HD), but you've still got a ton of 32-byte perferences files.

   A large file, unless it is an exact multiple of the block size
(don't quite think that's too common), will still have a partially
filled last block. On average, that's 50% unused. So, 0.5* block size
* number of files for wasted space still holds for most to all
systems.

   If you think the average Mac has less than 400 files on the HD,
that's nowhere near what I've seen. Several thousand files is a lot
more normal on a 1GB drive. (For reference, my Pentium's Win95 drive
has 6306 files occupying 991 of 1220MB. Average file size is thus
164K, a far cry from lots of tiny files. The drive has 32K chunks, so
by my formula, that's 98MB of wasted space. Even if the average file
size was doubled, that's still 50MB of space wastage.)

   My system may be atypical for a consumer/business box in terms of
filesystem usage (I'd bet the pentium I use at work has double the
number of files), but if you'd like to disagree, I'd like to see some
hard numbers, not just generalities about what Mac people put on their
HDs.

Nathan Mates
--
<*> Nathan Mates http://www.visi.com/~nathan/      <*>
# What are the facts? Again and again and again-- what are the _facts_?
# Shun wishful thinking, avoid opinion, care not what the neighbors
# think-- what are the facts, and to how many decimal places?  -R.A. Heinlein