Attachment 286363 Details for Bug 572512 – dominator_tree.patch

[patch] dominator_tree.patch

dominator_tree.patch (text/plain), 17.95 KB, created by Jason Koch

on 2021-05-11 09:12:00 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Jason Koch

Created: 2021-05-11 09:12:00 EDT

Size: 17.95 KB

patch

obsolete

>diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/HeapIntArray.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/HeapIntArray.java
>new file mode 100644
>index 00000000..2d35b987
>--- /dev/null
>+++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/HeapIntArray.java
>@@ -0,0 +1,25 @@
>+package org.eclipse.mat.parser.index;
>+
>+public class HeapIntArray implements IntArray
>+{
>+    final int[] array;
>+    public HeapIntArray(int size)
>+    {
>+        this.array = new int[size];
>+    }
>+
>+    public int get(int index)
>+    {
>+        return array[index];
>+    }
>+
>+    public void set(int index, int value)
>+    {
>+        array[index] = value;
>+    }
>+
>+    public int size()
>+    {
>+        return array.length;
>+    }
>+}
>\ No newline at end of file
>diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/HeapLongArray.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/HeapLongArray.java
>new file mode 100644
>index 00000000..2227f2c7
>--- /dev/null
>+++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/HeapLongArray.java
>@@ -0,0 +1,25 @@
>+package org.eclipse.mat.parser.index;
>+
>+public class HeapLongArray implements LongArray
>+{
>+    final long[] array;
>+    public HeapLongArray(int size)
>+    {
>+        this.array = new long[size];
>+    }
>+
>+    public long get(int index)
>+    {
>+        return array[index];
>+    }
>+
>+    public void set(int index, long value)
>+    {
>+        array[index] = value;
>+    }
>+
>+    public int size()
>+    {
>+        return array.length;
>+    }
>+}
>\ No newline at end of file
>diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IntArray.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IntArray.java
>index f6b9e726..47c6404b 100644
>--- a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IntArray.java
>+++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IntArray.java
>@@ -12,6 +12,29 @@ public interface IntArray
> 
>     public int size();
> 
>+    public default IteratorInt iterator() {
>+        return new IntArrayIterator(this);
>+    }
>+
>+    // from JDK code
>+    public default int binarySearch(int element) {
>+        int low = 0;
>+        int high = this.size() - 1;
>+
>+        while (low <= high) {
>+            int mid = (low + high) >>> 1;
>+            int midVal = this.get(mid);
>+
>+            if (midVal < element)
>+                low = mid + 1;
>+            else if (midVal > element)
>+                high = mid - 1;
>+            else
>+                return mid;
>+        }
>+        return -(low + 1);
>+    }
>+
>     static class IntArrayIterator implements IteratorInt
>     {
>         final IntArray array;
>@@ -122,4 +145,4 @@ public interface IntArray
>             array.set(j, temp);
>         }
>     }
>-}
>\ No newline at end of file
>+}
>diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/LongArray.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/LongArray.java
>index 5e32cf65..064c1496 100644
>--- a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/LongArray.java
>+++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/LongArray.java
>@@ -12,6 +12,29 @@ public interface LongArray
> 
>     public int size();
> 
>+    public default IteratorLong iterator() {
>+        return new LongArrayIterator(this);
>+    }
>+
>+    // from JDK code
>+    public default int binarySearch(long element) {
>+        int low = 0;
>+        int high = this.size() - 1;
>+
>+        while (low <= high) {
>+            int mid = (low + high) >>> 1;
>+            long midVal = this.get(mid);
>+
>+            if (midVal < element)
>+                low = mid + 1;
>+            else if (midVal > element)
>+                high = mid - 1;
>+            else
>+                return mid;
>+        }
>+        return -(low + 1);
>+    }
>+
>     static class LongArrayIterator implements IteratorLong
>     {
>         final LongArray array;
>@@ -122,4 +145,4 @@ public interface LongArray
>             array.set(j, temp);
>         }
>     }
>-}
>\ No newline at end of file
>+}
>diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedIntArray.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedIntArray.java
>index 86330e1f..f52fcb2e 100644
>--- a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedIntArray.java
>+++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedIntArray.java
>@@ -63,10 +63,6 @@ public class MemoryMappedIntArray extends MemoryMappedArraySupport<IntBuffer> im
>         new IntArray.IntArraySortTask(this, 0, size() - 1).invoke();
>     }
> 
>-    public IteratorInt iterator() {
>-        return new IntArray.IntArrayIterator(this);
>-    }
>-
>     public int[] getAll(int[] indices) {
>         int[] answers = new int[indices.length];
>         for(int i = 0; i < indices.length; i++)
>@@ -80,4 +76,4 @@ public class MemoryMappedIntArray extends MemoryMappedArraySupport<IntBuffer> im
>         checkExists(index);
>         buffers[bufferNumber(index)].put(offsetIntoBuffer(index), value);
>     }
>-}
>\ No newline at end of file
>+}
>diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedLongArray.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedLongArray.java
>index d16db471..e02c317d 100644
>--- a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedLongArray.java
>+++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedLongArray.java
>@@ -61,10 +61,6 @@ public class MemoryMappedLongArray extends MemoryMappedArraySupport<LongBuffer>
>         new LongArray.LongArraySortTask(this, 0, size() - 1).invoke();
>     }
> 
>-    public IteratorLong iterator() {
>-        return new LongArray.LongArrayIterator(this);
>-    }
>-
>     public long[] getAll(int[] indices) {
>         long[] answers = new long[indices.length];
>         for(int i = 0; i < indices.length; i++)
>@@ -78,4 +74,4 @@ public class MemoryMappedLongArray extends MemoryMappedArraySupport<LongBuffer>
>         checkExists(index);
>         buffers[bufferNumber(index)].put(offsetIntoBuffer(index), value);
>     }
>-}
>\ No newline at end of file
>+}
>diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/internal/DominatorTree.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/internal/DominatorTree.java
>index cd764e9b..b17c66de 100644
>--- a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/internal/DominatorTree.java
>+++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/internal/DominatorTree.java
>@@ -3,8 +3,8 @@
>  * All rights reserved. This program and the accompanying materials
>  * are made available under the terms of the Eclipse Public License 2.0
>  * which accompanies this distribution, and is available at
>- * https://www.eclipse.org/legal/epl-2.0/
>- *
>+ * https://www.eclipse.org/legal/epl-2.0/
>+ *
>  * SPDX-License-Identifier: EPL-2.0
>  *
>  * Contributors:
>@@ -25,6 +25,11 @@ import org.eclipse.mat.parser.index.IIndexReader;
> import org.eclipse.mat.parser.index.IndexManager;
> import org.eclipse.mat.parser.index.IndexWriter;
> import org.eclipse.mat.parser.index.IndexManager.Index;
>+import org.eclipse.mat.parser.index.HeapIntArray;
>+import org.eclipse.mat.parser.index.MemoryMappedIntArray;
>+import org.eclipse.mat.parser.index.MemoryMappedLongArray;
>+import org.eclipse.mat.parser.index.IntArray;
>+import org.eclipse.mat.parser.index.LongArray;
> import org.eclipse.mat.parser.internal.util.IntStack;
> import org.eclipse.mat.util.IProgressListener;
> import org.eclipse.mat.util.SimpleMonitor;
>@@ -48,14 +53,14 @@ public class DominatorTree
>         int[] gcRootsArray;
>         private BitField gcRootsSet;
> 
>-        int[] bucket;
>+        IntArray bucket;
>         private int r, n;
>         private int[] dom;
>-        private int[] parent;
>-        private int[] anchestor;
>-        private int[] vertex;
>-        private int[] label;
>-        private int[] semi;
>+        private IntArray parent;
>+        private IntArray anchestor;
>+        private IntArray vertex;
>+        private IntArray label;
>+        private IntArray semi;
> 
>         private static int ROOT_VALUE = -1;
>         private static int[] ROOT_VALUE_ARR = new int[] { ROOT_VALUE };
>@@ -90,18 +95,23 @@ public class DominatorTree
>             n = snapshot.getSnapshotInfo().getNumberOfObjects() + 1;
>             r = 1;
> 
>-            parent = new int[n + 1];
>-            anchestor = new int[n + 1];
>-            vertex = new int[n + 1];
>-            label = new int[n + 1];
>-            semi = new int[n + 1];
>+            // parent = new HeapIntArray(n + 1);
>+            // anchestor = new HeapIntArray(n + 1);
>+            // vertex = new HeapIntArray(n + 1);
>+            // label = new HeapIntArray(n + 1);
>+            // semi = new HeapIntArray(n + 1);
>+            parent = new MemoryMappedIntArray(null, n + 1, n + 1);
>+            anchestor = new MemoryMappedIntArray(null, n + 1, n + 1);
>+            vertex = new MemoryMappedIntArray(null, n + 1, n + 1);
>+            label = new MemoryMappedIntArray(null, n + 1, n + 1);
>+            semi = new MemoryMappedIntArray(null, n + 1, n + 1);
> 
>             /*
>              * Allocate these up front, to check for early OOM, but then free
>              * so that dfs() can use the space for outbound index caching.  
>              */
>             dom = new int[n + 1];
>-            bucket = new int[n + 1];
>+            bucket = new HeapIntArray(n + 1);
>             dom = null;
>             bucket = null;
>         }
>@@ -123,46 +133,49 @@ public class DominatorTree
>              * Reallocate just before use. 
>              */
>             dom = new int[snapshot.getSnapshotInfo().getNumberOfObjects() + 2];
>-            bucket = new int[snapshot.getSnapshotInfo().getNumberOfObjects() + 2];
>+            // bucket = new HeapIntArray(snapshot.getSnapshotInfo().getNumberOfObjects() + 2);
>+            bucket = new MemoryMappedIntArray(null, snapshot.getSnapshotInfo().getNumberOfObjects() + 2, snapshot.getSnapshotInfo().getNumberOfObjects() + 2);
> 
>-            Arrays.fill(bucket, -1);
>+            for(int i = 0; i < bucket.size(); i++) {
>+                bucket.set(i, -1);
>+            }
> 
>             for (int i = n; i >= 2; i--)
>             {
>-                int w = vertex[i];
>+                int w = vertex.get(i);
>                 for (int v : getPredecessors(w))
>                 {
>                     v += 2;
>                     if (v < 0)
>                         continue;
>                     int u = eval(v);
>-                    if (semi[u] < semi[w])
>+                    if (semi.get(u) < semi.get(w))
>                     {
>-                        semi[w] = semi[u];
>+                        semi.set(w, semi.get(u));
>                     }
>                 }
>                 // add w to bucket(vertex(semi(w)))
>                 // create the bucket if needed
>-                bucket[w] = bucket[vertex[semi[w]]]; // serves as next(w)
>-                bucket[vertex[semi[w]]] = w; // serves as
>+                bucket.set(w, bucket.get(vertex.get(semi.get(w)))); // serves as next(w)
>+                bucket.set(vertex.get(semi.get(w)), w); // serves as
>                 // first(vertex[semi[w]])
>-                link(parent[w], w);
>+                link(parent.get(w), w);
> 
>-                int v = bucket[parent[w]];
>+                int v = bucket.get(parent.get(w));
>                 while (v != -1)
>                 {
>                     int u = eval(v);
>-                    if (semi[u] < semi[v])
>+                    if (semi.get(u) < semi.get(v))
>                     {
>                         dom[v] = u;
>                     }
>                     else
>                     {
>-                        dom[v] = parent[w];
>+                        dom[v] = parent.get(w);
>                     }
>-                    v = bucket[v]; // here bucket serves as next[]
>+                    v = bucket.get(v); // here bucket serves as next[]
>                 }
>-                bucket[parent[w]] = -1;
>+                bucket.set(parent.get(w), -1);
>                 // }
>                 if (i % 1000 == 0)
>                 {
>@@ -174,8 +187,8 @@ public class DominatorTree
> 
>             for (int i = 2; i <= n; i++)
>             {
>-                int w = vertex[i];
>-                if (dom[w] != vertex[semi[w]])
>+                int w = vertex.get(i);
>+                if (dom[w] != vertex.get(semi.get(w)))
>                 {
>                     dom[w] = dom[dom[w]];
>                 }
>@@ -184,7 +197,12 @@ public class DominatorTree
> 
>             progressListener.done();
> 
>-            parent = anchestor = vertex = label = semi = bucket = null;
>+            bucket = null;
>+            parent = null;
>+            anchestor = null;
>+            vertex = null;
>+            label = null;
>+            semi = null;
>             inboundIndex.unload();
> 
>             if (progressListener0.isCanceled())
>@@ -265,13 +283,13 @@ public class DominatorTree
>                 successors = (int[]) successorsStack[size - 1];
>                 currentSuccessor = currentSuccessorStack[size - 1];
> 
>-                if (semi[v] == 0)
>+                if (semi.get(v) == 0)
>                 {
>                     n = n + 1;
>-                    semi[v] = n;
>-                    vertex[n] = v;
>-                    label[v] = v;
>-                    anchestor[v] = 0;
>+                    semi.set(v, n);
>+                    vertex.set(n, v);
>+                    label.set(v, v);
>+                    anchestor.set(v, 0);
>                 }
> 
>                 if (currentSuccessor < successors.length)
>@@ -282,9 +300,9 @@ public class DominatorTree
>                     // value
> 
>                     // push the next unvisited successor
>-                    if (semi[w] == 0)
>+                    if (semi.get(w) == 0)
>                     {
>-                        parent[w] = v;
>+                        parent.set(w, v);
>                         successors = outboundIndex.get(w - 2); // get the
>                         // successors of w
> 
>@@ -355,40 +373,40 @@ public class DominatorTree
>         private void compress(int v)
>         {
>             IntStack stack = new IntStack();
>-            while (anchestor[anchestor[v]] != 0) // is ancestor[v] a root in
>+            while (anchestor.get(anchestor.get(v)) != 0) // is ancestor[v] a root in
>             // the
>             // forest?
>             {
>                 stack.push(v);
>-                v = anchestor[v];
>+                v = anchestor.get(v);
>             }
>             while (stack.size() > 0)
>             {
>                 v = stack.pop();
>-                if (semi[label[anchestor[v]]] < semi[label[v]])
>+                if (semi.get(label.get(anchestor.get(v))) < semi.get(label.get(v)))
>                 {
>-                    label[v] = label[anchestor[v]];
>+                    label.set(v, label.get(anchestor.get(v)));
>                 }
>-                anchestor[v] = anchestor[anchestor[v]];
>+                anchestor.set(v, anchestor.get(anchestor.get(v)));
>             }
>         }
> 
>         private int eval(int v)
>         {
>-            if (anchestor[v] == 0)
>+            if (anchestor.get(v) == 0)
>             {
>                 return v;
>             }
>             else
>             {
>                 compress(v);
>-                return label[v];
>+                return label.get(v);
>             }
>         }
> 
>         private void link(int v, int w)
>         {
>-            anchestor[w] = v;
>+            anchestor.set(w, v);
>         }
> 
>         private void writeIndexFiles(FlatDominatorTree tree) throws IOException
>@@ -428,7 +446,7 @@ public class DominatorTree
> 
>             int[] dom;
>             int[] elements;
>-            long[] ts;
>+            LongArray ts;
>             SnapshotImpl dump;
> 
>             // temp arrays to pass for the radix sort
>@@ -441,7 +459,7 @@ public class DominatorTree
>                 this.dump = dump;
>                 this.dom = dom;
>                 this.elements = elements;
>-                this.ts = new long[dom.length];
>+                this.ts = new MemoryMappedLongArray(null, dom.length, dom.length);
>                 calculateTotalSizesIterative(root);
> 
>             }
>@@ -483,7 +501,7 @@ public class DominatorTree
>                 long[] totalSizes = new long[length];
>                 for (int i = 0; i < length; i++)
>                 {
>-                    totalSizes[i] = ts[objectIds[i] + 2];
>+                    totalSizes[i] = ts.get(objectIds[i] + 2);
>                 }
> 
>                 // sort both arrays according to the total sizes
>@@ -567,7 +585,7 @@ public class DominatorTree
>                         int nextChild = currentSucc.nextElement();
>                         currentSucc = getSuccessorsEnum(nextChild);
> 
>-                        ts[nextChild + 2] = nextChild < 0 ? 0 : snapshot.getHeapSize(nextChild);
>+                        ts.set(nextChild + 2, (nextChild < 0 ? 0 : snapshot.getHeapSize(nextChild)));
> 
>                         if (size == capacity)
>                         {
>@@ -590,12 +608,13 @@ public class DominatorTree
>                     {
>                         size--;
> 
>-                        if (size > 0)
>-                            ts[stack[size - 1] + 2] += ts[currentEntry + 2];
>+                        if (size > 0) {
>+                            ts.set(stack[size - 1] + 2, ts.get(stack[size - 1] + 2) + ts.get(currentEntry + 2));
>+                        }
> 
>                         if (currentEntry >= 0)
>                         {
>-                            retained.set(currentEntry, ts[currentEntry + 2]);
>+                            retained.set(currentEntry, ts.get(currentEntry + 2));
>                             if (++counter % 1000 == 0)
>                             {
>                                 if (progressListener.isCanceled())

Actions: View | Diff

Attachments on bug 572512: 286016 | 286362 | 286363 | 286508 | 286509 | 286510