From f149fa7699eddc4968dc5a9fa35694abcc28b0cd Mon Sep 17 00:00:00 2001 From: kiramt Date: Mon, 20 Nov 2017 09:33:31 +0000 Subject: [PATCH] JAL-2759 improvements to speed up synchronisation; caching of size --- src/jalview/datamodel/HiddenColumns.java | 69 ++++++++++---- src/jalview/datamodel/HiddenColumnsCursor.java | 100 ++++++++++---------- src/jalview/datamodel/HiddenCursorPosition.java | 34 +++++++ src/jalview/datamodel/RegionsIterator.java | 4 +- .../jalview/datamodel/HiddenColumnsCursorTest.java | 45 ++++----- 5 files changed, 163 insertions(+), 89 deletions(-) create mode 100644 src/jalview/datamodel/HiddenCursorPosition.java diff --git a/src/jalview/datamodel/HiddenColumns.java b/src/jalview/datamodel/HiddenColumns.java index 69d2ac4..0a4d04b 100644 --- a/src/jalview/datamodel/HiddenColumns.java +++ b/src/jalview/datamodel/HiddenColumns.java @@ -34,6 +34,8 @@ public class HiddenColumns private HiddenColumnsCursor cursor = new HiddenColumnsCursor(); + private int numColumns = 0; + /* * list of hidden column [start, end] ranges; the list is maintained in * ascending start column order @@ -99,6 +101,7 @@ public class HiddenColumns if (copy != null) { hiddenColumns = new ArrayList<>(); + numColumns = 0; Iterator it = copy.getBoundedIterator(start, end); while (it.hasNext()) { @@ -110,6 +113,7 @@ public class HiddenColumns hiddenColumns.add( new int[] { region[0] - offset, region[1] - offset }); + numColumns += region[1] - region[0] + 1; } } cursor.resetCursor(hiddenColumns); @@ -167,17 +171,24 @@ public class HiddenColumns try { LOCK.readLock().lock(); - int size = 0; - if (hiddenColumns != null) + + if (numColumns == 0 && hiddenColumns != null) { - Iterator it = hiddenColumns.iterator(); - while (it.hasNext()) + // numColumns is out of date, so recalculate + int size = 0; + if (hiddenColumns != null) { - int[] range = it.next(); - size += range[1] - range[0] + 1; + Iterator it = hiddenColumns.iterator(); + while (it.hasNext()) + { + int[] range = it.next(); + size += range[1] - range[0] + 1; + } } + numColumns = size; } - return size; + + return numColumns; } finally { LOCK.readLock().unlock(); @@ -266,7 +277,7 @@ public class HiddenColumns if (hiddenColumns != null) { - result += cursor.getHiddenOffset(column); + result += cursor.getHiddenOffset(column).getHiddenSoFar(); } return result; @@ -294,8 +305,10 @@ public class HiddenColumns if (hiddenColumns != null) { - int index = cursor.findRegionForColumn(hiddenColumn); - int hiddenBeforeCol = cursor.getHiddenSoFar(); + HiddenCursorPosition cursorPos = cursor + .findRegionForColumn(hiddenColumn); + int index = cursorPos.getRegionIndex(); + int hiddenBeforeCol = cursorPos.getHiddenSoFar(); // just subtract hidden cols count - this works fine if column is // visible @@ -397,7 +410,7 @@ public class HiddenColumns LOCK.readLock().lock(); if (hiddenColumns != null) { - int index = cursor.findRegionForColumn(alPos); + int index = cursor.findRegionForColumn(alPos).getRegionIndex(); if (index < hiddenColumns.size()) { int[] region = hiddenColumns.get(index); @@ -438,7 +451,7 @@ public class HiddenColumns if (hiddenColumns != null) { - int index = cursor.findRegionForColumn(alPos); + int index = cursor.findRegionForColumn(alPos).getRegionIndex(); if (index > 0) { @@ -505,6 +518,9 @@ public class HiddenColumns if (!wasAlreadyLocked) { cursor.resetCursor(hiddenColumns); + + // reset the number of columns so they will be recounted + numColumns = 0; } } finally { @@ -593,7 +609,7 @@ public class HiddenColumns { LOCK.readLock().lock(); - int regionindex = cursor.findRegionForColumn(column); + int regionindex = cursor.findRegionForColumn(column).getRegionIndex(); if (regionindex > -1 && regionindex < hiddenColumns.size()) { int[] region = hiddenColumns.get(regionindex); @@ -897,6 +913,7 @@ public class HiddenColumns hideColumns(r[0], r[1]); } cursor.resetCursor(hiddenColumns); + numColumns = 0; } finally { LOCK.writeLock().unlock(); @@ -924,6 +941,7 @@ public class HiddenColumns } hiddenColumns = null; cursor.resetCursor(hiddenColumns); + numColumns = 0; } } finally { @@ -945,7 +963,8 @@ public class HiddenColumns if (hiddenColumns != null) { - int regionIndex = cursor.findRegionForColumn(start); + int regionIndex = cursor.findRegionForColumn(start) + .getRegionIndex(); if (regionIndex != -1 && regionIndex != hiddenColumns.size()) { @@ -958,13 +977,20 @@ public class HiddenColumns { sel.addElement(j); } + int colsToRemove = region[1] - region[0] + 1; hiddenColumns.remove(regionIndex); if (hiddenColumns.isEmpty()) { hiddenColumns = null; + numColumns = 0; + } + else + { + numColumns -= colsToRemove; } cursor.updateForDeletedRegion(hiddenColumns); + } } } @@ -1073,6 +1099,7 @@ public class HiddenColumns } hiddenColumns = newhidden; cursor.resetCursor(hiddenColumns); + numColumns = 0; } finally { LOCK.writeLock().unlock(); @@ -1177,6 +1204,7 @@ public class HiddenColumns hideColumns(firstSet, lastSet - 1); } cursor.resetCursor(hiddenColumns); + numColumns = 0; } finally { LOCK.writeLock().unlock(); @@ -1283,15 +1311,24 @@ public class HiddenColumns if (hiddenColumns != null) { - int regionindex = cursor.findRegionForColumn(adjres - 1); + // look for a region ending just before adjres + int regionindex = cursor.findRegionForColumn(adjres - 1) + .getRegionIndex(); if (regionindex < hiddenColumns.size() && hiddenColumns.get(regionindex)[1] == adjres - 1) { reveal = hiddenColumns.get(regionindex); } + // check if the region ends just after adjres + else if (regionindex < hiddenColumns.size() + && hiddenColumns.get(regionindex)[0] == adjres + 1) + { + reveal = hiddenColumns.get(regionindex); + } + // or try the next region else { - regionindex = cursor.findRegionForColumn(adjres + 1); + regionindex++; if (regionindex < hiddenColumns.size() && hiddenColumns.get(regionindex)[0] == adjres + 1) { diff --git a/src/jalview/datamodel/HiddenColumnsCursor.java b/src/jalview/datamodel/HiddenColumnsCursor.java index 9d1351e..3284504 100644 --- a/src/jalview/datamodel/HiddenColumnsCursor.java +++ b/src/jalview/datamodel/HiddenColumnsCursor.java @@ -21,47 +21,53 @@ package jalview.datamodel; import java.util.List; +import java.util.concurrent.atomic.AtomicReference; public class HiddenColumnsCursor { // absolute position of first hidden column private int firstColumn; - // index of last visited region - private int regionIndex; - - // number of hidden columns before last visited region - private int hiddenSoFar; - private List hiddenColumns; + // AtomicReference to hold the current region index and hidden column count + // Could be done with synchronisation but benchmarking shows this way is 2x + // faster + private final AtomicReference cursorPos = new AtomicReference<>( + new HiddenCursorPosition(0, 0, 0)); + protected HiddenColumnsCursor() { } /** - * Set the cursor to a position + * Reset the cursor with a new hidden columns collection. Calls to resetCursor + * should be made from within a writeLock in the HiddenColumns class - since + * changes to the hiddenColumns collection require a writeLock the lock should + * already exist. * * @param hiddenCols */ protected void resetCursor(List hiddenCols) { - synchronized (this) + hiddenColumns = hiddenCols; + if ((hiddenCols != null) && (!hiddenCols.isEmpty())) { - hiddenColumns = hiddenCols; - if ((hiddenCols != null) && (!hiddenCols.isEmpty())) - { - firstColumn = hiddenColumns.get(0)[0]; - regionIndex = 0; - hiddenSoFar = 0; - } + firstColumn = hiddenColumns.get(0)[0]; + HiddenCursorPosition oldpos = cursorPos.get(); + HiddenCursorPosition newpos = new HiddenCursorPosition(0, 0, 0); + cursorPos.compareAndSet(oldpos, newpos); } } /** * Delete the region the cursor is currently at. Avoids having to reset the * cursor just because we deleted a region. + * + * Calls to updateForDeletedRegion should be made from within a writeLock in + * the HiddenColumns class - since changes to the hiddenColumns collection + * require a writeLock the lock should already exist. * * @param hiddenCols */ @@ -74,36 +80,23 @@ public class HiddenColumnsCursor // nothing changes; otherwise // we deleted the last region (index=hiddenCols.size()-1) // or the index was at the end of the alignment (index=hiddenCols.size()) - if (regionIndex >= hiddenColumns.size() - 1) + HiddenCursorPosition oldpos = cursorPos.get(); + + int index = oldpos.getRegionIndex(); + if (index >= hiddenColumns.size() - 1) { // deleted last region, index is now end of alignment - regionIndex = hiddenCols.size(); + index = hiddenCols.size(); } - } - - hiddenColumns = hiddenCols; - } - protected void updateCursor(int index, int hiddenCount) - { - synchronized (this) - { - regionIndex = index; - hiddenSoFar = hiddenCount; + // update the cursor position + HiddenCursorPosition newpos = new HiddenCursorPosition(index, + oldpos.getHiddenSoFar(), oldpos.getNumColumns()); + cursorPos.compareAndSet(oldpos, newpos); } + hiddenColumns = hiddenCols; } - protected synchronized int getIndex() - { - return regionIndex; - } - - protected synchronized int getHiddenSoFar() - { - return hiddenSoFar; - } - - /** * Get the index of the region that column is within (if column is hidden) or * which is to the right of column (if column is visible). If no hidden @@ -114,15 +107,16 @@ public class HiddenColumnsCursor * absolute position of a column in the alignment * @return region index */ - protected int findRegionForColumn(int column) + protected HiddenCursorPosition findRegionForColumn(int column) { if (hiddenColumns == null) { - return -1; + return null; } - int index = regionIndex; - int hiddenCount = hiddenSoFar; + HiddenCursorPosition oldpos = cursorPos.get(); + int index = oldpos.getRegionIndex(); + int hiddenCount = oldpos.getHiddenSoFar(); if (index == hiddenColumns.size()) { @@ -175,8 +169,10 @@ public class HiddenColumnsCursor } } } - updateCursor(index, hiddenCount); - return index; + HiddenCursorPosition newpos = new HiddenCursorPosition(index, + hiddenCount, oldpos.getNumColumns()); + cursorPos.compareAndSet(oldpos, newpos); + return newpos; } /** @@ -187,15 +183,16 @@ public class HiddenColumnsCursor * index of column in visible alignment * @return */ - protected int getHiddenOffset(int column) + protected HiddenCursorPosition getHiddenOffset(int column) { if (hiddenColumns == null) { - return -1; + return null; } - int index = getIndex(); - int hiddenCount = getHiddenSoFar(); + HiddenCursorPosition oldpos = cursorPos.get(); + int index = oldpos.getRegionIndex(); + int hiddenCount = oldpos.getHiddenSoFar(); if (column < firstColumn) { @@ -226,7 +223,10 @@ public class HiddenColumnsCursor } } - updateCursor(index, hiddenCount); - return hiddenCount; + + HiddenCursorPosition newpos = new HiddenCursorPosition(index, + hiddenCount, oldpos.getNumColumns()); + cursorPos.compareAndSet(oldpos, newpos); + return newpos; } } diff --git a/src/jalview/datamodel/HiddenCursorPosition.java b/src/jalview/datamodel/HiddenCursorPosition.java new file mode 100644 index 0000000..606a7c5 --- /dev/null +++ b/src/jalview/datamodel/HiddenCursorPosition.java @@ -0,0 +1,34 @@ +package jalview.datamodel; + +public class HiddenCursorPosition +{ + // index of last visited region + private int regionIndex; + + // number of hidden columns before last visited region + private int hiddenSoFar; + + private int numColumns; + + public HiddenCursorPosition(int index, int hiddencount, int colscount) + { + regionIndex = index; + hiddenSoFar = hiddencount; + numColumns = colscount; + } + + public int getRegionIndex() + { + return regionIndex; + } + + public int getHiddenSoFar() + { + return hiddenSoFar; + } + + public int getNumColumns() + { + return numColumns; + } +} diff --git a/src/jalview/datamodel/RegionsIterator.java b/src/jalview/datamodel/RegionsIterator.java index bafc288..7eb5ff8 100644 --- a/src/jalview/datamodel/RegionsIterator.java +++ b/src/jalview/datamodel/RegionsIterator.java @@ -39,7 +39,9 @@ public class RegionsIterator implements Iterator if (hiddenColumns != null) { - currentPosition = cursor.findRegionForColumn(start); + // TODO remove whole class? + // commented out to compile + // currentPosition = cursor.findRegionForColumn(start); if (currentPosition < hiddenColumns.size()) { diff --git a/test/jalview/datamodel/HiddenColumnsCursorTest.java b/test/jalview/datamodel/HiddenColumnsCursorTest.java index cc8e5e5..8666bbc 100644 --- a/test/jalview/datamodel/HiddenColumnsCursorTest.java +++ b/test/jalview/datamodel/HiddenColumnsCursorTest.java @@ -20,6 +20,7 @@ */ package jalview.datamodel; +import static org.testng.Assert.assertNull; import static org.testng.AssertJUnit.assertEquals; import java.util.ArrayList; @@ -37,51 +38,51 @@ public class HiddenColumnsCursorTest { HiddenColumnsCursor cursor = new HiddenColumnsCursor(); - int regionIndex = cursor.findRegionForColumn(20); - assertEquals(-1, regionIndex); + HiddenCursorPosition pos = cursor.findRegionForColumn(20); + assertNull(pos); List hidden = new ArrayList<>(); hidden.add(new int[] { 53, 76 }); hidden.add(new int[] { 104, 125 }); cursor.resetCursor(hidden); - regionIndex = cursor.findRegionForColumn(126); + int regionIndex = cursor.findRegionForColumn(126).getRegionIndex(); assertEquals(2, regionIndex); - regionIndex = cursor.findRegionForColumn(125); + regionIndex = cursor.findRegionForColumn(125).getRegionIndex(); assertEquals(1, regionIndex); - regionIndex = cursor.findRegionForColumn(108); + regionIndex = cursor.findRegionForColumn(108).getRegionIndex(); assertEquals(1, regionIndex); - regionIndex = cursor.findRegionForColumn(104); + regionIndex = cursor.findRegionForColumn(104).getRegionIndex(); assertEquals(1, regionIndex); - regionIndex = cursor.findRegionForColumn(103); + regionIndex = cursor.findRegionForColumn(103).getRegionIndex(); assertEquals(1, regionIndex); - regionIndex = cursor.findRegionForColumn(77); + regionIndex = cursor.findRegionForColumn(77).getRegionIndex(); assertEquals(1, regionIndex); - regionIndex = cursor.findRegionForColumn(76); + regionIndex = cursor.findRegionForColumn(76).getRegionIndex(); assertEquals(0, regionIndex); - regionIndex = cursor.findRegionForColumn(53); + regionIndex = cursor.findRegionForColumn(53).getRegionIndex(); assertEquals(0, regionIndex); - regionIndex = cursor.findRegionForColumn(52); + regionIndex = cursor.findRegionForColumn(52).getRegionIndex(); assertEquals(0, regionIndex); - regionIndex = cursor.findRegionForColumn(0); + regionIndex = cursor.findRegionForColumn(0).getRegionIndex(); assertEquals(0, regionIndex); hidden.add(new int[] { 138, 155 }); cursor.resetCursor(hidden); - regionIndex = cursor.findRegionForColumn(160); + regionIndex = cursor.findRegionForColumn(160).getRegionIndex(); assertEquals(3, regionIndex); - regionIndex = cursor.findRegionForColumn(100); + regionIndex = cursor.findRegionForColumn(100).getRegionIndex(); assertEquals(1, regionIndex); } @@ -93,30 +94,30 @@ public class HiddenColumnsCursorTest { HiddenColumnsCursor cursor = new HiddenColumnsCursor(); - int offset = cursor.getHiddenOffset(20); - assertEquals(-1, offset); + HiddenCursorPosition pos = cursor.getHiddenOffset(20); + assertNull(pos); List hidden = new ArrayList<>(); hidden.add(new int[] { 53, 76 }); hidden.add(new int[] { 104, 125 }); cursor.resetCursor(hidden); - offset = cursor.getHiddenOffset(80); + int offset = cursor.getHiddenOffset(80).getHiddenSoFar(); assertEquals(46, offset); - offset = cursor.getHiddenOffset(79); + offset = cursor.getHiddenOffset(79).getHiddenSoFar(); assertEquals(24, offset); - offset = cursor.getHiddenOffset(53); + offset = cursor.getHiddenOffset(53).getHiddenSoFar(); assertEquals(24, offset); - offset = cursor.getHiddenOffset(52); + offset = cursor.getHiddenOffset(52).getHiddenSoFar(); assertEquals(0, offset); - offset = cursor.getHiddenOffset(10); + offset = cursor.getHiddenOffset(10).getHiddenSoFar(); assertEquals(0, offset); - offset = cursor.getHiddenOffset(0); + offset = cursor.getHiddenOffset(0).getHiddenSoFar(); assertEquals(0, offset); } -- 1.7.10.2