Re: Smaller compressed kernel source tarballs?

Re: Smaller compressed kernel source tarballs?

[Bernd Eckenfels]

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

Re: Smaller compressed kernel source tarballs?

[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.

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

Re: Smaller compressed kernel source tarballs?

[Willy Tarreau]

On Sun, Oct 01, 2006 at 10:35:11PM -0500, Drew Scott Daniels wrote:
> 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 !

> 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.

> 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

Re: Smaller compressed kernel source tarballs?

[David Lang]

On Mon, 2 Oct 2006, Willy Tarreau wrote:

> 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

Re: Smaller compressed kernel source tarballs?

[Willy Tarreau]

On Sun, Oct 01, 2006 at 10:11:49PM -0700, David Lang wrote:
> On Mon, 2 Oct 2006, Willy Tarreau wrote:
> 
> >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?

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

Re: Smaller compressed kernel source tarballs?

[Phillip Susi]

David Lang wrote:
> 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.

> 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

Re: Smaller compressed kernel source tarballs?

[David Lang]

On Mon, 2 Oct 2006, Phillip Susi wrote:

> David Lang wrote:
>> 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

Re: Smaller compressed kernel source tarballs?

[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.

David Lang

On Mon, 2 Oct 2006, Phillip Susi wrote:

> Date: Mon, 02 Oct 2006 16:20:40 -0400
> From: Phillip Susi <psusi@cfl.rr.com>
> To: David Lang <dlang@digitalinsight.com>
> Cc: Willy Tarreau <w@1wt.eu>, Drew Scott Daniels <ddaniels@UMAlumni.mb.ca>,
>     linux-kernel@vger.kernel.org
> 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.
>
> David Lang wrote:
>> On Mon, 2 Oct 2006, Phillip Susi wrote:
>> 
>>> David Lang wrote:
>>>> 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
>
>

Re: Smaller compressed kernel source tarballs?

[Phillip Susi]

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.

David Lang wrote:
> On Mon, 2 Oct 2006, Phillip Susi wrote:
> 
>> David Lang wrote:
>>> 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

Re: Smaller compressed kernel source tarballs?

[Willy Tarreau]

On Mon, Oct 02, 2006 at 01:12:55PM -0700, David Lang wrote:
> 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

Re: Smaller compressed kernel source tarballs?

[David Lang]

On Mon, 2 Oct 2006, Sean wrote:

> On Mon, 2 Oct 2006 22:35:27 +0200
> Willy Tarreau <w@1wt.eu> wrote:
>
>> On Mon, Oct 02, 2006 at 01:12:55PM -0700, David Lang wrote:
>>> 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.
>
> 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

Re: Smaller compressed kernel source tarballs?

[Sean]

On Mon, 2 Oct 2006 22:35:27 +0200
Willy Tarreau <w@1wt.eu> wrote:

> On Mon, Oct 02, 2006 at 01:12:55PM -0700, David Lang wrote:
> > 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.

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

Re: Smaller compressed kernel source tarballs?

[Willy Tarreau]

On Mon, Oct 02, 2006 at 05:49:38PM -0400, Sean wrote:
> On Mon, 2 Oct 2006 22:35:27 +0200
> Willy Tarreau <w@1wt.eu> wrote:
> 
> > On Mon, Oct 02, 2006 at 01:12:55PM -0700, David Lang wrote:
> > > 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.
> 
> 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

Re: Smaller compressed kernel source tarballs?

[Jan Engelhardt]

>> 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
-- 

Re: Smaller compressed kernel source tarballs?

[Phillip Susi]

Jan Engelhardt wrote:
> 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.

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

[Jörn Engel]

On Tue, 3 October 2006 14:24:01 -0400, Phillip Susi wrote:
> Jan Engelhardt wrote:
> >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

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