Compression speed issue in lossless WebP for specific images

[Jon Sneyers]

Hi everybody,

I've been running some lossless compression tests (to see how FLIF does w.r.t. the other formats), and I noticed a weird performance issue that might be worth investigating.

In general, WebP encoding is pretty fast, but it seems to be quite image-dependent.

I was testing on these images:
https://sourceforge.net/projects/testimages/files/PATTERNS/8BIT/GRAY/4096x2560_8BIT_GRAY.tar.bz2/download

These are all simple geometric patterns that usually compress very well because they are very repetitive. WebP does a very good job at compressing them. But sometimes it is extremely slow. All the images are the same dimensions (4096x2560). On some images, it took only ~0.15 seconds to encode them (on my laptop), which is very fast. On some other images, however, it took several minutes (!). The slowest ones take more than 1000 times longer than the fastest ones. I did my testing with "-m 6 -q 100" and cwebp 0.5.0 but the behavior seems to be the same with default options and older versions of cwebp.

It seems to be the 'fast' images are the horizontal ones (e.g. *_bars_horizontal_*) while the 'slow' ones have vertical patterns (e.g. *_bars_vertical_*).

Maybe this asymmetry between horizontal and vertical patterns is inherent to the WebP algorithm (the scanlines are horizontal after all), but I still have the feeling that there might be a performance bug here. In any case, in some use cases it can be quite problematic to have such wildly varying encode times (3 orders of magnitude for images that are essentially the same up to 90 degree rotation), so I would be interested in learning more about what causes this behavior and what can perhaps be done to predict or avoid the long encode times.

Best,
-Jon.

[Jyrki Alakuijala]

This is due to the LZ77 match finding by a hash array. On some images matches go to a small number of hash buckets. We could use a more elegant match finder like we do in brotli:11, but it wouldn't be without an increase in complexity in code -- the hash array is still the best choice for faster compression options.

[Pascal Massimino]

Hi Jon,

On Sun, May 15, 2016 at 11:37 PM, Jon Sneyers <jon.s...@gmail.com> wrote:

Hi everybody,

I've been running some lossless compression tests (to see how FLIF does w.r.t. the other formats), and I noticed a weird performance issue that might be worth investigating.

In general, WebP encoding is pretty fast, but it seems to be quite image-dependent.

I was testing on these images:
https://sourceforge.net/projects/testimages/files/PATTERNS/8BIT/GRAY/4096x2560_8BIT_GRAY.tar.bz2/download

Thanks for the report and samples!

These images are indeed made of hard-to-search repetitive patterns. The way to address these

implies a deep rewriting of the way backward-references are searched for (basically, how the

sub-string matching is done). I had this patch pending for a while now:

    https://chromium-review.googlesource.com/#/c/344541/

which addresses the problem somehow. But, as you can see, the algorithm and code are quite involved

and needs a careful testing for corner cases. That's why review progress has been slow on this patch.

But it's definitely useful for the difficult images like the ones you pointed to.

I'll try and finish the review for this patch.

thanks!

skal/

For the record, here's some timings for compressing with '-m 6 -q 100 -lossless -v', with or without

the patch #344541 (x86 laptop). For difficult cases (*bars_vertical_sin_*), the speed-up is ~10x!

img_4096x2560_1x8bit_bars_vertical_sin_0008_0xhalfPI.png   3.530s  <--  36.347s
img_4096x2560_1x8bit_bars_vertical_sin_0008_1xhalfPI.png   3.807s  <--  36.021s

img_4096x2560_1x8bit_bars_vertical_sin_0008_2xhalfPI.png   3.708s  <--  35.981s

img_4096x2560_1x8bit_bars_vertical_sin_0008_3xhalfPI.png   3.654s  <--  36.144s

img_4096x2560_1x8bit_bars_vertical_sin_0016_0xhalfPI.png   7.916s  <--  71.497s

img_4096x2560_1x8bit_bars_vertical_sin_0016_1xhalfPI.png   7.755s  <--  71.224s

img_4096x2560_1x8bit_bars_vertical_sin_0016_2xhalfPI.png   7.759s  <--  70.668s

img_4096x2560_1x8bit_bars_vertical_sin_0016_3xhalfPI.png   7.701s  <--  70.719s

img_4096x2560_1x8bit_bars_vertical_sin_0032_0xhalfPI.png   7.718s  <--  69.938s

img_4096x2560_1x8bit_bars_vertical_sin_0032_1xhalfPI.png   7.650s  <--  69.629s

img_4096x2560_1x8bit_bars_vertical_sin_0032_2xhalfPI.png   7.661s  <--  70.371s

