Skip to contentSkip to conversation

Smaller compressed kernel source tarballs?

DISCUSSION Drew Scott Daniels 8 participants 16 messages Oct 2, 2006 – Oct 4, 2006 2 messages not in the archive

lore
Share & tools
lore
#0 lore raw

ppmd, also in Debian had better compression than lzma. PAQ8i has even better compression, but isn't in Debian. See the maximumcompression web site or other archive comparison tests.

The pace of compression algorithm development is high enough that I'd suggest that the bar be placed quite high before switching to a new compression format that's not reverse compatible.

For those interested, I'm working on publishing a proof of concept that can make most tarballs compress better. About 2-3% better in my tests with bzip2/gzip on the Linux kernel source code.

Drew Daniels
Resume: http://www.boxheap.net/ddaniels/resume.html

#1 lore raw
Quoted 7 lines · In article <20061002033511.GB12695@zimmer> you wrote:

The pace of compression algorithm development is high enough that I'd suggest that the bar be placed quite high before switching to a new compression format that's not reverse compatible.

For those interested, I'm working on publishing a proof of concept that can make most tarballs compress better. About 2-3% better in my tests with bzip2/gzip on the Linux kernel source code.

3% is not a high bar.

Gruss
Bernd

#2 lore raw
In reply to Drew Scott Daniels
Quoted 3 lines · Drew Scott Daniels

ppmd, also in Debian had better compression than lzma. PAQ8i has even better compression, but isn't in Debian. See the maximumcompression web site or other archive comparison tests.

Interesting. But I suspect that you have not checked the compression time. PAQ8I for instance is between 100 and 300 times SLOWER than bzip2 to achieve about 30% smaller ! Given that the kernel already takes a very long time to compress with bzip2, it would take several hours to compress it with such tools. While they're very interesting proofs of concept for compression research, they're not suited to any real world usage !

Quoted 3 lines

The pace of compression algorithm development is high enough that I'd suggest that the bar be placed quite high before switching to a new compression format that's not reverse compatible.

At least, ppmd takes the same time as bzip2 to achieve about 12% better compression. But I don't think it justifies a switch.

Quoted 3 lines

For those interested, I'm working on publishing a proof of concept that can make most tarballs compress better. About 2-3% better in my tests with bzip2/gzip on the Linux kernel source code.

A lot of improvement can be made in tar to compress better archive with large number of small files such as the kernel. You just have to see the difference in archive size depending on the base directory name. If you come up with something really interesting which does not alter the output format nor the compression time, it might get a place in the git-tar-tree command. But IMHO, it would me more interesting to further reduce patches size than tarballs size, since patches might be downloaded far more often.

Regards,
Willy

#3 lore raw
Quoted 7 lines · Willy Tarreau

A lot of improvement can be made in tar to compress better archive with large number of small files such as the kernel. You just have to see the difference in archive size depending on the base directory name. If you come up with something really interesting which does not alter the output format nor the compression time, it might get a place in the git-tar-tree command. But IMHO, it would me more interesting to further reduce patches size than tarballs size, since patches might be downloaded far more often.

I just had what's probably a silly thought.

as an alturnative to useing tar, what about useing a git pack?

create a git archive with no history, just the current files, and then pack it with agressive delta options.

since git uses compression on the result anyway it's unlikly to be much worse then a tarball, and since it can use deltas across files it may even be better (potentially enough better to cover the cost of downloading the git binaries)

this would be especially effective once git adds a 'shallow clone' capability to then take the snapshot pack and extend it (either forward or backward as requested by the user), but may be worth doing even without this.

thoughts?

David Lang

#4 lore raw
Quoted 10 lines · David Lang
Quoted 7 lines · Willy Tarreau

A lot of improvement can be made in tar to compress better archive with large number of small files such as the kernel. You just have to see the difference in archive size depending on the base directory name. If you come up with something really interesting which does not alter the output format nor the compression time, it might get a place in the git-tar-tree command. But IMHO, it would me more interesting to further reduce patches size than tarballs size, since patches might be downloaded far more often.

Quoted 3 lines

I just had what's probably a silly thought.

as an alturnative to useing tar, what about useing a git pack?

Nice idea, but I tried on 2.4 : 43 MB for git-pack vs 38 for tar.gz and 31 for tar.bz2. However, it is blazingly fast. 4 seconds vs 30 for tar.gz (hot cache).

When speed is important, it's a clear winner. When size matters, it's not the best solution.

Regards,
Willy

#5 lore raw
In reply to David Lang
Quoted 6 lines · David Lang

I just had what's probably a silly thought.

as an alturnative to useing tar, what about useing a git pack?

create a git archive with no history, just the current files, and then pack it with agressive delta options.

Isn't that what a patch.gz is? Diff generates the deltas and then they are compressed. Can't get much simpler or better than that.

Quoted 7 lines

since git uses compression on the result anyway it's unlikly to be much worse then a tarball, and since it can use deltas across files it may even be better (potentially enough better to cover the cost of downloading the git binaries)

