From a6789f8a91ca11fac840b958ee9207581ea4d14f Mon Sep 17 00:00:00 2001 From: kiramt Date: Tue, 26 Sep 2017 10:26:42 +0100 Subject: [PATCH] JAL-2647 Added iterators and associated tests and benchmarks --- .../org/jalview/HiddenColsIteratorsBenchmark.java | 193 ++++++++++++++++ .../java/org/jalview/HiddenColumnsBenchmark.java | 4 +- src/jalview/appletgui/ScalePanel.java | 17 +- src/jalview/appletgui/SeqCanvas.java | 19 +- src/jalview/datamodel/HiddenColumns.java | 234 +++++++++++++++++++- src/jalview/gui/ScalePanel.java | 18 +- src/jalview/gui/SeqCanvas.java | 22 +- test/jalview/datamodel/HiddenColumnsTest.java | 101 +++++++++ 8 files changed, 559 insertions(+), 49 deletions(-) create mode 100644 benchmarking/src/main/java/org/jalview/HiddenColsIteratorsBenchmark.java diff --git a/benchmarking/src/main/java/org/jalview/HiddenColsIteratorsBenchmark.java b/benchmarking/src/main/java/org/jalview/HiddenColsIteratorsBenchmark.java new file mode 100644 index 0000000..7836367 --- /dev/null +++ b/benchmarking/src/main/java/org/jalview/HiddenColsIteratorsBenchmark.java @@ -0,0 +1,193 @@ +/* + * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$) + * Copyright (C) $$Year-Rel$$ The Jalview Authors + * + * This file is part of Jalview. + * + * Jalview is free software: you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation, either version 3 + * of the License, or (at your option) any later version. + * + * Jalview is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR + * PURPOSE. See the GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Jalview. If not, see . + * The Jalview Authors are detailed in the 'AUTHORS' file. + */ + +package org.jalview; + +import org.openjdk.jmh.annotations.Benchmark; +import org.openjdk.jmh.annotations.BenchmarkMode; +import org.openjdk.jmh.annotations.Fork; +import org.openjdk.jmh.annotations.Measurement; +import org.openjdk.jmh.annotations.Mode; +import org.openjdk.jmh.annotations.Setup; +import org.openjdk.jmh.annotations.State; +import org.openjdk.jmh.annotations.Warmup; +import org.openjdk.jmh.infra.Blackhole; +import org.openjdk.jmh.annotations.Scope; +import org.openjdk.jmh.annotations.Param; + +import java.util.Iterator; +import java.util.List; +import java.util.Random; +import java.util.concurrent.TimeUnit; + +import jalview.datamodel.ColumnSelection; +import jalview.datamodel.HiddenColumns; + +/* + * A class to benchmark hidden columns performance + */ +@Warmup(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS) +@Measurement(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS) +@Fork(1) +public class HiddenColsIteratorsBenchmark { + /* + * State with multiple hidden columns and a start position set + */ + @State(Scope.Thread) + public static class HiddenColsAndStartState + { + @Param({"300", "10000", "100000"}) + public int maxcols; + + @Param({"1", "50", "90"}) + public int startpcnt; // position as percentage of maxcols + + @Param({"1","15","100"}) + public int hide; + + HiddenColumns h = new HiddenColumns(); + Random rand = new Random(); + + public int hiddenColumn; + public int visibleColumn; + + @Setup + public void setup() + { + rand.setSeed(1234); + int lastcol = 0; + while (lastcol < maxcols) + { + int count = rand.nextInt(100); + lastcol += count; + h.hideColumns(lastcol, lastcol+hide); + lastcol+=hide; + } + + // make sure column at start is hidden + hiddenColumn = (int)(maxcols * startpcnt/100.0); + h.hideColumns(hiddenColumn, hiddenColumn); + + // and column after start is visible + ColumnSelection sel = new ColumnSelection(); + h.revealHiddenColumns(hiddenColumn+hide, sel); + visibleColumn = hiddenColumn+hide; + + System.out.println("Maxcols: " + maxcols + " HiddenCol: " + hiddenColumn + " Hide: " + hide); + System.out.println("Number of hidden columns: " + h.getSize()); + } + } + + /* Convention: functions in alphabetical order */ + + @Benchmark + @BenchmarkMode({Mode.Throughput}) + public int benchStartIterator(HiddenColsAndStartState tstate) + { + int res = 0; + int startx = tstate.visibleColumn; + Iterator it = tstate.h.getBoundedStartIterator(startx, + startx+60, true); + while (it.hasNext()) + { + res = it.next() - startx; + Blackhole.consumeCPU(5); + } + return res; + } + + @Benchmark + @BenchmarkMode({Mode.Throughput}) + public int benchBoundedIterator(HiddenColsAndStartState tstate) + { + int startx = tstate.visibleColumn; + int blockStart = startx; + int blockEnd; + int screenY = 0; + Iterator it = tstate.h.getBoundedIterator(startx, + startx+60, true); + while (it.hasNext()) + { + int[] region = it.next(); + + blockEnd = Math.min(region[0] - 1, blockStart + 60 - screenY); + + screenY += blockEnd - blockStart + 1; + blockStart = region[1] + 1; + + Blackhole.consumeCPU(5); + } + return blockStart; + } + + + @Benchmark + @BenchmarkMode({Mode.Throughput}) + public int benchHiddenColsCopy(HiddenColsAndStartState tstate) + { + int startx = tstate.visibleColumn; + int blockEnd; + int blockStart = startx; + int screenY = 0; + for (int[] region : tstate.h.getHiddenColumnsCopy()) + { + int hideStart = region[0]; + int hideEnd = region[1]; + + if (hideStart <= blockStart) + { + blockStart += (hideEnd - hideStart) + 1; + continue; + } + + //do something + Blackhole.consumeCPU(5); + blockEnd = Math.min(hideStart - 1, blockStart + 60 - screenY); + + screenY += blockEnd - blockStart + 1; + blockStart = hideEnd + 1; + + if (screenY > 60) + { + //done + break; + } + } + return blockStart; + } + + + @Benchmark + @BenchmarkMode({Mode.Throughput}) + public int benchLoop1(HiddenColsAndStartState tstate) + { + int res = 0; + int startx = tstate.visibleColumn; + List positions = tstate.h.findHiddenRegionPositions(startx, startx+60); + + for (int pos : positions) + { + res = pos - startx; + Blackhole.consumeCPU(5); + } + return res; + } +} diff --git a/benchmarking/src/main/java/org/jalview/HiddenColumnsBenchmark.java b/benchmarking/src/main/java/org/jalview/HiddenColumnsBenchmark.java index eb35e3b..383a064 100644 --- a/benchmarking/src/main/java/org/jalview/HiddenColumnsBenchmark.java +++ b/benchmarking/src/main/java/org/jalview/HiddenColumnsBenchmark.java @@ -112,12 +112,12 @@ public class HiddenColumnsBenchmark return tstate.h.findColumnPosition(tstate.visibleColumn); } - @Benchmark + /*@Benchmark @BenchmarkMode({Mode.Throughput}) public List benchFindHiddenRegionPositions(HiddenColsAndStartState tstate) { return tstate.h.findHiddenRegionPositions(); - } + }*/ @Benchmark @BenchmarkMode({Mode.Throughput}) diff --git a/src/jalview/appletgui/ScalePanel.java b/src/jalview/appletgui/ScalePanel.java index e00db7c..bbbb92b 100755 --- a/src/jalview/appletgui/ScalePanel.java +++ b/src/jalview/appletgui/ScalePanel.java @@ -42,6 +42,7 @@ import java.awt.event.MouseEvent; import java.awt.event.MouseListener; import java.awt.event.MouseMotionListener; import java.beans.PropertyChangeEvent; +import java.util.Iterator; import java.util.List; public class ScalePanel extends Panel @@ -436,19 +437,17 @@ public class ScalePanel extends Panel if (av.getShowHiddenMarkers()) { int widthx = 1 + endx - startx; - List positions = hidden.findHiddenRegionPositions(startx, - startx + widthx + 1); - for (int pos : positions) + Iterator it = hidden.getBoundedStartIterator(startx, + startx + widthx + 1, true); + while (it.hasNext()) { - res = pos - startx; + res = it.next() - startx; gg.fillPolygon( new int[] - { -1 + res * avCharWidth - avcharHeight / 4, - -1 + res * avCharWidth + avcharHeight / 4, - -1 + res * avCharWidth }, - new int[] - { y, y, y + 2 * yOf }, 3); + { -1 + res * avCharWidth - avcharHeight / 4, -1 + res * avCharWidth + avcharHeight / 4, + -1 + res * avCharWidth }, new int[] + { y, y, y + 2 * yOf }, 3); } } } diff --git a/src/jalview/appletgui/SeqCanvas.java b/src/jalview/appletgui/SeqCanvas.java index 5667b6e..20ec665 100755 --- a/src/jalview/appletgui/SeqCanvas.java +++ b/src/jalview/appletgui/SeqCanvas.java @@ -37,7 +37,7 @@ import java.awt.Graphics; import java.awt.Image; import java.awt.Panel; import java.beans.PropertyChangeEvent; -import java.util.List; +import java.util.Iterator; public class SeqCanvas extends Panel implements ViewportListenerI { @@ -491,21 +491,16 @@ public class SeqCanvas extends Panel implements ViewportListenerI HiddenColumns hidden = av.getAlignment().getHiddenColumns(); g.setColor(Color.blue); int res; - List positions = hidden.findHiddenRegionPositions(startRes, - endx + 1); - for (int pos : positions) + Iterator it = hidden.getBoundedStartIterator(startRes, + endx + 1, true); + while (it.hasNext()) { - res = pos - startRes; - + res = it.next() - startRes; gg.fillPolygon( new int[] - { res * avcharWidth - avcharHeight / 4, - res * avcharWidth + avcharHeight / 4, - res * avcharWidth }, + { res * avcharWidth - avcharHeight / 4, res * avcharWidth + avcharHeight / 4, res * avcharWidth }, new int[] - { ypos - (avcharHeight / 2), ypos - (avcharHeight / 2), - ypos - (avcharHeight / 2) + 8 }, - 3); + { ypos - (avcharHeight / 2), ypos - (avcharHeight / 2), ypos - (avcharHeight / 2) + 8 }, 3); } } diff --git a/src/jalview/datamodel/HiddenColumns.java b/src/jalview/datamodel/HiddenColumns.java index 8380e1f..9f3b929 100644 --- a/src/jalview/datamodel/HiddenColumns.java +++ b/src/jalview/datamodel/HiddenColumns.java @@ -25,6 +25,7 @@ import jalview.util.Comparison; import java.util.ArrayList; import java.util.BitSet; import java.util.Collections; +import java.util.Iterator; import java.util.List; import java.util.Vector; import java.util.concurrent.locks.ReentrantReadWriteLock; @@ -62,7 +63,7 @@ public class HiddenColumns { if (copy.hiddenColumns != null) { - hiddenColumns = copy.copyHiddenRegionsToArrayList(); + hiddenColumns = copy.copyHiddenRegionsToArrayList(0); } } } finally @@ -374,7 +375,7 @@ public class HiddenColumns // iterate from start to end, adding start positions of each // hidden region. Positions are visible columns count, not absolute while (i < hiddenColumns.size() - && (hiddenColumns.get(i)[0] < end + hiddenSoFar)) + && (hiddenColumns.get(i)[0] < end)) { int[] region = hiddenColumns.get(i); positions.add(region[0] - hiddenSoFar); @@ -622,7 +623,7 @@ public class HiddenColumns } } - private ArrayList copyHiddenRegionsToArrayList() + private ArrayList copyHiddenRegionsToArrayList(int startIndex) { int size = 0; if (hiddenColumns != null) @@ -631,7 +632,7 @@ public class HiddenColumns } ArrayList copy = new ArrayList<>(size); - for (int i = 0, j = size; i < j; i++) + for (int i = startIndex, j = size; i < j; i++) { int[] rh; int[] cp; @@ -660,7 +661,7 @@ public class HiddenColumns try { LOCK.readLock().lock(); - return copyHiddenRegionsToArrayList(); + return copyHiddenRegionsToArrayList(0); } finally { LOCK.readLock().unlock(); @@ -1446,4 +1447,227 @@ public class HiddenColumns LOCK.readLock().unlock(); } } + + public Iterator getBoundedIterator(int start, int end, + boolean useCopy) + { + return new BoundedHiddenColsIterator(start, end, useCopy); + } + + public Iterator getBoundedStartIterator(int start, int end, + boolean useCopy) + { + return new BoundedStartRegionIterator(start, end, useCopy); + } + + /** + * An iterator which iterates over hidden column regions in a range. + * + * @author kmourao + * + */ + + + class BoundedHiddenColsIterator implements Iterator + { + + private int start; // start position to iterate from + + private int end; // end position to iterate to + + // current index in hiddenColumns + private int currentPosition = 0; + + // current column in hiddenColumns + private int[] currentRegion; + + // whether to make a local copy of hiddenColumns + private final boolean useCopy; + + // local copy or reference to hiddenColumns + private List localHidden; + + /** + * Construct an iterator over hiddenColums bounded at + * [lowerBound,upperBound] + * + * @param lowerBound + * lower bound to iterate from + * @param upperBound + * upper bound to iterate to + * @param opt + * Option.OVERLAP: regions which overlap [lowerBound,upperBound] + * are included Option.START: regions which start in + * [lowerBound,upperBound] are included + * @param useAbsolutePos + * have bounds and return values with reference to absolute indices + * (if false, use indices for visible columns) + * @param useCopyCols + * whether to make a local copy of hiddenColumns for iteration (set + * to true if calling from outwith the HiddenColumns class) + */ + BoundedHiddenColsIterator(int lowerBound, int upperBound, + boolean useCopyCols) + { + start = lowerBound; + end = upperBound; + useCopy = useCopyCols; + + try + { + if (useCopy) + { + // assume that if useCopy is false the calling code has locked + // hiddenColumns + LOCK.readLock().lock(); + } + + if (hiddenColumns != null) + { + localHidden = new ArrayList<>(); + + // iterate until a region overlaps with [start,end] + int i = 0; + while ((i < hiddenColumns.size()) + && (hiddenColumns.get(i)[1] < start)) + { + i++; + } + + // iterate from start to end, adding each hidden region. Positions are + // absolute, and all regions which *overlap* [start,end] are added. + while (i < hiddenColumns.size() + && (hiddenColumns.get(i)[0] <= end)) + { + int[] rh; + int[] cp; + rh = hiddenColumns.get(i); + if (rh != null) + { + cp = new int[rh.length]; + System.arraycopy(rh, 0, cp, 0, rh.length); + localHidden.add(cp); + } + i++; + } + } + } + finally + { + if (useCopy) + { + LOCK.readLock().unlock(); + } + } + } + + @Override + public boolean hasNext() + { + return (localHidden != null) + && (currentPosition < localHidden.size()); + } + + @Override + public int[] next() + { + currentRegion = localHidden.get(currentPosition); + currentPosition++; + return currentRegion; + } + } + + class BoundedStartRegionIterator implements Iterator + { + + private int start; // start position to iterate from + + private int end; // end position to iterate to + + // current index in hiddenColumns + private int currentPosition = 0; + + // local copy or reference to hiddenColumns + private List positions = null; + + /** + * Construct an iterator over hiddenColums bounded at + * [lowerBound,upperBound] + * + * @param lowerBound + * lower bound to iterate from + * @param upperBound + * upper bound to iterate to + * @param useCopyCols + * whether to make a local copy of hiddenColumns for iteration (set + * to true if calling from outwith the HiddenColumns class) + */ + BoundedStartRegionIterator(int lowerBound, int upperBound, + boolean useCopy) + { + start = lowerBound; + end = upperBound; + + try + { + if (useCopy) + { + // assume that if useCopy is false the calling code has locked + // hiddenColumns + LOCK.readLock().lock(); + } + + if (hiddenColumns != null) + { + positions = new ArrayList<>(hiddenColumns.size()); + + // navigate to start, keeping count of hidden columns + int i = 0; + int hiddenSoFar = 0; + while ((i < hiddenColumns.size()) + && (hiddenColumns.get(i)[0] < start + hiddenSoFar)) + { + int[] region = hiddenColumns.get(i); + hiddenSoFar += region[1] - region[0] + 1; + i++; + } + + // iterate from start to end, adding start positions of each + // hidden region. Positions are visible columns count, not absolute + while (i < hiddenColumns.size() + && (hiddenColumns.get(i)[0] <= end + hiddenSoFar)) + { + int[] region = hiddenColumns.get(i); + positions.add(region[0] - hiddenSoFar); + hiddenSoFar += region[1] - region[0] + 1; + i++; + } + } + else + { + positions = new ArrayList<>(); + } + } finally + { + if (useCopy) + { + LOCK.readLock().unlock(); + } + } + } + + @Override + public boolean hasNext() + { + return (currentPosition < positions.size()); + } + + @Override + public Integer next() + { + int result = positions.get(currentPosition); + currentPosition++; + return result; + } + } } diff --git a/src/jalview/gui/ScalePanel.java b/src/jalview/gui/ScalePanel.java index 4e4db23..bf9ca8e 100755 --- a/src/jalview/gui/ScalePanel.java +++ b/src/jalview/gui/ScalePanel.java @@ -42,6 +42,7 @@ import java.awt.event.MouseEvent; import java.awt.event.MouseListener; import java.awt.event.MouseMotionListener; import java.beans.PropertyChangeEvent; +import java.util.Iterator; import java.util.List; import javax.swing.JMenuItem; @@ -487,19 +488,18 @@ public class ScalePanel extends JPanel if (av.getShowHiddenMarkers()) { - List positions = hidden.findHiddenRegionPositions(startx, - startx + widthx + 1); - for (int pos : positions) + Iterator it = hidden.getBoundedStartIterator(startx, + startx + widthx + 1, true); + while (it.hasNext()) { - res = pos - startx; + res = it.next() - startx; gg.fillPolygon( new int[] - { -1 + res * avCharWidth - avCharHeight / 4, - -1 + res * avCharWidth + avCharHeight / 4, - -1 + res * avCharWidth }, - new int[] - { y, y, y + 2 * yOf }, 3); + { -1 + res * avCharWidth - avCharHeight / 4, + -1 + res * avCharWidth + avCharHeight / 4, + -1 + res * avCharWidth }, new int[] + { y, y, y + 2 * yOf }, 3); } } } diff --git a/src/jalview/gui/SeqCanvas.java b/src/jalview/gui/SeqCanvas.java index 8af99b7..1df6ae3 100755 --- a/src/jalview/gui/SeqCanvas.java +++ b/src/jalview/gui/SeqCanvas.java @@ -41,7 +41,7 @@ import java.awt.RenderingHints; import java.awt.Shape; import java.awt.image.BufferedImage; import java.beans.PropertyChangeEvent; -import java.util.List; +import java.util.Iterator; import javax.swing.JComponent; @@ -696,21 +696,19 @@ public class SeqCanvas extends JComponent implements ViewportListenerI g.setColor(Color.blue); int res; HiddenColumns hidden = av.getAlignment().getHiddenColumns(); - List positions = hidden.findHiddenRegionPositions(startRes, - endx + 1); - for (int pos : positions) - { - res = pos - startRes; + Iterator it = hidden.getBoundedStartIterator(startRes, + endx + 1, true); + while (it.hasNext()) + { + res = it.next() - startRes; gg.fillPolygon( new int[] - { res * charWidth - charHeight / 4, - res * charWidth + charHeight / 4, res * charWidth }, + { res * charWidth - charHeight / 4, + res * charWidth + charHeight / 4, res * charWidth }, new int[] - { ypos - (charHeight / 2), ypos - (charHeight / 2), - ypos - (charHeight / 2) + 8 }, - 3); - + { ypos - (charHeight / 2), ypos - (charHeight / 2), + ypos - (charHeight / 2) + 8 }, 3); } } diff --git a/test/jalview/datamodel/HiddenColumnsTest.java b/test/jalview/datamodel/HiddenColumnsTest.java index af7ace7..295ad9f 100644 --- a/test/jalview/datamodel/HiddenColumnsTest.java +++ b/test/jalview/datamodel/HiddenColumnsTest.java @@ -32,6 +32,7 @@ import jalview.util.Comparison; import java.util.ArrayList; import java.util.Arrays; import java.util.BitSet; +import java.util.Iterator; import java.util.List; import java.util.Random; @@ -1293,7 +1294,107 @@ public class HiddenColumnsTest h.hideColumns(0, 30); result = h.subtractVisibleColumns(31, 0); assertEquals(-31, result); + } + @Test(groups = "Functional") + public void testBoundedIterator() + { + HiddenColumns h = new HiddenColumns(); + Iterator it = h.getBoundedIterator(0, 10, false); + + // no hidden columns = nothing to iterate over + assertFalse(it.hasNext()); + + // [start,end] contains all hidden columns + // all regions are returned + h.hideColumns(3, 10); + h.hideColumns(14, 16); + it = h.getBoundedIterator(0, 20, false); + assertTrue(it.hasNext()); + int[] next = it.next(); + assertEquals(3, next[0]); + assertEquals(10, next[1]); + next = it.next(); + assertEquals(14, next[0]); + assertEquals(16, next[1]); + assertFalse(it.hasNext()); + + // [start,end] overlaps a region + // 1 region returned + it = h.getBoundedIterator(5, 7, false); + assertTrue(it.hasNext()); + next = it.next(); + assertEquals(3, next[0]); + assertEquals(10, next[1]); + assertFalse(it.hasNext()); + + // [start,end] fully contains 1 region and start of last + // - 2 regions returned + it = h.getBoundedIterator(3, 15, false); + assertTrue(it.hasNext()); + next = it.next(); + assertEquals(3, next[0]); + assertEquals(10, next[1]); + next = it.next(); + assertEquals(14, next[0]); + assertEquals(16, next[1]); + assertFalse(it.hasNext()); + + // [start,end] contains end of first region and whole of last region + // - 2 regions returned + it = h.getBoundedIterator(4, 20, false); + assertTrue(it.hasNext()); + next = it.next(); + assertEquals(3, next[0]); + assertEquals(10, next[1]); + next = it.next(); + assertEquals(14, next[0]); + assertEquals(16, next[1]); + assertFalse(it.hasNext()); } + @Test(groups = "Functional") + public void testBoundedStartIterator() + { + HiddenColumns h = new HiddenColumns(); + Iterator it = h.getBoundedStartIterator(0, 10, false); + + // no hidden columns = nothing to iterate over + assertFalse(it.hasNext()); + + // [start,end] contains all hidden columns + // all regions are returned + h.hideColumns(3, 10); + h.hideColumns(14, 16); + it = h.getBoundedStartIterator(0, 20, false); + assertTrue(it.hasNext()); + int next = it.next(); + assertEquals(3, next); + next = it.next(); + assertEquals(6, next); + assertFalse(it.hasNext()); + + // [start,end] does not contain a start of a region + // no regions to iterate over + it = h.getBoundedStartIterator(4, 5, false); + assertFalse(it.hasNext()); + + // [start,end] fully contains 1 region and start of last + // - 2 regions returned + it = h.getBoundedStartIterator(3, 7, false); + assertTrue(it.hasNext()); + next = it.next(); + assertEquals(3, next); + next = it.next(); + assertEquals(6, next); + assertFalse(it.hasNext()); + + // [start,end] contains whole of last region + // - 1 region returned + it = h.getBoundedStartIterator(4, 20, false); + assertTrue(it.hasNext()); + next = it.next(); + assertEquals(6, next); + assertFalse(it.hasNext()); + } } -- 1.7.10.2