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 <[email protected]> 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()); } }