img_4096x2560_1x8bit_bars_vertical_sin_0032_3xhalfPI.png   7.720s  <--  69.538s

img_4096x2560_1x8bit_bars_vertical_sin_0064_0xhalfPI.png   16.517s  <--  143.403s

img_4096x2560_1x8bit_bars_vertical_sin_0064_1xhalfPI.png   15.608s  <--  148.250s

img_4096x2560_1x8bit_bars_vertical_sin_0064_2xhalfPI.png   16.430s  <--  143.090s

img_4096x2560_1x8bit_bars_vertical_sin_0064_3xhalfPI.png   16.659s  <--  142.510s

img_4096x2560_1x8bit_bars_vertical_sin_0128_0xhalfPI.png   16.635s  <--  142.493s

img_4096x2560_1x8bit_bars_vertical_sin_0128_1xhalfPI.png   16.765s  <--  142.643s

img_4096x2560_1x8bit_bars_vertical_sin_0128_2xhalfPI.png   16.630s  <--  140.668s

...

These are all simple geometric patterns that usually compress very well because they are very repetitive. WebP does a very good job at compressing them. But sometimes it is extremely slow. All the images are the same dimensions (4096x2560). On some images, it took only ~0.15 seconds to encode them (on my laptop), which is very fast. On some other images, however, it took several minutes (!). The slowest ones take more than 1000 times longer than the fastest ones. I did my testing with "-m 6 -q 100" and cwebp 0.5.0 but the behavior seems to be the same with default options and older versions of cwebp.

It seems to be the 'fast' images are the horizontal ones (e.g. *_bars_horizontal_*) while the 'slow' ones have vertical patterns (e.g. *_bars_vertical_*).

Maybe this asymmetry between horizontal and vertical patterns is inherent to the WebP algorithm (the scanlines are horizontal after all), but I still have the feeling that there might be a performance bug here. In any case, in some use cases it can be quite problematic to have such wildly varying encode times (3 orders of magnitude for images that are essentially the same up to 90 degree rotation), so I would be interested in learning more about what causes this behavior and what can perhaps be done to predict or avoid the long encode times.

Best,
-Jon.

--
You received this message because you are subscribed to the Google Groups "WebP Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to webp-discuss...@webmproject.org.
To post to this group, send email to webp-d...@webmproject.org.
Visit this group at https://groups.google.com/a/webmproject.org/group/webp-discuss/.
For more options, visit https://groups.google.com/a/webmproject.org/d/optout.

[Pascal Massimino]

Hi,

an update on these.

On Tue, May 17, 2016 at 8:01 AM, Pascal Massimino <pascal.m...@gmail.com> wrote:

Hi Jon,

On Sun, May 15, 2016 at 11:37 PM, Jon Sneyers <jon.s...@gmail.com> wrote:

Hi everybody,

I've been running some lossless compression tests (to see how FLIF does w.r.t. the other formats), and I noticed a weird performance issue that might be worth investigating.

In general, WebP encoding is pretty fast, but it seems to be quite image-dependent.

I was testing on these images:
https://sourceforge.net/projects/testimages/files/PATTERNS/8BIT/GRAY/4096x2560_8BIT_GRAY.tar.bz2/download

Thanks for the report and samples!

These images are indeed made of hard-to-search repetitive patterns. The way to address these

implies a deep rewriting of the way backward-references are searched for (basically, how the

sub-string matching is done). I had this patch pending for a while now:

    https://chromium-review.googlesource.com/#/c/344541/

which addresses the problem somehow. But, as you can see, the algorithm and code are quite involved

and needs a careful testing for corner cases. That's why review progress has been slow on this patch.

But it's definitely useful for the difficult images like the ones you pointed to.

I'll try and finish the review for this patch.

Patches #344541 and #345821 have been submitted, bringing significant speed-up overall (almost 10x in some cases!).

There's still a sequence which remains difficult: img_4096x2560_1x8bit_circles_*. None of the patches are helping

the backward-reference search, which seems inherently difficult for this sort of input.

thanks for the samples!

skal/

[Vincent Rabaud]

Hi,

we've submitted #347010, # 349160, #351290 that help with backward-reference by caching data which drastically helps with images with long (4096 pixels) sequences of repetitive patterns for LZ77, which is the case in quite a few of those images (like the vertical or horizontal bands).
We also submitted #350760, that only provides a few mallocs, instead of thousands, for some of those images.

The results are in the attached graph for the dataset you mention Jon. Images are sorted by their initial encoding time.

As a bonus, size also got improved for big images (cf second plot where images are sorted by their initial WebP size).