[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: RFS: lbzip2

(I'm sorry I can't reply directly to <e13a36b30902121947y639c65cbq3f925f5ac5039552@mail.gmail.com>, my subscription didn't go through before that message appeared on the list, and pine doesn't let me edit In-reply-to: and References: manually, and currently I can only use pine.)

How is this different to or better than pbzip2?

As I've written in the "hot spice" paragraph of my RFS, lbzip2 can
- with multiple threads

pbzip2 too.

- a bz2 file consisting of a single bzip2 stream (eg. created by
standard bzip2 or 7za)

pbzip2 too.

- reading it from a pipe

pbzip2 (in 1.0.4 and later)

I believe I wasn't exact enough. If your compressed input has *any* of the following characterists, pbzip2 won't use multiple worker threads to decompress it, while lbzip2 will:
(1) The compressed input is read from a pipe.
(2) The compressed input consists of a single pbzip2 stream.

Proof for (1), see the pbzip2 ChangeLog:
Changes in 1.0.3 (Oct 31, 2008)
- Added support for decompression using stdin and pipes but
  currently limited to only a single thread

Proof for (2), same file, same Changes section:
- Added support to directly decompress files without using
  threads when files are small or the system only has 1 CPU.
  This mode is also used if the .bz2 file contains only 1
  bzip2 stream.

The changes in releases since then (1.0.4 and 1.0.5) don't invalidate these.

As a further, experimental proof, please look at the my reports that were created for tests that used pbzip2-1.0.5:
- report_alpha_osf1.txt
- report_sparc_solaris.txt
- report_x86_linux.txt

Citing the "Version", "File size [B]" and "Decompr. speed [%]" blocks from "report_alpha_osf1.txt" (I mark the relevant rows with exlamation marks now):

|                  |bzip2                                          1.0.5
|                  |lbzip2                                          0.13
|                  |pbzip2                                         1.0.5
|                  |7za                                    (A) 4.61 beta
|File size [B]
|                  |original                                   666681476
|                  |bzip2                                       82731810
|                  |lbzip2                                      82726254
|                  |pbzip2                                      82738316
|                  |7za                                         82738302
|Decompr. speed [%]
|                  +----------------------------------------------------
|                  |from regf
|                  |            +---------------------------------------
|                  |            |from bzip2
|                  |            |            |lbzip2:bzip2        475.55 !
|                  |            |            |pbzip2:bzip2         95.25 !
|                  |            |            |7za:bzip2           106.64
|                  |            +---------------------------------------
|                  |            |from lbzip2
|                  |            |            |lbzip2:bzip2        408.75 !
|                  |            |            |pbzip2:bzip2        495.45 !
|                  |            |            |7za:bzip2           107.92
|                  |            +---------------------------------------
|                  |            |from pbzip2
|                  |            |            |lbzip2:bzip2        444.89 !
|                  |            |            |pbzip2:bzip2        480.88 !
|                  |            |            |7za:bzip2           105.14
|                  |            +---------------------------------------
|                  |            |from 7za
|                  |            |            |lbzip2:bzip2        430.87 !
|                  |            |            |pbzip2:bzip2         96.10 !
|                  |            |            |7za:bzip2           107.00
|                  +----------------------------------------------------
|                  |from pipe
|                  |            +---------------------------------------
|                  |            |from bzip2
|                  |            |            |lbzip2:bzip2        530.40 !
|                  |            |            |pbzip2:bzip2        100.30 !
|                  |            |            |7za:bzip2
|                  |            +---------------------------------------
|                  |            |from lbzip2
|                  |            |            |lbzip2:bzip2        507.81 !
|                  |            |            |pbzip2:bzip2        100.77 !
|                  |            |            |7za:bzip2
|                  |            +---------------------------------------
|                  |            |from pbzip2
|                  |            |            |lbzip2:bzip2        506.29 !
|                  |            |            |pbzip2:bzip2         99.22 !
|                  |            |            |7za:bzip2
|                  |            +---------------------------------------
|                  |            |from 7za
|                  |            |            |lbzip2:bzip2        537.09 !
|                  |            |            |pbzip2:bzip2        102.30 !
|                  |            |            |7za:bzip2

- using an input-bound splitter (ie. it's not the splitter thread that
looks for bzip2 block headers at any bit positions, because that would
become a bottleneck real fast as the number of cores (worker threads)

Unsure about that as I haven't read the pbzip2 code, perhaps you could
comment on that and if it is not available, please contact the pbzip2
author about adding it:


I invited him a while ago to look at lbzip2 (on 16 Oct 2008). At that time lbzip2 already had an input bound splitter (I mentioned that in my first mail to Jeff.)

I just checked pbzip2-1.0.5, and if I'm not mistaken, it uses memcmp() in a loop over a seekable file to find bzip2 block headers aligned at byte boundaries. If you have many cores, this could become a bottleneck, because the accumulated throughput of the workers is higher than the spliiter is able to produce decompression tasks.

It doesn't matter anyway because pbzip2 does two passes on the regular file to decompress, from pbzip2.cpp:

    This function works in two passes of the input file.
    The first pass will look for BZIP2 headers in the file
    and note their location and size of the sections.
    The second pass will read in those BZIP2 sections and
    pass them off the the selected CPU(s) for decompression.
int producer_decompress(int hInfile, OFF_T fileSize, queue *fifo)

So in the first pass only one core should be exercised.

The multiple-workers decompressor of lbzip2 is very different. Please see the README if you're interested.

Based on your list, it looks like lbzip2 has no advantage over pbzip2?

In some cases, it does have an advantage; see above.

Seems pbzip2 has some more features than lbzip2, like using the load
average to determine the number of threads.

That's right. It also supports more command line options. They are not important for me. I started lbzip2 as lbunzip2, because I considered the compression part a solveed problem (exactly by pbzip2). I added compression and the single-worker decompressor (for single core machines) later for some kind of "completeness".

If anybody forks lbzip2 and adds a lot of fluff to make users happier, and *that* forked version gets into Debian, I'd be just as happy. However, I won't add fluff to lbzip2.

The report URLs give errors when requested. Same with the download link.

Strange. Please try http://lacos.web.elte.hu/pub/lbzip2/ then (which is also the URL I put in debian/watch).

My question was to determine if lbzip2 adds any functionality to
Debian that Debian doesn't already have. Based on what you've said
about lbzip2 it seems that pbzip2 does everything lbzip2 does.

Well, no :)

Personally, I'm not going to sponsor this you can think of some
advantage it has over pbzip2, but that doesn't mean you won't be able
to find a sponsor, there are lots of DDs in Debian with widely varying
opinions about what Debian is and what it is not.

I fully agree (as a mere user) that vanity packages and packages with no new functionality shouldn't get into Debian. However, I wouldn't have had the courage to spam the list if I hadn't been convinced about lbzip2 having some features over pbzip2.

Personally I think pbzip2/lbzip2/bzip2smp/smpbzip2/dbzip2/etc
shouldn't exist and parallelism should simply be added to bzip2.

Exactly. However, due to the nature of parallelism (and perhaps due to the nature of imperative system programming tools we tend to use), parallelism, like security, is not something you can bolt on later. It frequently requires fundamentelly different designs.

If you could talk to the bzip2 upstream and all the people who rewrote it
to add parallelism and convince them to all work on adding parallelism
to bzip2, that would be a really great contribution to the world of
free software. Same for gzip/pigz.

I agree.

When I started out writing lbzip2 (at that time called lbunzip2), the first thing I did was to contact the bzip2 author with questions I considered important for lbunzip2. (This happened on 15 Aug 2008, after I released lbunzip2-0.01). He didn't have the time for me. I said thanks to him on 26 Sep 2008, especially for making bzip2 available as a library, and said I found satisfactory answers to my questions.


Reply to: