sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject [sis] 01/02: Add more tests and add comments about optimization strategies that have been discarded. Two strategies were tried and failed to provide significantly better performance:
Date Wed, 30 Dec 2020 19:23:12 GMT
This is an automated email from the ASF dual-hosted git repository.

desruisseaux pushed a commit to branch geoapi-4.0
in repository https://gitbox.apache.org/repos/asf/sis.git

commit 76cd431653924db774256d694fba7aee9632adc4
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Wed Dec 30 16:01:51 2020 +0100

    Add more tests and add comments about optimization strategies that have been discarded.
    Two strategies were tried and failed to provide significantly better performance:
    
    - Leveraging Java2D optimizations for integer types by reading sample values as `int`
before conversion to `double`.
    - Reducing the amount of data read by `getPixels(…)` by moving values that are still
valid.
---
 .../java/org/apache/sis/image/BandedIterator.java  | 14 ++-
 .../java/org/apache/sis/image/PixelIterator.java   | 51 ++++++++---
 .../org/apache/sis/image/PixelIteratorTest.java    | 99 +++++++++++++++++++---
 3 files changed, 131 insertions(+), 33 deletions(-)

diff --git a/core/sis-feature/src/main/java/org/apache/sis/image/BandedIterator.java b/core/sis-feature/src/main/java/org/apache/sis/image/BandedIterator.java
index 2f9fce8..9bab905 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/image/BandedIterator.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/image/BandedIterator.java
@@ -338,10 +338,9 @@ final class BandedIterator extends WritablePixelIterator {
          */
         @Override
         Object getPixels(final Raster raster, int subX, int subY, final int subWidth, int
subHeight, final int mode) {
-            if (mode != TRANSFER_FROM_OTHER) {
-                assert subX == x && subY == y;          // Constraint documented
in parent class.
+            final float[] target = (mode == DIRECT) ? data : transfer;
+            if (mode != TRANSFER_FROM_OTHER && subY == y) {
                 final DataBuffer source = buffer;
-                final float[]    target = (mode == DIRECT) ? data : transfer;
                 final int        toNext = scanlineStride - subWidth;
                 final int        numBds = numBands;
                 int srcOff = subX + xToBuffer;
@@ -360,7 +359,7 @@ final class BandedIterator extends WritablePixelIterator {
                 return target;
             }
             // Fallback for all cases that we can not handle with above loop.
-            return raster.getPixels(subX, subY, subWidth, subHeight, transfer);
+            return raster.getPixels(subX, subY, subWidth, subHeight, target);
         }
 
         /**
@@ -408,10 +407,9 @@ final class BandedIterator extends WritablePixelIterator {
          */
         @Override
         Object getPixels(final Raster raster, int subX, int subY, final int subWidth, int
subHeight, final int mode) {
-            if (mode != TRANSFER_FROM_OTHER) {
-                assert subX == x && subY == y;          // Constraint documented
in parent class.
+            final double[] target = (mode == DIRECT) ? data : transfer;
+            if (mode != TRANSFER_FROM_OTHER && subY == y) {
                 final DataBuffer source = buffer;
-                final double[]   target = (mode == DIRECT) ? data : transfer;
                 final int        toNext = scanlineStride - subWidth;
                 final int        numBds = numBands;
                 int srcOff = subX + xToBuffer;
@@ -430,7 +428,7 @@ final class BandedIterator extends WritablePixelIterator {
                 return target;
             }
             // Fallback for all cases that we can not handle with above loop.
-            return raster.getPixels(subX, subY, subWidth, subHeight, transfer);
+            return raster.getPixels(subX, subY, subWidth, subHeight, target);
         }
 
         /**
diff --git a/core/sis-feature/src/main/java/org/apache/sis/image/PixelIterator.java b/core/sis-feature/src/main/java/org/apache/sis/image/PixelIterator.java
index 7dd9366..c77a208 100644
--- a/core/sis-feature/src/main/java/org/apache/sis/image/PixelIterator.java
+++ b/core/sis-feature/src/main/java/org/apache/sis/image/PixelIterator.java
@@ -566,7 +566,14 @@ public class PixelIterator {
      * @return the most efficient data type for transferring data.
      */
     public TransferType<?> getTransferType() {
-        return TransferType.valueOf(image != null ? image.getSampleModel().getTransferType()
: currentRaster.getTransferType());
+        return TransferType.valueOf(getSampleModel().getTransferType());
+    }
+
+    /**
+     * Returns the sample model of the image or raster.
+     */
+    private SampleModel getSampleModel() {
+        return (image != null) ? image.getSampleModel() : currentRaster.getSampleModel();
     }
 
     /**
@@ -587,7 +594,7 @@ public class PixelIterator {
          * stay consistent at least with the fact that all getter methods in PixelIterator
return information relative
          * to current iterator position.
          */
-        final SampleModel model = (currentRaster != null) ? currentRaster.getSampleModel()
: image.getSampleModel();
+        final SampleModel model = getSampleModel();
         final NumberRange<?>[] ranges = new NumberRange<?>[model.getNumBands()];
         if (ranges.length != 0) {
             final int dataType = model.getDataType();
@@ -1088,22 +1095,24 @@ public class PixelIterator {
     public <T extends Buffer> Window<T> createWindow(final TransferType<T>
type) {
         ArgumentChecks.ensureNonNull("type", type);
         final int length = numBands * windowWidth * windowHeight;
+        // `transfer` array needs one row or one column less than `data`.
         final int transferLength = length - numBands * Math.min(windowWidth, windowHeight);
-        // `transfer` will always have at least one row or one column less than `data`.
+        final Window<?> window;
         switch (type.dataBufferType) {
-            case DataBuffer.TYPE_INT:    return (Window<T>) new IntWindow(new int 
 [length], new int   [transferLength]);
-            case DataBuffer.TYPE_FLOAT:  return (Window<T>)  createWindow(new float
[length], new float [transferLength]);
-            case DataBuffer.TYPE_DOUBLE: return (Window<T>)  createWindow(new double[length],
new double[transferLength]);
+            case DataBuffer.TYPE_INT:    window = new IntWindow(new int   [length], new int
  [transferLength]); break;
+            case DataBuffer.TYPE_FLOAT:  window =  createWindow(new float [length], new float
[transferLength]); break;
+            case DataBuffer.TYPE_DOUBLE: window =  createWindow(new double[length], new double[transferLength]);
break;
             default: throw new AssertionError(type);  // Should never happen unless we updated
TransferType and forgot to update this method.
         }
+        return (Window<T>) window;
     }
 
     /**
      * Creates a window for floating point values using the given arrays. This is a hook
for allowing subclasses
      * to specify alternative implementations. We provide hooks only for floating point types,
not for integers,
      * because the {@code int} type is already optimized by Java2D with specialized {@code
Raster.getPixels(…)}
-     * method implementations. By contract the {@code float} and {@code double} types in
Java2D use generic and
-     * slower code path.
+     * method implementations. By contrast the {@code float} and {@code double} types in
Java2D use generic and
+     * slower code paths.
      */
     Window<FloatBuffer>  createWindow( float[] data,  float[] transfer) {return new
 FloatWindow(data, transfer);}
     Window<DoubleBuffer> createWindow(double[] data, double[] transfer) {return new
DoubleWindow(data, transfer);}
@@ -1189,11 +1198,7 @@ public class PixelIterator {
          * depending on the buffer data type.
          *
          * <h4>Constraints</h4>
-         * If {@code mode} == {@link #DIRECT} or {@link #TRANSFER}, then {@code subX}={@link
#x} and
-         * {@code subY}={@link #y}. This constraint allows subclasses to use cached values
for current position.
-         * Otherwise ({@code mode} == {@link #TRANSFER_FROM_OTHER}), {@code subX} and {@code
subY} can be anything.
-         *
-         * <p>{@code subWidth} and {@code subHeight} shall always be greater than zero.</p>
+         * {@code subWidth} and {@code subHeight} shall always be greater than zero.
          *
          * @param  raster     the raster from which to get the pixel values.
          * @param  subX       the X coordinate of the upper-left pixel location.
@@ -1263,6 +1268,8 @@ public class PixelIterator {
 
     /**
      * {@link Window} implementation backed by an array of {@code float[]}.
+     * This implementation is provided for completeness but is rarely used.
+     * We do not attempt performance optimization for this case.
      */
     private final class FloatWindow extends Window<FloatBuffer> {
         /**
@@ -1309,6 +1316,16 @@ public class PixelIterator {
 
     /**
      * {@link Window} implementation backed by an array of {@code double[]}.
+     * This is the implementation used by Apache SIS for most computations.
+     *
+     * <div class="note"><b>Performance note</b>
+     * Java2D has numerous optimizations for the integer cases, with no equivalent for the
floating point cases.
+     * Consequently if the data buffer is known to use some integer type, it is faster to
get integer values and
+     * convert them to {@code double} values instead than to request directly floating-point
values. However the
+     * improvement is not as much as using {@link BandedIterator} as least for small windows.
For that reason,
+     * we do not provide the "integers converted to doubles" performance workaround for now.
Even if we provided
+     * it, this {@code DoubleWindow} would still be necessary for the general case (non-integer
data buffers).
+     * </div>
      */
     private final class DoubleWindow extends Window<DoubleBuffer> {
         /**
@@ -1356,6 +1373,12 @@ public class PixelIterator {
     /**
      * Updates the content of given window with the sample values in the region starting
at current iterator position.
      *
+     * <div class="note"><b>Performance note</b>
+     * we could store the position of last update in the {@code Window} object and invoke
{@code getPixels(…)}
+     * only for window area that changed. Sample values that are still inside the window
could be moved with
+     * {@code System.arraycopy(…)}. We tried that approach, but performance at least on
small windows was worst
+     * than current naive implementation.</div>
+     *
      * @param  window  the window to update.
      * @param  data    the array of primitive type where sample values are stored.
      */
@@ -1370,7 +1393,7 @@ public class PixelIterator {
             /*
              * Optimization for the case where the full window is inside current raster.
              * This is the vast majority of cases, so we perform this check soon before
-             * to compute more internal variables.
+             * to compute more local variables.
              */
             final Object transfer = window.getPixels(currentRaster, x, y, subWidth, subHeight,
Window.DIRECT);
             assert transfer == data;
diff --git a/core/sis-feature/src/test/java/org/apache/sis/image/PixelIteratorTest.java b/core/sis-feature/src/test/java/org/apache/sis/image/PixelIteratorTest.java
index 9f8c71e..5e2be98 100644
--- a/core/sis-feature/src/test/java/org/apache/sis/image/PixelIteratorTest.java
+++ b/core/sis-feature/src/test/java/org/apache/sis/image/PixelIteratorTest.java
@@ -16,7 +16,11 @@
  */
 package org.apache.sis.image;
 
+import java.util.Random;
 import java.util.Optional;
+import java.nio.IntBuffer;
+import java.nio.FloatBuffer;
+import java.nio.DoubleBuffer;
 import java.awt.Point;
 import java.awt.Dimension;
 import java.awt.Rectangle;
@@ -27,11 +31,11 @@ import java.awt.image.Raster;
 import java.awt.image.SampleModel;
 import java.awt.image.WritableRaster;
 import java.awt.image.WritableRenderedImage;
-import java.nio.FloatBuffer;
 import org.opengis.coverage.grid.SequenceType;
 import org.apache.sis.util.ArraysExt;
 import org.apache.sis.measure.NumberRange;
 import org.apache.sis.test.DependsOnMethod;
+import org.apache.sis.test.TestUtilities;
 import org.apache.sis.test.TestCase;
 import org.junit.After;
 import org.junit.Test;
@@ -1148,33 +1152,106 @@ public strictfp class PixelIteratorTest extends TestCase {
     /**
      * Verifies {@link PixelIterator#createWindow(TransferType)}.
      * This method assumes that the iterator traverses the full image (no sub-area).
+     * All 3 window types are tested, but values are not necessarily fetched at each iteration
step.
+     * Fetching values or not is determined randomly for testing {@code Window} capability
to reuse
+     * values from previous iteration step.
      *
      * @see #verifyIteration(boolean)
      * @see #verifyIterationAfterMove(int, int)
      */
     private void verifyWindow(final Dimension window) {
-        final PixelIterator.Window<FloatBuffer> w = iterator.createWindow(TransferType.FLOAT);
-        final FloatBuffer values = w.values;
-        final float[] windowValues = new float[window.width * window.height * numBands];
+        final Random random = TestUtilities.createRandomNumberGenerator();
+        final WindowVerifier verifier = new WindowVerifier(window);
         while (iterator.next()) {
             final Point pos = iterator.getPosition();
             pos.translate(-xmin, -ymin);
-            w.update();
+            verifier.test(pos, random.nextBoolean(), random.nextBoolean(), random.nextBoolean());
+        }
+        /*
+         * Test again, but moving the window at random positions.
+         */
+        iterator.rewind();
+        for (int i=0; i<50; i++) {
+            final int x = random.nextInt(width  - window.width);
+            final int y = random.nextInt(height - window.height);
+            iterator.moveTo(x + xmin, y + ymin);
+            verifier.test(new Point(x,y), true, true, true);
+        }
+    }
+
+    /**
+     * Helper class for testing {@link org.apache.sis.image.PixelIterator.Window} values
+     * at current iterator position. This class tests all 3 window types.
+     */
+    private final class WindowVerifier {
+        private final Dimension window;
+        private final float[] windowValues;
+        private final PixelIterator.Window<IntBuffer> wi;
+        private final PixelIterator.Window<FloatBuffer> wf;
+        private final PixelIterator.Window<DoubleBuffer> wd;
+
+        /**
+         * Creates a new verifier for windows of the given size.
+         */
+        WindowVerifier(final Dimension window) {
+            this.window = window;
+            wi = iterator.createWindow(TransferType.INT);
+            wf = iterator.createWindow(TransferType.FLOAT);
+            wd = iterator.createWindow(TransferType.DOUBLE);
+            windowValues = new float[window.width * window.height * numBands];
+        }
+
+        /**
+         * Tests window values at current iterator position.
+         *
+         * @param  pos  (0,0)-based position of expected values.
+         * @param  ti   whether to test {@code int} values.
+         * @param  tf   whether to test {@code float} values.
+         * @param  td   whether to test {@code double} values.
+         */
+        public void test(final Point pos, final boolean ti, final boolean tf, final boolean
td) {
             getExpectedWindowValues(new Rectangle(pos, window), windowValues);
+            if (ti) wi.update();
+            if (tf) wf.update();
+            if (td) wd.update();
             int indexOfExpected = 0;
             for (int y=0; y<window.height; y++) {
                 for (int x=0; x<window.width; x++) {
                     for (int b=0; b<numBands; b++) {
-                        final float a = values.get();
-                        final float e = windowValues[indexOfExpected++];
-                        if (Float.floatToRawIntBits(a) != Float.floatToRawIntBits(e)) {
-                            fail("Index (" + x + ", " + y + ") in window starting at index
("
-                                    + pos.x + ", " + pos.y + "), band " + b + ": expected
" + e + " but got " + a);
+                        final float expected = windowValues[indexOfExpected++];
+                        TransferType<?> type = null;
+                        float actual = Float.NaN;
+                        boolean success = true;
+                        if (tf) {
+                            type    = TransferType.FLOAT;
+                            actual  = wf.values.get();
+                            success = Float.floatToRawIntBits(actual) == Float.floatToRawIntBits(expected);
+                        }
+                        if (success) {
+                            if (td) {
+                                type    = TransferType.DOUBLE;
+                                actual  = (float) wd.values.get();
+                                success = Float.floatToRawIntBits(actual) == Float.floatToRawIntBits(expected);
+                            }
+                            if (success) {
+                                if (ti) {
+                                    type    = TransferType.INT;
+                                    actual  = wi.values.get();
+                                    success = !(StrictMath.abs(actual - expected) >= 1);
 // Use `!` for accepting NaN.
+                                }
+                                if (success) {
+                                    continue;
+                                }
+                            }
                         }
+                        fail("Type " + type + " index (" + x + ", " + y + ") in window starting
at index (" +
+                             pos.x + ", " + pos.y + "), band " + b + ": expected " + expected
+ " but got " + actual);
                     }
                 }
             }
-            assertEquals("buffer.remaining()", 0, values.remaining());
+            if (ti) assertEquals("buffer.remaining()", 0, wi.values.remaining());
+            if (tf) assertEquals("buffer.remaining()", 0, wf.values.remaining());
+            if (td) assertEquals("buffer.remaining()", 0, wd.values.remaining());
         }
     }
 


Mime
View raw message