Up
Defragmenter
Recycled directory
Safe writing
Space efficiency

Space efficiency

First I'll give you a small overview of the filesystems you will find in our comparison so you can get a very general idea of how they store their data on your disk.   Following this explanation you will be presented with the overhead table.  The different kinds of overhead are explained in the final section.

Fast FileSystem (FFS)

The standard filesystem for the Amiga. This filesystem stores information for each file and directory separately in one block (the fileinfoblock), regardless of blocksize.   In the fileinfoblock FFS also stores pointers to all the blocks that make up a file (one pointer for every block).  If there isn't enough room to store all these pointers FFS will allocate extension blocks which are linked to the fileinfoblock.   FFS uses a bitmap to keep track of free space.  The bitmap is, as with most filesystems, redundant.  It can be reconstructed from the file and directory information on the disk.  This is what in fact is happening when the a FFS disk needs to be revalidated.  Optionally FFS can cache files and directories together in special blocks (DirCache) for faster directory access.

AmiFileSafe (AFS)

A 3rd party filesystem for the Amiga.  Multiple files and directories can be stored in a single block resulting in a more efficient usage of space.  AFS uses blockpointer and length pairs stored in a special list structure to keep track of what blocks belong to a file.  Just like FFS, AFS uses a bitmap to keep track of free space.  AFS reserves a fixed amount of diskspace for administration blocks (5% of the total size of the partition).

The FAT16 filesystem (FAT16)

The filesystem used on MS-DOS and Windows based computers, which probably makes it the filesystem which is used by the largest number of computers.  It can store multiple file and directory names in a single block.   To keep track of blocks used by files it uses the File Allocation Table, or FAT.  The FAT has a 16-bit entry for every block the disk consists of.  The 16-bit entry contains the number of the next block in a chain.  This means that with 16-bit entries there is a 65536 (2^16) block limit for FAT16.  Because of this partitions larger than 32 MB require a blocksize larger than 512 bytes.  Since the blocksize cannot be larger than 32768 bytes (32 kB) the maximum size of a partition with this filesystem is 2 GB.  The FAT also serves as a means to keep track of unused space (there is no bitmap).

The FAT32 filesystem (FAT32)

A relatively simple extension to the FAT16 filesystem.  It uses a File Allocation Table with 32-bit entries instead of 16-bit entries.  There are more variants of FAT based filesystems.  Floppies formatted in MS-DOS format for example use a FAT with 12-bit entries in order to reduce space requirements on floppies.  With FAT32 you can have more than 65536 blocks in a single partition, meaning that you can use smaller blocksizes than FAT16 on bigger partitions than FAT16.  However, you still cannot set the blocksize to 512 bytes for a 2 GB partition.  This is most likely an enforced limit and not an internal one, because the File Allocation Table becomes very large in those situations (about 16 MB in this case).  Since the FAT is also used to determine free space it is accessed often.  The smaller the FAT the faster it can be accessed (and the easier it is to keep in memory).

SFS

SFS is very similair to AFS.  Internally all the structures are different, but they work very similair.  The most striking difference is the fact that administration space is allocated in chunks dynamically when needed, not wasting any more space than necessary.  Another difference is the type of structure used to keep track of file allocation information which was designed with automatic file defragmentation in mind.

Comparison

The table gives you an estimate on the amount of overhead in MB for each of the filesystems described above, when they need to store 30000 files varying in size from 4 to 1000 kB (there are more small files than large files).  This includes the overhead for the bitmap or FAT, the overhead for administration blocks and the overhead caused by having to round the size of files up to the nearest multiple of the blocksize.  The size of the partition used is almost 2 GB.

Keep in mind that these are calculated figures, and that they represent an average case (especially AFS and this filesystem have a bad worse case scenario, see below).  Also keep in mind that a lot of things have been simplified, but these figures should still be accurate to within a couple of megabytes.

(*) The minus sign indicates the filesystem doesn't support this blocksize at all or just in this case.
(**) You aren't allowed to use these blocksizes for a 2 GB partition although it probably would be possible.
(***) The overhead in this case is very extreme.  It is unlikely we could fit all 30000 files on the disk as we would run out of space.

Explanation of the figures

If you are interested on how these figures are calculated then read on.  Keep in mind that all of these figures use a 2 GB partition with 30000 files on them.  The overhead of a filesystem is made up out of a number of components:

Rounding a file up to a multiple of the blocksize: Each file stored will waste a small portion of space on your disk simply because a file must be stored in a whole number of blocks.  Since blocks cannot be used partially for multiple files this means that for every file on the disk about half a block is wasted.  The larger the blocksize, the more space is wasted for each file.

Size of the bitmap:  Some of these filesystems use a bitmap to keep track of what blocks are still free.  A bitmap contains 1 bit for every block the disk consists of.  The more blocks the larger the bitmap.  Increasing the blocksize means less blocks to keep track of and thus means a smaller bitmap.

Size of the File Allocation Table:  The FAT filesystems do not use a bitmap.  The FAT is used to keep track of free space and what space belongs to a file.  The FAT is a huge table consisting of 16-bits or 32-bits entries for FAT16 or FAT32 respectively.  There is such an entry for every block the partition consists of.   Increasing the blocksize means less blocks and thus less entries in the FAT.   For FAT16 the table cannot become bigger than 65536 entries, meaning that for a 2 GB partition a blocksize of atleast 32768 bytes is required.

(*) You aren't allowed to use these blocksizes for a 2 GB partition although it probably would be possible.

Filesystem specific overhead for FFS:  For FFS every file stored means that a complete block (the fileinfoblock) is allocated to store its name, comment, protection bits and so on.  The larger the blocksize the larger this overhead is.   Furthermore, FFS uses special blocks and part of the fileinfoblock to keep track of what data blocks belong to a file. You can compare this to a dynamically allocated FAT.   These blocks contain one 32-bit entry for every block the file has in use.   The larger the blocksize the less blocks a file will need, and thus less entries are required to keep track of all the blocks.

Filesystem specific overhead for AFS, FAT16, FAT32 and SFS:  For these filesystems the rest of the overhead is quite small.  All of these filesystems store as much information (name, comment and other information) as possible in each block.   The blocksize therefore becomes irrelevant when storing that information since information of more files would be stored in a block when the blocksize gets larger.

FAT16 and FAT32 do not need special blocks to keep track of what blocks a file has in use because the FAT already contains this information.  AFS and SFS do not keep track of what blocks are used by a file by providing a single entry for each block.   Instead AFS and SFS make use of the fact that usually lots of blocks in sequence belong to a single file.  These filesystems simply store the start and end of such a range, which is very compact for the average case.  Of course, there is a worst case scenario when storing file allocation information in this way (when a very large file is split up in fragments only 1 block in size) but this scenario is extremely unlikely, and can be avoided by having a file defragmenter.

Finally, AFS uses a fixed amount of a partition (5%) to store all of the information above, except the actual file data itself.  This means that it doesn't really matter how much space exactly is used by AFS administration blocks, as a fixed portion of the disk is used for this anyway (I believe there were plans to make this administration area dynamic in size, but as far as I know these were never implemented).

For FAT16 and FAT32 the test-case presented above would mean that about 1 to 2 MB is wasted on administration blocks.  For SFS it would mean about 3 to 4 MB is wasted (with a worst case of more than 30 MB).  For AFS it is the same as for SFS, except that it doesn't matter as the adminstration blocks are stored in the 5% area anyway.

All rights reserved.
For comments, problems or questions regarding this page contact John Hendrikx.
Last updated: 26 april 1998.