Messages in this thread | | | Date | Fri, 17 Oct 2003 16:51:26 +0400 | From | Edward Shushkin <> | Subject | Re: Transparent compression in the FS |
| |
> Richard B. Johnson wrote: > > >Then the degenerative case is no compression at all. There is no > >advantage to writing a block that is 1/N full of compressed data. > >You end up having to write the whole block anyway. > > > >This problem was well developed in the days where RLE (at the hardware > >level) was used to extend the size of hard disks from their physical > >size of about 38 megabytes to about 70 megabytes. The minimim size > >of a read or write is a sector. > > > >So, lets's use the minimum compression alogithm, no sliding > >dictionaries complicating things, just RLE and see. > > > >The alogithm is a sentinal byte, a byte representing the number > >of bytes to expand -1, then the byte to expand. The sentinal byte > >in RLE was 0xbb. If you needed to read/write a 0xbb, you need > >to expand that to three bytes, 0xbb, 0x00, 0xbb. > > | | |___ byte to expand > > | |________ nr bytes (0 + 1) > > |______________ sentinal byte > > > >All other sequences will reduce the size. So, we have a 512- > >byte sector full of nulls, what gets written is: > > 0xbb, 0xff, 0x00, 0xbb, 0xff, 0x00 > > | | | | | |___ byte value > > | | | | |_________ 256 bytes > > | | | |_______________ sentinal > > | | |_____________________ byte value > > | |___________________________ 256 bytes > > |_________________________________ sentinal. > > > >In this example, we have compressed a 512 byte sector to > >only 6 bytes. Wonderful! Now we have to write 512 bytes > >so that effort was wasted.
Reiser4 packs compressed block so it will be represented by a set of tails (fragments). This approach allows to keep compression ratio as maximal as possible.
Edward. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |