You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by de...@apache.org on 2020/12/30 19:23:12 UTC
[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:
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 <ma...@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());
}
}