this would be especially effective once git adds a 'shallow clone' capability to then take the snapshot pack and extend it (either forward or backward as requested by the user), but may be worth doing even without this.

thoughts?

David Lang

#6 lore raw
Quoted 9 lines · Phillip Susi
Quoted 6 lines · David Lang

I just had what's probably a silly thought.

as an alturnative to useing tar, what about useing a git pack?

create a git archive with no history, just the current files, and then pack it with agressive delta options.

Isn't that what a patch.gz is? Diff generates the deltas and then they are compressed. Can't get much simpler or better than that.

not quite, a git pack includes everythign you need to get the full source, a patch.gz requires that you have the prior version of the source to start with.

David Lang

#7 lore raw

It sounded like you were talking about a modified pack file that did NOT contain everything you need to get the current source. You said it would have no history and use aggressive delta compression to achieve a smaller size than a full tarball. If the pack contains the full previous version and the delta to the head version, then it will be larger than the tar, not smaller.

Quoted 15 lines · David Lang
Quoted 9 lines · Phillip Susi
Quoted 6 lines · David Lang

I just had what's probably a silly thought.

as an alturnative to useing tar, what about useing a git pack?

create a git archive with no history, just the current files, and then pack it with agressive delta options.

Isn't that what a patch.gz is? Diff generates the deltas and then they are compressed. Can't get much simpler or better than that.

not quite, a git pack includes everythign you need to get the full source, a patch.gz requires that you have the prior version of the source to start with.

David Lang

#8 lore raw

no, I was suggesting a pack file that contained _only_ the head version.

within the pack file it would delta against other files in the pack (how many copies of the GPLv2 text exist across all files for example)

however Willy did a test and found that the resulting pack was significantly larger then a .tgz. I don't know what options he used, so while there's some chance that being more agressive in looking for deltas would result in an improvement, the difference to make up is fairly significant.

David Lang

Quoted 27 lines · Phillip Susi

Date: Mon, 02 Oct 2006 16:20:40 -0400
From: Phillip Susi <[email protected]>
To: David Lang <[email protected]>
Cc: Willy Tarreau <[email protected]>, Drew Scott Daniels <[email protected]>,
[email protected]
Subject: Re: Smaller compressed kernel source tarballs?

It sounded like you were talking about a modified pack file that did NOT contain everything you need to get the current source. You said it would have no history and use aggressive delta compression to achieve a smaller size than a full tarball. If the pack contains the full previous version and the delta to the head version, then it will be larger than the tar, not smaller.

Quoted 15 lines · David Lang
Quoted 9 lines · Phillip Susi
Quoted 6 lines · David Lang

I just had what's probably a silly thought.

as an alturnative to useing tar, what about useing a git pack?

create a git archive with no history, just the current files, and then pack it with agressive delta options.

Isn't that what a patch.gz is? Diff generates the deltas and then they are compressed. Can't get much simpler or better than that.

not quite, a git pack includes everythign you need to get the full source, a patch.gz requires that you have the prior version of the source to start with.

David Lang

#9 lore raw
Quoted 10 lines · David Lang

no, I was suggesting a pack file that contained _only_ the head version.

within the pack file it would delta against other files in the pack (how many copies of the GPLv2 text exist across all files for example)

however Willy did a test and found that the resulting pack was significantly larger then a .tgz. I don't know what options he used, so while there's some chance that being more agressive in looking for deltas would result in an improvement, the difference to make up is fairly significant.

no options at all, so there may be room for improvement. Also, on my notebook, I have hardlinked all my linux directories so that each content only appears once. I don't have the numbers right here, but I remember that it was really useful to merge lots of different versions, but that the net gain within one given tree was really minor, as there are not that many identical files in one tree.

Regards,
Willy

#10 lore raw
Quoted 12 lines · On Mon, 2 Oct 2006 22:35:27 +0200 Willy Tarreau <[email protected]> wrote:
Quoted 10 lines · David Lang

no, I was suggesting a pack file that contained _only_ the head version.

within the pack file it would delta against other files in the pack (how many copies of the GPLv2 text exist across all files for example)

however Willy did a test and found that the resulting pack was significantly larger then a .tgz. I don't know what options he used, so while there's some chance that being more agressive in looking for deltas would result in an improvement, the difference to make up is fairly significant.

Quoted 6 lines

no options at all, so there may be room for improvement. Also, on my notebook, I have hardlinked all my linux directories so that each content only appears once. I don't have the numbers right here, but I remember that it was really useful to merge lots of different versions, but that the net gain within one given tree was really minor, as there are not that many identical files in one tree.

Hey Willy,

I don't really understand the objective here, but you may want to double check your procedure, the entire 2.4 history only takes a single 41M pack in Git for me.

Sean

