Optimizing libpng encode time
Adam Richter <[email protected]> Tue, 14 Jul 2020 06:24:56 -0700
| Newsgroups | gmane.comp.graphics.png.devel |
|---|---|
| Message-ID | <CAGn-TggVSRKhguoWGWxEObe17ZRCH=0kVrN==3Ox+xx16k91mw@mail.gmail.com> |
Hi.
I am new to libpng development, just looking to avoid duplication of
effort in a what I expect to be just a brief exploration of ways to
make PNG encoding run a bit faster.
The current release occurred in the past few months, and I see mention
of an "upcoming 1.7.x series" for libpng at
http://www.libpng.org/pub/png/libpng.html , so I infer that some
development is probably occurring.
Assuming that this mailing list is the right place, I would like to
pass along a few observations so far, from my initial look, using gcc
9.3.0-10ubuntu2 on Ubuntu 20.04 on an i7-4770k, trying just a few .png
images, each of a different type (scan of a mostly white piece of
paper with some writing on it, scan of a book page, scan of a magazine
cover, and a screen snapshot).
What worked:
1. Compiling pngwutil.c with "-ftree-vectorize" (which is also
activated by "-O3") to get the compiler to generate single instruction
multiple data (SIMD) loop vectorization gets about a 1% improvement in
the GraphicsMagick command "gm convert ______.pnm ______.png", for my
few test files, and it more import to the next item.
2. I have attached a patch changing the filter selection code in
pngwutil.c to first score all filters in one pass (at least in cases
when certain filters are selected). This change gets mixed results by
itself, but, with "-ftree-vectorize" it makes that "gm convert"
command run ~10-15% faster. Basically, the idea here is to reduce the
number of transfers from memory cache to the CPU. Without this change,
selecting every filter means the code will read the input row nearly
five times and write it nearly five times. With the change, the code
reads the input line twice and writes it once, but computing the
winning output an extra time. So, with the vectorization, the
computation is cheap enough so that the reduction in cache-CPU
transfers outweighs the cost of the additional computation. I suspect
that this trade-off will also be more beneficial for multiprocessing,
where memory bandwidth is likely to be more of an area of contention.
By the way, I hereby release my copyright interest in the attached
patch to the public domain, so please feel free to incorporate code
from it if you wish.
3. For the Paeth encoding, changing the differences from ints to
shorts made the code slightly faster, especially with the
vectorization enabled.
What failed:
4. I briefly tried "#pragma omp parallel for simd (reduce +:"... with
"-fopenmp" for my filter comparison function, and it resulted in
slightly worse performance. Doing so without with "simd" keyword
(using multiple CPU threads) resulted in worse performance, presumably
because there is too little work in a single scanline to justify the
threading overhead. I have not yet tried doing the same on the filter
encoding functions.
5. Putting "__attribute__ ((target_clones("sse2", "avx", "avx2",
"default") ))" did not improve my too small benchmark.
I hope these data points are helpful. Any further pointers to how to
contribute to libpng development would be welcome. Thanks in advance
for any input.
Adam
_______________________________________________
png-mng-implement mailing list
png-mng-implement-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@public.gmane.org
https://lists.sourceforge.net/lists/listinfo/png-mng-implement
pngwutil.c.diff
(text/x-patch, 5.3 KB)
diff --git a/pngwutil.c b/pngwutil.c
index 16345e4..982e08b 100644
--- a/pngwutil.c
+++ b/pngwutil.c
@@ -13,6 +13,8 @@
#include "pngpriv.h"
+// #define fprintf(x...) do { } while(0)
+
#ifdef PNG_WRITE_SUPPORTED
#ifdef PNG_WRITE_INT_FUNCTIONS_SUPPORTED
@@ -2467,7 +2469,7 @@ png_setup_paeth_row(png_structrp png_ptr, png_uint_32 bpp,
for (lp = png_ptr->row_buf + 1, cp = png_ptr->prev_row + 1; i < row_bytes;
i++)
{
- int a, b, c, pa, pb, pc, p;
+ short a, b, c, pa, pb, pc, p;
b = *pp++;
c = *cp++;
@@ -2520,7 +2522,7 @@ png_setup_paeth_row_only(png_structrp png_ptr, png_uint_32 bpp,
for (lp = png_ptr->row_buf + 1, cp = png_ptr->prev_row + 1; i < row_bytes;
i++)
{
- int a, b, c, pa, pb, pc, p;
+ short a, b, c, pa, pb, pc, p;
b = *pp++;
c = *cp++;
@@ -2544,6 +2546,160 @@ png_setup_paeth_row_only(png_structrp png_ptr, png_uint_32 bpp,
*dp++ = (png_byte)(((int)*rp++ - p) & 0xff);
}
}
+
+static inline png_byte
+png_byte_abs(png_byte v)
+{
+#ifdef PNG_USE_ABS
+ return 128 - abs((int)v - 128);
+#elif 1
+ return (v < 128) ? v : 256 - v;
+#else /* did not help: */
+ /* Adapted from Hackers Delight by Henry S. Warren, chapter 2: */
+ char v = v_unsigned;
+ typeof(v) neg_mask = v >> ((sizeof(v) * CHAR_BIT) - 1);
+ typeof(v) result = (v ^ neg_mask) - neg_mask;
+ return result;
+#endif
+}
+
+static inline short
+png_short_abs(short v)
+{
+#ifdef PNG_USE_ABS
+ return abs(v);
+#elif 1
+ return (v >= 0) ? v : -v;
+#else /* did not help: */
+ /* Adapted from Hackers Delight by Henry S. Warren, chapter 2: */
+ typeof(v) neg_mask = v >> ((sizeof(v) * CHAR_BIT) - 1);
+ typeof(v) result = (v ^ neg_mask) - neg_mask;
+ return result;
+#endif
+}
+static inline int
+png_int_abs(int v)
+{
+#ifdef PNG_USE_ABS
+ return abs(v);
+#elif 1
+ return (v >= 0) ? v : -v;
+#else /* did not help: */
+ /* Adapted from Hackers Delight by Henry S. Warren, chapter 2: */
+ typeof(v) neg_mask = v >> ((sizeof(v) * CHAR_BIT) - 1);
+ typeof(v) result = (v ^ neg_mask) - neg_mask;
+ return result;
+#endif
+}
+
+static unsigned int
+png_reduce_filters(png_structrp png_ptr, png_uint_32 bpp,
+ size_t row_bytes, unsigned int filters)
+{
+ png_bytep rp, dp, pp, cp, lp;
+ size_t i;
+
+ png_byte left = 0;
+ png_byte upper_left = 0;
+ png_byte up;
+ png_byte up_plus_left;
+ png_byte avg;
+
+ size_t sum_none = 0;
+ size_t sum_up = 0;
+ size_t sum_avg = 0;
+
+ for (i = 0, rp = png_ptr->row_buf + 1,
+ pp = png_ptr->prev_row + 1; i < bpp; i++, rp++, pp++)
+ {
+ png_byte input = *rp;
+ png_byte up = *pp;
+ sum_none += png_byte_abs(input);
+ sum_up += png_byte_abs(input - up);
+ sum_avg += png_byte_abs(input - up/2);
+ }
+
+ size_t sum_sub = sum_none;
+ size_t sum_paeth = sum_up;
+
+ for (lp = png_ptr->row_buf + 1, cp = png_ptr->prev_row + 1; i < row_bytes;
+ i++, pp++, cp++, lp++, rp++)
+ {
+ png_byte input = *rp;
+ sum_none += png_byte_abs(input);
+
+ png_byte left = *lp;
+ sum_sub += png_byte_abs(input - left);
+
+ png_byte up = *pp;
+ sum_up += png_byte_abs(input - up);
+
+ unsigned short up_plus_left = up + left;
+ png_byte avg = up_plus_left >> 1;
+ sum_avg += png_byte_abs(input - avg);
+
+ short a, b, c, pa, pb, pc, p;
+ unsigned int v_paeth;
+
+ b = up;
+ c = *cp;
+ a = left;
+
+ p = b - c;
+ pc = a - c;
+
+ pa = png_short_abs(p);
+ pb = png_short_abs(pc);
+ pc = png_short_abs(p + pc);
+
+ p = (pa <= pb && pa <=pc) ? a : (pb <= pc) ? b : c;
+ v_paeth = (input - p) & 0xFF;
+
+ sum_paeth += png_byte_abs(v_paeth);
+ }
+
+ unsigned int best_filter = 0;
+ unsigned int sum_least = 0;
+
+ if (filters & PNG_FILTER_NONE) {
+ best_filter = PNG_FILTER_NONE;
+ sum_least = sum_none;
+ }
+
+ if ((filters & PNG_FILTER_SUB) &&
+ (best_filter == 0 || sum_least > sum_sub)) {
+
+ best_filter = PNG_FILTER_SUB;
+ sum_least = sum_sub;
+ }
+
+ if ((filters & PNG_FILTER_UP) &&
+ (best_filter == 0 || sum_least > sum_up)) {
+
+ best_filter = PNG_FILTER_UP;
+ sum_least = sum_up;
+ }
+
+ if ((filters & PNG_FILTER_AVG) &&
+ (best_filter == 0 || sum_least > sum_avg)) {
+
+ best_filter = PNG_FILTER_AVG;
+ sum_least = sum_avg;
+ }
+
+ if ((filters & PNG_FILTER_PAETH) &&
+ (best_filter == 0 || sum_least > sum_paeth)) {
+
+ best_filter = PNG_FILTER_PAETH;
+ // sum_least = sum_paeth;
+ }
+
+ if (best_filter)
+ return best_filter | (filters & ~(PNG_FILTER_NONE|PNG_FILTER_SUB|PNG_FILTER_UP|PNG_FILTER_AVG|PNG_FILTER_PAETH));
+ else
+ return filters;
+}
+
#endif /* WRITE_FILTER */
void /* PRIVATE */
@@ -2605,7 +2761,10 @@ png_write_find_filter(png_structrp png_ptr, png_row_infop row_info)
*/
filter_to_do &= 0U-filter_to_do;
}
- else if ((filter_to_do & PNG_FILTER_NONE) != 0 &&
+ else if (filter_to_do & (PNG_FILTER_UP | PNG_FILTER_AVG | PNG_FILTER_PAETH)) {
+ filter_to_do = png_reduce_filters(png_ptr, bpp, row_bytes, filter_to_do);
+ }
+ if ((filter_to_do & PNG_FILTER_NONE) != 0 &&
filter_to_do != PNG_FILTER_NONE)
{
/* Overflow not possible and multiple filters in the list, including the