Messages in this thread |  | | From | Daniel Phillips <> | Subject | [fsdevel] Tailmerging - first results | Date | Mon, 21 Aug 2000 13:11:58 +0200 |
| |
I'd normally post this to linux-fsdevel, but the list isn't up yet, so...
I now have part of my experimental tailmerging extension for Ext2 working - enough to measure the expected disk space savings. I'm currently doing a full pass through the entire filesystem at mount time, merging as many file tails as I can with a simple, first-fit algorithm.
The current algorithm is:
For each inode with a partly filled tail: Search back through the list of partly filled merge rings Is there a merge ring with enough space to hold this file's tail? If so, merge this file into the ring and reduce the ring's space If not, add this file to the list of partly filled merge rings If the list has reached maximal size, drop the oldest ring
What is surprising is how well this simple-minded algorithm works. I tested it on two source trees: the Linux kernel and Mozilla. Here are the results:
# Install experimental tailmerging version of Ext2 insmod tme2 # Use kernel source for tailmerge test cd /x && tar -xzf /zoo/linux-2.4.0-test6.tar.gz && cd / && umount /x # Remount and perform full-filesystem tailmerge pass mount -t tme2 -o tails=merge /x Aug 21 11:27:09 gimli kernel: Tailmerging enabled! Aug 21 11:27:09 gimli kernel: Average tail usage was 1768 of 4096 bytes (43%) Aug 21 11:27:09 gimli kernel: Average tail usage now 3727 of 4096 bytes (91%) Aug 21 11:27:09 gimli kernel: Freed 3978 of 26861 blocks (14%)
# Install experimental tailmerging version of Ext2 insmod tme2 # Use mozilla source for tailmerge test cd /x && tar -xzf /zoo/mozilla-source.tar.gz && cd / && umount /x # Remount and perform full-filesystem tailmerge pass mount -t tme2 -o tails=merge /x Aug 21 12:19:57 gimli kernel: Tailmerging enabled! Aug 21 12:19:57 gimli kernel: Average tail usage was 1182 of 4096 bytes (28%) Aug 21 12:19:57 gimli kernel: Average tail usage now 3787 of 4096 bytes (92%) Aug 21 12:19:57 gimli kernel: Freed 16490 of 53341 blocks (30%)
The bottom line is 14% space savings for the Linux source tree and 30% for Mozilla. Average utilization of the (merged) tail blocks increases from 28% to 92% for Mozilla.
No doubt a more sophistated algorithm could achieve even better packing but 92% usage is already pretty good. (For anyone who cares, I seem to recall that this kind of optimization problem falls into the np-complete class, IOW, no optimal result computable in polynomial time.)
This is still far from being useable. The current code just computes the merging arrangement; it doesn't actually change the filesystem. Reading and writing to the merged files is not implemented yet, although it has been designed. The incremental version of the tail merging algorithm still has to be designed and implemented.
More details are available in the linux-fsdevel archives: http://web.gnu.walfield.org/mail-archive/linux-fsdevel/2000-July/0142.html
-- Daniel - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org Please read the FAQ at http://www.tux.org/lkml/
|  |