#11 lore raw
Quoted 22 lines · Sean
Quoted 12 lines · On Mon, 2 Oct 2006 22:35:27 +0200 Willy Tarreau <[email protected]> wrote:
Quoted 10 lines · David Lang

no, I was suggesting a pack file that contained _only_ the head version.

within the pack file it would delta against other files in the pack (how many copies of the GPLv2 text exist across all files for example)

however Willy did a test and found that the resulting pack was significantly larger then a .tgz. I don't know what options he used, so while there's some chance that being more agressive in looking for deltas would result in an improvement, the difference to make up is fairly significant.

Quoted 6 lines

no options at all, so there may be room for improvement. Also, on my notebook, I have hardlinked all my linux directories so that each content only appears once. I don't have the numbers right here, but I remember that it was really useful to merge lots of different versions, but that the net gain within one given tree was really minor, as there are not that many identical files in one tree.

Quoted 5 lines

Hey Willy,

I don't really understand the objective here, but you may want to double check your procedure, the entire 2.4 history only takes a single 41M pack in Git for me.

the idea was to use a git pack instead of a .tgz or .tar.bz2 as a distribution format from kernel.org

for example, the pack would only include the 2.6.18 kernel, no history.

once git supports shallow clones then the distributed blob could be a clone seed that a person could download and then track changes from there forward. but that's a future enhancement.

David Lang

A message that is not in the archive (sent off-list or not yet received): [email protected]

#13 lore raw
Quoted 22 lines · Sean
Quoted 12 lines · On Mon, 2 Oct 2006 22:35:27 +0200 Willy Tarreau <[email protected]> wrote:
Quoted 10 lines · David Lang

no, I was suggesting a pack file that contained _only_ the head version.

within the pack file it would delta against other files in the pack (how many copies of the GPLv2 text exist across all files for example)

however Willy did a test and found that the resulting pack was significantly larger then a .tgz. I don't know what options he used, so while there's some chance that being more agressive in looking for deltas would result in an improvement, the difference to make up is fairly significant.

Quoted 6 lines

no options at all, so there may be room for improvement. Also, on my notebook, I have hardlinked all my linux directories so that each content only appears once. I don't have the numbers right here, but I remember that it was really useful to merge lots of different versions, but that the net gain within one given tree was really minor, as there are not that many identical files in one tree.

Quoted 5 lines

Hey Willy,

I don't really understand the objective here, but you may want to double check your procedure, the entire 2.4 history only takes a single 41M pack in Git for me.

I'm not really surprized, as GIT history begins at 2.4.32 and recent 2.4 patches are very small. So basically, the size is about the same for the latest 2.4 and all 2.4 history.

Willy

#14 lore raw
In reply to Willy Tarreau
Quoted 11 lines
Quoted 4 lines

ppmd, also in Debian had better compression than lzma. PAQ8i has even better compression, but isn't in Debian. See the maximumcompression web site or other archive comparison tests.

Interesting. But I suspect that you have not checked the compression time. PAQ8I for instance is between 100 and 300 times SLOWER than bzip2 to achieve about 30% smaller ! Given that the kernel already takes a very long time to compress with bzip2, it would take several hours to compress it with such tools. While they're very interesting proofs of concept for compression research, they're not suited to any real world usage !

There are lots of obscure compression formats that achieve somewhat better compression at the cost of MUCH more time (neglecting they are not too open), such as MS CAB and ACE.

Jan Engelhardt

#15 lore raw
Quoted 1 line · Jan Engelhardt

There are lots of obscure compression formats that achieve somewhat better compression at the cost of MUCH more time (neglecting they are not too open), such as MS CAB and ACE.

CAB is an archive container format, not a compression algorithm. Last time I worked on some code to handle it, they used the standard LZW algorithm implemented by gzip ( but had the ability to support others in the future ) and could only compress 32kb blocks. The small block size led to poor compression.

#16 lore raw

Compressing pages [was: Re: Smaller compressed kernel source tarballs?]

Quoted 10 lines · Phillip Susi
Quoted 3 lines · Jan Engelhardt

There are lots of obscure compression formats that achieve somewhat better compression at the cost of MUCH more time (neglecting they are not too open), such as MS CAB and ACE.

CAB is an archive container format, not a compression algorithm. Last time I worked on some code to handle it, they used the standard LZW algorithm implemented by gzip ( but had the ability to support others in the future ) and could only compress 32kb blocks. The small block size led to poor compression.

Actually, compression in 4KiB blocks is a _very_ interesting benchmark. Jffs2 works with that size for compression and other compressed filesystems likely do the same, although possibly with something larger like 64KiB.

And the results are completely different in that benchmark. Gzip actually beats bzip2 hands-down on compression ratio, for example.

I used to have a script, but cannot find it anymore. Basically something like:

while (read next 4KiB from input file) {
compress chunk
add compressed_size to total
}
print total

Jörn

Signature · 3 lines
Unless something dramatically changes, by 2015 we'll be largely
wondering what all the fuss surrounding Linux was really about.
-- Rob Enderle