GNOME Bugzilla – Bug 80925
improve scaling down by large factors
Last modified: 2017-02-03 20:10:24 UTC
From gdk-pixbuf/pixops/README: * Scaling down images by large scale factors is _slow_ since huge filter matrixes are computed. (e.g., to scale down by a factor of 100, we compute 101x101 filter matrixes. At some point, it would be more efficent to switch over to subsampling when scaling down - one should never need a filter matrix bigger than 16x16.
This is an important fix ... there is one implementation of this that Alex Larsson added to eel, which might be usuable.
When I looked at this some time ago, I didn't get any real speed improvements from the eel code. Maybe because the scaling cost is dominated by iterating over all pixels in the huge source image. "nearest" scaling blows the eel code away performance- wise because it only iterates over the pixels of the small destination image.
Scaling down by small factors doesn't matter much, but the filter matrices you get when scale down by large factors can easily be multi-megabyte. Computing them takes significant amounts of time.
My current thought on downscaling is to replace the current implementation with a two-pass algorithm ... still not hugely efficient, but makes the overhead O(scale_factor) not O(scale_factor^2).
You mean first horizontal, then vertical ? Or use tile to scale down far enough to make the matrix sizes resonable in next step, then use the selected scale mode to do the rest ?
I mean horizontal, then vertical. Because the filters are separable, this produces the same result, and is much more efficient for large factors.
You should consider using Integral Images ("summed area tables") for scaling down by significant amounts, e.g.: http://citeseer.nj.nec.com/594293.html You pass over the image once to compute the integral image, which is simply: iimg[x,y] = orig_img[x,y] - iimg[x-1,y] - iimg[x,y-1] + iimg[x-1,y-1] . iimg[x,y] is then the cumulative sum of all pixel values over the rectangle between [0,0] and [x,y]. You can then find the sum of all pixel values over an arbitrary rectangle in O(1) time, using: integral(x1,y1,x2,y2) = iimg[x2,y2] - iimg[x1,y2] - iimg[x2,y1] + iimg[x1,y1] . You then divide the integral by the area, (x2 - x1) * (y2 - y1), to get the average value over the area in O(1) time. (The calculations obviously have to be modified if they overlap the edge of the image.) Thus you have a "rectangular pulse" convolution kernel of arbitrary size, that works in O(1) time. Great for blurring! You just center a rectangular kernel over each pixel that you're sampling which is a bit bigger than your sampling interval, and you only have to sample at screen resolution, not at image resolution. You can approximate a Gaussian blur by overlapping three kernels: one medium-sized square kernel, one wide narrow kernel, and one tall narrow kernel. But that's probably overkill for dramatically-scaled-down images. Obviously iimg[] needs to have integer entries to handle the cumulative sum across large images (or you could tile the integral images across the image, and use shorts, but that's more complicated). You would probably have to do it on a per-plane basis (R,G,B,A). It's still O(1) though, and probably faster than what you have now. Another alternative is to pointwise-samle the image down by a factor of say 1/5 of the total scale factor, then use integral images on that at a 5:1 ratio to get the final "blur" effect. I don't think this has been done before for image scaling -- I'm planning on writing a paper on it. But I would be interested to see it go into GTK. If anyone tries it out, let me know how it goes. P.S. the formulae above are off the top of my head, but I think they're right.
*** Bug 336327 has been marked as a duplicate of this bug. ***
*** Bug 343345 has been marked as a duplicate of this bug. ***
*** Bug 348222 has been marked as a duplicate of this bug. ***
*** Bug 349768 has been marked as a duplicate of this bug. ***
*** Bug 354465 has been marked as a duplicate of this bug. ***
*** Bug 520840 has been marked as a duplicate of this bug. ***
Additional info from bug #520840: + happen with BILINEAR, works fine on NEAREST (obviously) + ends up crashing while trying to allocate multi-Gigabyte buffer + test case for the crash attached to bug #520840
Some thoughts: In bug 522803 I supplied a patch to the pixbuf loaders to use two-stage scaling when the scaling ratio exceeds 64. This was implemented using two call to gdk_pixbuf_scale_simple, using sqrt-N each time. I used a test folder that had four 15000x400 tif images and four 15000x400 png images (solid colors). Without the patch, it took Nautilus 4 minutes and 30 seconds to thumbnail the folder. With the patch, it took 8 seconds. I'm not clever enough to touch the actual pixop codebase. But these numbers suggest there is enormous room for improvement! This bug has been open for 6 years - nudge, nudge. - Mike
*** Bug 348260 has been marked as a duplicate of this bug. ***
*** Bug 385571 has been marked as a duplicate of this bug. ***
Bumping version info, to make clear that this is still an issue.
*** Bug 385514 has been marked as a duplicate of this bug. ***
Should someone look into gimp's algorithms used to scale down (and up) images? http://svn.gnome.org/viewvc/gimp/trunk/app/paint-funcs/scale-region.c?view=markup
Giacomo: Thanks for the link. We must solve this really soon now. It's causing all kinds of issues when people use large photo-sized thumbnails for files that are shrinked to a few dozen pixels. Besides, this could probably speed up display of images in many applications. CCing gimp-maint: Do you see any chance of moving or copying the linear, cubic and lanzcos interpolation routines into gdk-pixbuf, and helping us to to improve when doing "extreme" downscales? scale-region.c:shrink_line() seems to be able to deal with it very well.
Actually, we consider the code that is used in GIMP to be rather bad for downscaling (see bug #464466). It is fast, but it doesn't provide the quality that users expect from an image manipulation program. Perhaps the algorithm is well-suited for your gdk-pixbuf though. It is quite likely that in the next days we are going to replace some code in the downscaling code path in trunk. So if you are interested in the fast, but somewhat wrong, version, then you better look at the gimp-2-4 branch.
> if you are interested in the fast, but somewhat wrong, version, then you better look at the gimp-2-4 branch. Since GTK+ is used both for professional image processing applications and for other applications that need a snappy algorithm, it may be wise to provide a shared implementation for both use cases inside gdk-pixbuf.
Sven, since now gimp uses new code for more then year, what do you think now? Is it good idea to use gimp implementation of downscaling? And another program affected by this bug: http://developer.pidgin.im/ticket/11021
*** Bug 774755 has been marked as a duplicate of this bug. ***
It's time something was done about this. 14 years is too long to keep a pathological bug on hold. Soon it will be over 18 and legally responsible for its actions! All valiant attempts to fix it have failed and attempts to find alternative code have been poo-pooed as not producing as good quality results. However, if it hasn't been fixed "properly" in 14 years, despite several valiant efforts, it never is going to be. Time for a workaround. (In reply to Matthias Clasen from comment #5) > You mean first horizontal, then vertical ? I've tried this, both in my app and in the library. It does avoid the bug but the resulting image is not the same. Mostly it is, sometimes values are off by one, presumably due to the intermediate image pixels being stored in 8-bit ints. There ar eno higher-precision colour formats available. At small sizes, the pixel value differences are greater. Here's the workaround: The pathological case only bites badly (900MB of VM, minutes of CPU) when the destination width or height are == 1, with the worst case being when they are both 1. Scaling to width or height of 1 is easy: just average all the pixels in each column or row, then scale the other dimension with the usual code. Where to do this? The internal function call graph is that gdk_pixbuf_scale_simple() calls gdk_pixbuf_scale() which calls _pixops_scale() which calls _pixops_scale_real(). Unfortunately, from gdk_pixbuf_scale() onwards, the destination width and height have disappeared and been replaced by double-precision scale factors, leaving the destination height and width to be recalculated (i.e. guessed). I wouldn't b sure to get that right, what with all those offsets and stuff floating around too. As a quick, safe solution I propose putting some special cases in gdk_scale_simple(), the interface that everyone uses and where the destination width and height are evident, that detect the pathological case (BILINEAR and width or height == 1) and handle them by reducing the image to a line in one dimension then using the high-quality scaler in the other dimension. It's not "the right thing". It's just a practical solution that can be implemented fairly safely (not rocket science, doesn't disturb the hairy code) to a shameful situation that refuses to go away. I don't mind implementing this if this solution seems valid. Then, when a passing graphics guru happens to have a few weeks spare, we can finally have the right thing in glorious technicolor. But we might die first... Thoughts? M
Hypothesis: Avoiding scaling to 1xH and Wx1 will avoid the bug. Experiment: Modify application code: when scaling to 1x and to x1 is detected, prescale the image in one dimension 1024x768 -> 1x768 then -> 1xH. Observation: This improves matters - the hangs are less frequent and last a few seconds instead of tens. The pathological behaviour still happens in scalings to, for example 8x2. Also (according to valgrind --callgrind ./image1-gtk2 ; kcachegrind) the CPU time is not in the scaler itself but it spends 99.84% CPU in pixops_process() (in reality in make_filter_table(), which is inlined into pixops_process()). make_filter_table builds a 16x16 array of filter tables to cover all cases of subsampling to 4-bit-precision offset, making for a total of 1793792 weights instead of the usual few thousand. This can be improved by reducing the subpixel precision to 2 bits, which accounts for 1/4-pixel resolution instead of 1/16th, and reduces the filter table siz by a factor of 16. gdk-pixbuf/pixops/pixops.c < #define SUBSAMPLE_BITS 4 > #define SUBSAMPLE_BITS 2 This also needs: /* The MMX code, at least for scaling, seems to know that SUBSAMPLE_BITS==4 as * it garbles the output when SUBSAMPLE_BITS==2 and both axes are enlarged. */ #if SUBSAMPLE_BITS != 4 # undef USE_MMX #endif
(In reply to Martin Guy from comment #26) > It's time something was done about this. 14 years is too long to keep a > pathological bug on hold. Soon it will be over 18 and legally responsible > for its actions! > > All valiant attempts to fix it have failed and attempts to find alternative > code have been poo-pooed as not producing as good quality results. > However, if it hasn't been fixed "properly" in 14 years, despite several > valiant efforts, it never is going to be. Most of the applications avoid this, or use libgnome-desktop's helper: https://git.gnome.org/browse/gnome-desktop/tree/libgnome-desktop/gnome-thumbnail-pixbuf-utils.c#n51 > Time for a workaround. I'd be fine having work-arounds, I'd be fine having the gnome-desktop function wholesale, but I'd like to have a test case or test cases. It would be great if you could figure out at which point the matrix just gets too big. To do that I would: - create a test case that creates a big image, always the same size - the test case then downscales the image by a specified ratio (/1, /2, etc.) - run the test suite (the test case with decreasing ratio) under valgrind's massif tool: http://valgrind.org/docs/manual/ms-manual.html - tidy up the massif output to find when the pathological memory usage starts - bolt in gnome-desktop's function and make it active when the ratio is under a certain number - re-run test - success!
Thanks. I've run CPU timing tests, rather than memory-usage tests, since the CPU usage rises before the memory usage goes potty. The gnome-desktop-scaler is a cruder scaler: it just averages rectangles of pixels whereas gdk does this to 16th-of-a-pixel subpixel accuracy. It turns out that the 1x optimizations still provoke the slowdown when scaling to small sizes, whereas the "two_step" optimization suggested in bug 522803 is more effective. To find the cases for which we should apply the optimization, we time the scaler at various reduction ratios (time is for 100 applications of the scaler): When scaling only the width: 1134x768->1134x20, size ratio 38.40, area ratio 38.00, 1252 msec 1134x768->1134x19, size ratio 40.42, area ratio 40.00, 1252 msec 1134x768->1134x18, size ratio 42.67, area ratio 42.00, 1240 msec 1134x768->1134x17, size ratio 45.18, area ratio 45.00, 1264 msec 1134x768->1134x16, size ratio 48.00, area ratio 48.00, 1252 msec 1134x768->1134x15, size ratio 51.20, area ratio 51.00, 1240 msec 1134x768->1134x14, size ratio 54.86, area ratio 54.00, 1244 msec 1134x768->1134x13, size ratio 59.08, area ratio 59.00, 1244 msec 1134x768->1134x12, size ratio 64.00, area ratio 64.00, 1244 msec 1134x768->1134x11, size ratio 69.82, area ratio 69.00, 1260 msec 1134x768->1134x10, size ratio 76.80, area ratio 76.00, 1268 msec 1134x768->1134x9, size ratio 85.33, area ratio 85.00, 1268 msec 1134x768->1134x8, size ratio 96.00, area ratio 96.00, 1252 msec 1134x768->1134x7, size ratio 109.71, area ratio 109.00, 1252 msec 1134x768->1134x6, size ratio 128.00, area ratio 128.00, 1276 msec 1134x768->1134x5, size ratio 153.60, area ratio 153.00, 1292 msec 1134x768->1134x4, size ratio 192.00, area ratio 192.00, 1332 msec 1134x768->1134x3, size ratio 256.00, area ratio 256.00, 1436 msec *** 1134x768->1134x2, size ratio 384.00, area ratio 384.00, 2076 msec 1134x768->1134x1, size ratio 768.00, area ratio 768.00, 2600 msec When scaling only the height: 1134x768->20x768, size ratio 56.70, area ratio 56.00, 800 msec 1134x768->19x768, size ratio 59.68, area ratio 59.00, 796 msec 1134x768->18x768, size ratio 63.00, area ratio 63.00, 796 msec 1134x768->17x768, size ratio 66.71, area ratio 66.00, 820 msec 1134x768->16x768, size ratio 70.88, area ratio 70.00, 820 msec 1134x768->15x768, size ratio 75.60, area ratio 75.00, 824 msec 1134x768->14x768, size ratio 81.00, area ratio 81.00, 836 msec 1134x768->13x768, size ratio 87.23, area ratio 87.00, 832 msec 1134x768->12x768, size ratio 94.50, area ratio 94.00, 840 msec 1134x768->11x768, size ratio 103.09, area ratio 103.00, 848 msec 1134x768->10x768, size ratio 113.4, area ratio 113.00, 820 msec 1134x768->9x768, size ratio 126.00, area ratio 126.00, 856 msec 1134x768->8x768, size ratio 141.75, area ratio 141.00, 876 msec 1134x768->7x768, size ratio 162.00, area ratio 162.00, 924 msec 1134x768->6x768, size ratio 189.00, area ratio 189.00, 924 msec 1134x768->5x768, size ratio 226.80, area ratio 226.00, 952 msec 1134x768->4x768, size ratio 283.50, area ratio 283.00, 1012 msec *** 1134x768->3x768, size ratio 378.00, area ratio 378.00, 1188 msec 1134x768->2x768, size ratio 567.00, area ratio 567.00, 1432 msec 1134x768->1x768, size ratio 1134.00, area ratio 1134.00, 2396 msec When scaling both dimensions by the same factor: 1134x768->40x40, size ratio 19.20, area ratio 544.00, 668 msec 1134x768->39x39, size ratio 19.69, area ratio 572.00, 668 msec 1134x768->38x38, size ratio 20.21, area ratio 603.00, 708 msec 1134x768->37x37, size ratio 20.76, area ratio 636.00, 672 msec 1134x768->36x36, size ratio 21.33, area ratio 672.00, 728 msec 1134x768->35x35, size ratio 21.94, area ratio 710.00, 692 msec 1134x768->34x34, size ratio 22.59, area ratio 753.00, 732 msec 1134x768->33x33, size ratio 23.27, area ratio 799.00, 744 msec 1134x768->32x32, size ratio 24.00, area ratio 850.00, 744 msec 1134x768->31x31, size ratio 24.77, area ratio 906.00, 768 msec 1134x768->30x30, size ratio 25.60, area ratio 967.00, 880 msec 1134x768->29x29, size ratio 26.48, area ratio 1035.00, 820 msec 1134x768->28x28, size ratio 27.43, area ratio 1110.00, 848 msec 1134x768->27x27, size ratio 28.44, area ratio 1194.00, 920 msec 1134x768->26x26, size ratio 29.54, area ratio 1288.00, 1000 msec 1134x768->25x25, size ratio 30.72, area ratio 1393.00, 948 msec 1134x768->24x24, size ratio 32.00, area ratio 1512.00, 972 msec 1134x768->23x23, size ratio 33.39, area ratio 1646.00, 1352 msec *** 1134x768->22x22, size ratio 34.91, area ratio 1799.00, 1080 msec 1134x768->21x21, size ratio 36.57, area ratio 1974.00, 1140 msec 1134x768->20x20, size ratio 38.40, area ratio 2177.00, 1232 msec 1134x768->19x19, size ratio 40.42, area ratio 2412.00, 1332 msec 1134x768->18x18, size ratio 42.67, area ratio 2688.00, 1392 msec 1134x768->17x17, size ratio 45.18, area ratio 3013.00, 4036 msec 1134x768->16x16, size ratio 48.00, area ratio 3402.00, 1672 msec 1134x768->15x15, size ratio 51.20, area ratio 3870.00, 3300 msec 1134x768->14x14, size ratio 54.86, area ratio 4443.00, 9944 msec 1134x768->13x13, size ratio 59.08, area ratio 5153.00, 15804 msec 1134x768->12x12, size ratio 64.00, area ratio 6048.00, 14620 msec So the point where the execution time is notably increased from the "usual" seems to be when either dimension is scaled by more than a factor of 256 or the area is scaled by more than 1600 (where "more than usual" is more than 150% but not yet 200%).
Created attachment 340931 [details] test program to measure time taken by pixbuf_scale()
Using the gnome-desktop scaler to handle the pathological cases is fine for simple_scale but the generic scaler also handles offsets into the source and destination pixmaps. I wouldn't fancy adding offsets to an existing hairy scaler. Meanwhile I've hacked up the two-step reduction at the bottleneck through which all scaling goes, and it makes scaling time pretty much constant with a 20 or 30% increase in CPU time just before the point where the two-step scale kicks in. "test" now goes: (Cases in which the two-step scaling happens are *-ed) Scaling width: 1134x768->20x768, size ratio 56.70, area ratio 56.00, 800 msec 1134x768->19x768, size ratio 59.68, area ratio 59.00, 812 msec 1134x768->18x768, size ratio 63.00, area ratio 63.00, 812 msec 1134x768->17x768, size ratio 66.71, area ratio 66.00, 868 msec 1134x768->16x768, size ratio 70.88, area ratio 70.00, 780 msec 1134x768->15x768, size ratio 75.60, area ratio 75.00, 820 msec 1134x768->14x768, size ratio 81.00, area ratio 81.00, 824 msec 1134x768->13x768, size ratio 87.23, area ratio 87.00, 844 msec 1134x768->12x768, size ratio 94.50, area ratio 94.00, 832 msec 1134x768->11x768, size ratio 103.09, area ratio 103.00, 848 msec 1134x768->10x768, size ratio 113.40, area ratio 113.00, 864 msec 1134x768->9x768, size ratio 126.00, area ratio 126.00, 860 msec 1134x768->8x768, size ratio 141.75, area ratio 141.00, 872 msec 1134x768->7x768, size ratio 162.00, area ratio 162.00, 900 msec 1134x768->6x768, size ratio 189.00, area ratio 189.00, 904 msec 1134x768->5x768, size ratio 226.80, area ratio 226.00, 972 msec 1134x768->4x768, size ratio 283.50, area ratio 283.00, 968 msec * 1134x768->3x768, size ratio 378.00, area ratio 378.00, 952 msec * 1134x768->2x768, size ratio 567.00, area ratio 567.00, 948 msec * 1134x768->1x768, size ratio 1134.00, area ratio 1134.00, 936 msec * Scaling height: 1134x768->1134x20, size ratio 38.40, area ratio 38.00, 1252 msec 1134x768->1134x19, size ratio 40.42, area ratio 40.00, 1300 msec 1134x768->1134x18, size ratio 42.67, area ratio 42.00, 1356 msec 1134x768->1134x17, size ratio 45.18, area ratio 45.00, 1308 msec 1134x768->1134x16, size ratio 48.00, area ratio 48.00, 1240 msec 1134x768->1134x15, size ratio 51.20, area ratio 51.00, 1252 msec 1134x768->1134x14, size ratio 54.86, area ratio 54.00, 1252 msec 1134x768->1134x13, size ratio 59.08, area ratio 59.00, 1248 msec 1134x768->1134x12, size ratio 64.00, area ratio 64.00, 1288 msec 1134x768->1134x11, size ratio 69.82, area ratio 69.00, 1264 msec 1134x768->1134x10, size ratio 76.80, area ratio 76.00, 1256 msec 1134x768->1134x9, size ratio 85.33, area ratio 85.00, 1260 msec 1134x768->1134x8, size ratio 96.00, area ratio 96.00, 1264 msec 1134x768->1134x7, size ratio 109.71, area ratio 109.00, 1280 msec 1134x768->1134x6, size ratio 128.00, area ratio 128.00, 1348 msec 1134x768->1134x5, size ratio 153.60, area ratio 153.00, 1292 msec 1134x768->1134x4, size ratio 192.00, area ratio 192.00, 1324 msec 1134x768->1134x3, size ratio 256.00, area ratio 256.00, 1420 msec 1134x768->1134x2, size ratio 384.00, area ratio 384.00, 1380 msec * 1134x768->1134x1, size ratio 768.00, area ratio 768.00, 1324 msec * Scaling both: 1134x768->40x40, size ratio 28.35, area ratio 544.00, 676 msec 1134x768->39x39, size ratio 29.08, area ratio 572.00, 668 msec 1134x768->38x38, size ratio 29.84, area ratio 603.00, 708 msec 1134x768->37x37, size ratio 30.65, area ratio 636.00, 660 msec 1134x768->36x36, size ratio 31.50, area ratio 672.00, 748 msec 1134x768->35x35, size ratio 32.40, area ratio 710.00, 692 msec 1134x768->34x34, size ratio 33.35, area ratio 753.00, 708 msec 1134x768->33x33, size ratio 34.36, area ratio 799.00, 744 msec 1134x768->32x32, size ratio 35.44, area ratio 850.00, 732 msec 1134x768->31x31, size ratio 36.58, area ratio 906.00, 776 msec 1134x768->30x30, size ratio 37.80, area ratio 967.00, 868 msec 1134x768->29x29, size ratio 39.10, area ratio 1035.00, 828 msec 1134x768->28x28, size ratio 40.50, area ratio 1110.00, 864 msec 1134x768->27x27, size ratio 42.00, area ratio 1194.00, 1116 msec 1134x768->26x26, size ratio 43.62, area ratio 1288.00, 1108 msec 1134x768->25x25, size ratio 45.36, area ratio 1393.00, 1084 msec 1134x768->24x24, size ratio 47.25, area ratio 1512.00, 1028 msec 1134x768->23x23, size ratio 49.30, area ratio 1646.00, 696 msec * 1134x768->22x22, size ratio 51.55, area ratio 1799.00, 676 msec * 1134x768->21x21, size ratio 54.00, area ratio 1974.00, 760 msec * 1134x768->20x20, size ratio 56.70, area ratio 2177.00, 748 msec * 1134x768->19x19, size ratio 59.68, area ratio 2412.00, 816 msec * 1134x768->18x18, size ratio 63.00, area ratio 2688.00, 700 msec * 1134x768->17x17, size ratio 66.71, area ratio 3013.00, 668 msec * 1134x768->16x16, size ratio 70.88, area ratio 3402.00, 616 msec * 1134x768->15x15, size ratio 75.60, area ratio 3870.00, 660 msec * 1134x768->14x14, size ratio 81.00, area ratio 4443.00, 640 msec * 1134x768->13x13, size ratio 87.23, area ratio 5153.00, 656 msec * 1134x768->12x12, size ratio 94.50, area ratio 6048.00, 612 msec * 1134x768->11x11, size ratio 103.09, area ratio 7197.00, 680 msec * 1134x768->10x10, size ratio 113.40, area ratio 8709.00, 636 msec * 1134x768->9x9, size ratio 126.00, area ratio 10752.00, 652 msec * 1134x768->8x8, size ratio 141.75, area ratio 13608.00, 608 msec * 1134x768->7x7, size ratio 162.00, area ratio 17773.00, 604 msec * 1134x768->6x6, size ratio 189.00, area ratio 24192.00, 612 msec * 1134x768->5x5, size ratio 226.80, area ratio 34836.00, 664 msec * 1134x768->4x4, size ratio 283.50, area ratio 54432.00, 620 msec * 1134x768->3x3, size ratio 378.00, area ratio 96768.00, 636 msec * 1134x768->2x2, size ratio 567.00, area ratio 217728.00, 732 msec * 1134x768->1x1, size ratio 1134.00, area ratio 870912.00, 1228 msec * The output looks fine; what it's lacking is any certainty that my handling of non-zero offsets is correct. It looks like some image-scaling-correctness tests would be in order anyway - at present it only seems to test that the resulting image dimension is 1/2 that of the original (or whatever).
Created attachment 340977 [details] [review] Patch to circumvent pathological scaling cases doing extreme reduction in two steps This is an adaptation of Michael Chudobiak's two-step scaling patch in bug 522803, moved to the bottleneck through which all scaling passes. It makes the scaling execution time pretty much constant regardless of target size but needs checking that the source offset and destination offset stuff works right when the optimization kicks in.
(In reply to Martin Guy from comment #31) > The output looks fine; what it's lacking is any certainty that my handling > of non-zero offsets is correct. It looks like some image-scaling-correctness > tests would be in order anyway - at present it only seems to test that the > resulting image dimension is 1/2 that of the original (or whatever). There are "ref tests" in the test suite. pixbuf-reftest.c is one where the image is just loaded (I think we had some problems with palettes), some other tests use pixdata_equal() to compare the expected result with the actual one. You want to start with that?
Review of attachment 340977 [details] [review]: For committing this, we'll need a git formatted patch. This will allow us to have authorship, and a well-written commit message. Obviously, would be even better once we have the test cases to verify how it works before and after the patch, and avoid regressions. ::: gdk-pixbuf-2.31.1/gdk-pixbuf/gdk-pixbuf-scale.c @@ +130,3 @@ + * From http://freaknet.org/martin/tape/gos/misc/personal/msc/sqrt */ +static unsigned long +int_sqrt(unsigned long number) { We'll use the already optimised and maintained math library, thanks :) @@ +175,3 @@ src_pixels = gdk_pixbuf_read_pixels (src); + /* make_filter_table() bloats out in VM usage and consumes 100% CPU for You can add the comment and constants above the function. @@ +188,3 @@ +#define PATHO_SIZE_RATIO (1/256.0) +#define PATHO_AREA_RATIO (1/1600.0) + if (interp_type != GDK_INTERP_NEAREST) Maybe this could all be done in a separate function? It would make it more readable.
(In reply to Bastien Nocera from comment #33) > (In reply to Martin Guy from comment #31) > > The output looks fine; what it's lacking is any certainty that my handling > > of non-zero offsets is correct. It looks like some image-scaling-correctness > > tests would be in order anyway - at present it only seems to test that the > > resulting image dimension is 1/2 that of the original (or whatever). > > There are "ref tests" in the test suite. pixbuf-reftest.c is one where the > image is just loaded (I think we had some problems with palettes), some > other tests use pixdata_equal() to compare the expected result with the > actual one. I see no pixbuf-reftest.c here in Debian's gdk-pixbuf-2.31.1 source, but the test framework looks pretty easy to extend. Is there a preferred g* function to compare two images' contents, and can you suggest some tests that should have known results? I'm guessing that a 256x256 black and white checkerboard, reduced it to exactly 50% should have all pixels 50% grey (or checkerboard of (1,1,1) and (255,255,255) so the result is (128,128,128). For the offsets, scaling by 1:1, selecting a region of a source image and checking that it's identical to a file similarly created with the GIMP?
(In reply to Martin Guy from comment #35) > (In reply to Bastien Nocera from comment #33) > > (In reply to Martin Guy from comment #31) > > > The output looks fine; what it's lacking is any certainty that my handling > > > of non-zero offsets is correct. It looks like some image-scaling-correctness > > > tests would be in order anyway - at present it only seems to test that the > > > resulting image dimension is 1/2 that of the original (or whatever). > > > > There are "ref tests" in the test suite. pixbuf-reftest.c is one where the > > image is just loaded (I think we had some problems with palettes), some > > other tests use pixdata_equal() to compare the expected result with the > > actual one. > > I see no pixbuf-reftest.c here in Debian's gdk-pixbuf-2.31.1 source, gdk-pixbuf 2.36.0 is the latest version. 2.31.1 is more than 2 years old. > but the > test framework looks pretty easy to extend. Is there a preferred g* function > to compare two images' contents, and can you suggest some tests that should > have known results? There's already one called pixdata_equal() in the test suite. Of the latest version. You can probably compile the latest gdk-pixbuf without too much trouble, and without installing it. The tests within the source tree will use the libraries inside the source tree. But you'll likely want to use git if you want the patch to be ready for committing, and make it easier for you to provide those. > I'm guessing that a 256x256 black and white > checkerboard, reduced it to exactly 50% should have all pixels 50% grey (or > checkerboard of (1,1,1) and (255,255,255) so the result is (128,128,128). > For the offsets, scaling by 1:1, selecting a region of a source image and > checking that it's identical to a file similarly created with the GIMP? You can also generate it with the old version of the code, before your patch, as we know it's working, which would be your reference and compare it to a version after the patch.
> gdk-pixbuf 2.36.0 is the latest version. 2.31.1 is more than 2 years old. I'm working on git master now. > There's already one called pixdata_equal() in the test suite. > You can also generate it with the old version of the code, before your patch, > as we know it's working, which would be your reference and compare it to a > version after the patch. The result won't be pixel-per-pisel identical, if only because the intermediate image is stored at 8-bit color value precision, but checking that every color value is no more than 1 different from the one-step version, which should be anough to account for the inherent rounding errors. I notice that there are currently no tests for image scaling correctness, other than seeing whether the result size is as expected. As a run-up I've written a rudimentary test correct functioning, attached if you'd like to include it. It can't use pixdata_equal() because the HYPER scaler gives different results, getting corner and edge pixels different from the other two smooth scalers - attached. Either way, I'll do something similar for the two-step scaler cases. M
Created attachment 341145 [details] [review] Patch to add some rudimentary tests for correctness of image scaler's results
Created attachment 341146 [details] [review] Patch to add some rudimentary tests for correctness of image scaler's results (11.48 KB, patch) 2016-12-01 12:39 UTC, Martin Guy
OK, here's the current version. The criterion for scaling in two steps is now related to the number of inner loop iterations performed in make_filter_table(), which is where profiling show that the massive CPU time is spent and is also proportional to the size of the array it creates. The test is on the number of filter blocks it creates, and is chosen so that none of the timed test runs exceed the "normal" execution time by more than 50%. In practice, some of the higher-reduction scales still run in "usual" time while others take dozens or hundreds of time longer; we ensure it never slows down by more than 1.5 times. Included is a test suite for result correctness of the two-step part.
Created attachment 341345 [details] [review] Patch to circumvent pathological scaling cases doing extreme reduction in two steps, version 2
Currently, the heuristic is to do two-step scaling when the area reduction factor is over 1000, which also limits the filter table size to 2MB. The following plots show the time taken to downscale a 100x100 image by various ratios, without and with the two-step optimiation. The troublesome region executes in normal time for about half of the ratio pairs and takes an age for the other half but the correlation between scaling ratios and long execution times is unclear, presumably due to the CPU cache and the regions of the filter table that is actually used during the scaling. The current heuristic just draws a line round the whole troublesome area.
Created attachment 341348 [details] Plot of time in milliseconds to downscale a 100x100 image by various ratios without the 2-step scaler
Created attachment 341349 [details] Plot of time in milliseconds to downscale a 100x100 image by various ratios with the 2-step scaler
Created attachment 341351 [details] Test program used to generate graphs
Review of attachment 341345 [details] [review]: Oversight: need_to_prescale() should return FALSE if interp_type is NEAREST. The current patch does the two-step scaling needlessly also for NEAREST. In test suite, testing "destination" fields by scaling an image in four quarters: 381 g_test_add_data_func ("/pixbuf/scale/two-step/dest/hyper", &hyper, 382 test_dest); 383 /* Don't bother with hyper as it changes the edge pixels */ Remove the comment. Hyper was originally excluded from this test because, when scaling a 128x128 checkerboard of (1,1,1) and (255,255,255), it gives (129,129,129) and (127,127,127) for corner and edge pixels, but this edge effect only happens to the whole scaled image, not to a destination region, so it should give the same results whether done all at once or in parts.
Review of attachment 341146 [details] [review]: I've committed this with a number of changes, amongst them: - indentation (gdk-pixbuf doesn't use tabs for spacing) - make sure to have a space before parenthesis for function calls - space in between operators - use curly braces when conditions, or loops are multi-line - use g_assert_nonnull() when possible - use G_OBJECT() for g_object_unref() instead of casting to void *
Created attachment 342223 [details] [review] tests: Add rudimentary correctness tests for scaler The scaler's testsuite has no checks for correctness of the scaled image. This add some rudimentary ones, scaling a checkerboard to 1/2 size and seeing if it's all gray and checking the "dest" and "offset" parameters.
Comment on attachment 342223 [details] [review] tests: Add rudimentary correctness tests for scaler Attachment 342223 [details] pushed as ecea71e - tests: Add rudimentary correctness tests for scaler
Review of attachment 341345 [details] [review]: Can you please split the tests from the code as well? ::: gdk-pixbuf/pixops/pixops.c @@ +21,3 @@ #include <math.h> #include <glib.h> +#include <stdlib.h> /* for getenv() */ You could use g_getenv(). But... @@ +1748,3 @@ +/* + * Two-step scaler begins The "begins" is probably not necessary. @@ +1769,3 @@ + * GDK_INTER_BILINEAR, GDK_INTERP_TILES and GDK_INTER_HYPER all have + * similar symptoms; only GDK_INTERP_NEAREST does not need this trick. + **/ Finish the comment on the line above. @@ +1779,3 @@ + + /* The testsuite sets this to compare the results with and without it. */ + if (getenv("GDK_PIXBUF_DISABLE_TWO_STEP_SCALER")) return FALSE; I don't like this, I'd rather you passed the source pixbuf here, and check for some data being attached to the pixbuf object. For example: if (g_object_get_data (G_OBJECT (pixbuf), "disable-two-step-scaler") != NULL) return FALSE; And, in the tests, you'd set: g_object_set_data (G_OBJECT (pixbuf), "disable-two-step-scaler", GINT_TO_POINTER (1)); Also use 2 lines for this. @@ +1784,3 @@ + if (interp_type == PIXOPS_INTERP_HYPER) + { + n_x = ceil(1/scale_x + 3); space before the opening parenthesis. @@ +1957,3 @@ g_free (filter.y.weights); + if (tmp_buf) + g_free (tmp_buf); g_clear_pointer (&tmp_buf, g_free); ::: tests/pixbuf-scale-two-step.c @@ +118,3 @@ + + if (gdk_pixbuf_get_width(one) != gdk_pixbuf_get_width(two) || + gdk_pixbuf_get_height(one) != gdk_pixbuf_get_height(two)) Please use braces when the condition is multi-line... @@ +348,3 @@ + } + + g_object_unref ((void *) source); G_OBJECT()
Thanks. > Can you please split the tests from the code as well? You mean into two separate patches? > + if (getenv("GDK_PIXBUF_DISABLE_TWO_STEP_SCALER")) return FALSE; > I don't like this It turns out that using an environment variable is more useful than setting internal data because it can be set from the shell when launching any program without having to recompile it, making it easier to test a range of existing affected programs and, incidentally, to produce the plots. To me it seems simpler, more reliable and less easy to get wrong than attaching a property to some otherwise unused pixbuf and using other gdk internals to test it. Apart from being more awkward, the test's result depends less on other parts of gdk working correctly. In style it matches GDK_DISABLE_MEDIALIB in pixops/pixops.c If we set a property on, say, the source pixbuf and pass that down to where it is tested, suppose then that some test or user code tries scaling a NULL pixbuf - that would risk making it fail or dump core in the code that tests the property, instead of triggering the test for scaling NULL pixbufs, if there is one. Yes, we can do that too; the point is that a more complicated method to communicate a flag is more error-prone. Anyway, the functions that call this stuff don't have a pixbuf or other GOBJECT available; the whole pixops.c file deals in guchar pointers to the data and ints. I had tried using a global boolean but was stopped by unfathomable linker errors. Incidentally, the only other use of bare getenv() in the code base is in gdk-pixbuf/pixops/pixops.c ("GDK_DISABLE_MEDIALIB"); the others ("GDK_PIXBUF_MODULE_FILE" and "GDK_PIXBUF_MODULEDIR") use g_getenv(). Changing the MEDIALIB test to g_getenv would eliminate a compiler warning for pixops.c I suggest using_getenv() unless there's a better alternative solution.
Lets not introduce more random environment variables, please.
Can you suggest a working alternative please? A global boolean is out because you can't link to it from the test suite. There is no g_object to attach a random (ha!) property to. All I'm left with is: - touching a bizarrely-named file in /tmp - modifying all the functions in scaler call stack, from where the pixbufs disappear down to the bottom of the scaler, adding an extra boolean flag to every call that might end up in the scaler, then set a random property in the source pixbuf and making sure the random property is converted to a boolean at all the possible entry points to te stack. Frankly, these all seem worse.
(In reply to Martin Guy from comment #54) > Can you suggest a working alternative please? > > A global boolean is out because you can't link to it from the test suite. > > There is no g_object to attach a random (ha!) property to. Which is why we should pass one through.
Created attachment 343032 [details] [review] pixops: Add two-step scaler optimization As scaling becomes incredibly slow at high reduction factors, detect the pathological cases and do the scaling in two steps instead.
Created attachment 343033 [details] [review] tests: Move pixbuf creation helpers to test-common.[ch] Those will be used in the 2-step scaler tests.
Created attachment 343034 [details] [review] tests: Add two-step scaler test Test the output of scaling functions to see whether optimisation/simplification to avoid huge memory and CPU usage is effective and does not regress.
(In reply to Bastien Nocera from comment #55) > (In reply to Martin Guy from comment #54) > > Can you suggest a working alternative please? > > > > A global boolean is out because you can't link to it from the test suite. > > > > There is no g_object to attach a random (ha!) property to. > > Which is why we should pass one through. Turns out that we don't pass the GdkPixbuf all the way down to the pixops code. So let's use the envvar for testing. It doesn't need to be documented as it's a verification tool, not a testing tool.
Review of attachment 343033 [details] [review]: OK
Review of attachment 343034 [details] [review]: ---pixbuf-scale-two-step.c:333: > /* Don't bother with hyper as it changes the edge pixels */ We can drop this comment as it is no longer true. The hyper scaler gets edge pixels different from the other scalers so it was initially excluded from the region tests but it turns out that its subregion-selection code tests OK anyway, presumably because the edge effects apply to the edges of the source image, not of the source or target regions. Just the comment got left behind.
Created attachment 343076 [details] [review] pixops: Add two-step scaler optimization v2 NEAREST doesn't need the optimization, but was getting it anyway. The difference between this patch and "pixops: Add two-step scaler optimization" is shown below. < @@ -1745,6 +1745,135 @@ make_weights (PixopsFilter *filter, --- > @@ -1745,6 +1745,139 @@ make_weights (PixopsFilter *filter, 57,66c55,68 < + if (interp_type == PIXOPS_INTERP_HYPER) < + { < + n_x = ceil (1 / scale_x + 3); < + n_y = ceil (1 / scale_y + 3); < + } < + else /* TILES and BILINEAR */ < + { < + n_x = ceil (1 / scale_x + 1); < + n_y = ceil (1 / scale_y + 1); < + } --- > + switch (interp_type) > + case PIXOPS_INTERP_HYPER: > + n_x = ceil (1 / scale_x + 3); > + n_y = ceil (1 / scale_y + 3); > + break; > + case PIXOPS_INTERP_TILES: > + case PIXOPS_INTERP_BILINEAR: > + n_x = ceil (1 / scale_x + 1); > + n_y = ceil (1 / scale_y + 1); > + break; > + case PIXOPS_INTERP_NEAREST: > + /* Doesn't need the optimization */ > + return FALSE; > + }
(In reply to Martin Guy from comment #62) > Created attachment 343076 [details] [review] [review] > pixops: Add two-step scaler optimization v2 > > NEAREST doesn't need the optimization, but was getting it anyway. The > difference between this patch and "pixops: Add two-step scaler optimization" > is shown below. Please don't edit files in place, provide separate patches to be applied on top of the existing ones.
Thanks. It's not EIP - it's a new patch generated from your work, applying the correction and regenerating a corrected patch. I included the significant differences here as an aid to review. If you prefer to commit a buggy patch followed by a correction, that's fine by me, but it feels to me that I'm being told again and again to do the company dance, which is not something I'm really interested in learning, as I am already discouraged from ever doing work on GTK/GDK again, and the experience is unlikely to be useful when interacting with other, healther, open source projects. That said, I had already flagged these two corrections in my comments previous to your patch-splitting work, but you seem not to have seen that. I provided you with a fixed version of the more erronesous one of your patches to save you work, but that too has been poo-pooed. Incidentally, what brought me here is that I am writing an article comparing all the existing C GUI toolkits. The poor experience trying to fix the second-buggiest one will be included in the section about GTK.
(In reply to Martin Guy from comment #64) > Thanks. It's not EIP - it's a new patch generated from your work, applying > the correction and regenerating a corrected patch. I included the > significant differences here as an aid to review. That's nice, but you also dropped the bug reference from the commit message, which makes me wonder if there were more significant changes in the patches as well. I'd rather have had a fixup patch which I can merge into the patches already in this bug, so that I don't need to review the whole patch line-by-line. > If you prefer to commit a buggy patch followed by a correction, that's fine > by me, but it feels to me that I'm being told again and again to do the > company dance, which is not something I'm really interested in learning, as > I am already discouraged from ever doing work on GTK/GDK again, and the > experience is unlikely to be useful when interacting with other, healther, > open source projects. > > That said, I had already flagged these two corrections in my comments > previous to your patch-splitting work, but you seem not to have seen that. I > provided you with a fixed version of the more erronesous one of your patches > to save you work, but that too has been poo-pooed. Poo-pooed what? Were those changes hidden in a newer version of the patches, in between the first post and me fixing up those first patches? > Incidentally, what brought me here is that I am writing an article comparing > all the existing C GUI toolkits. The poor experience trying to fix the > second-buggiest one will be included in the section about GTK. I hope you mention the days I spent cleaning up your code to be readable in your article as well. It's nice of you to have dropped by and helped fix this, but this sort of comment won't help the patches get merged quicker, or see a change in what we consider acceptable code to be merged. This patch is waiting on Matthias or Federico reviewing them. I'll try to integrate your changes into them.
Created attachment 343254 [details] [review] pixops: Add two-step scaler optimization As scaling becomes incredibly slow at high reduction factors, detect the pathological cases and do the scaling in two steps instead.
Created attachment 343255 [details] [review] tests: Move pixbuf creation helpers to test-common.[ch] Those will be used in the 2-step scaler tests.
Created attachment 343256 [details] [review] tests: Add two-step scaler test Test the output of scaling functions to see whether optimisation/simplification to avoid huge memory and CPU usage is effective and does not regress.
Seeing as we're probably not going to get an in-depth review, I'm pushing this and we'll follow up on specific problems. Thanks for your help solving this problem. Attachment 343254 [details] pushed as 61e3ede - pixops: Add two-step scaler optimization Attachment 343255 [details] pushed as 5f232dc - tests: Move pixbuf creation helpers to test-common.[ch] Attachment 343256 [details] pushed as eee598c - tests: Add two-step scaler test