Attachment 285606 Details for Bug 571331 – Identifier Index patch

[patch] Identifier Index patch

571331_pass1_heap.patch (text/plain), 7.13 KB, created by Jason Koch

on 2021-02-19 04:11:01 EST

(hide)

Description:

Filename:

MIME Type:

Creator: Jason Koch

Created: 2021-02-19 04:11:01 EST

Size: 7.13 KB

patch

obsolete

>diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IndexWriter.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IndexWriter.java
>index a7d9d1da..d5411494 100644
>--- a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IndexWriter.java
>+++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IndexWriter.java
>@@ -32,6 +32,7 @@ import java.util.concurrent.ExecutionException;
> import java.util.concurrent.ExecutorService;
> import java.util.concurrent.Executors;
> import java.util.concurrent.Future;
>+import java.util.concurrent.RecursiveAction;
> import java.util.concurrent.TimeUnit;
> import java.util.function.Supplier;
> 
>@@ -82,35 +83,133 @@ public abstract class IndexWriter
> 
>     public static class Identifier implements IIndexReader.IOne2LongIndex
>     {
>-        long[] identifiers;
>+        private static final int SUBARRAY_SIZE = 4 * 1024 * 1024; // 8 bytes, 32MB chunks
>+        private static final int SUBARRAY_SHIFT = 22;
>+        private static final int SUBARRAY_MASK = 0b00111111_11111111_11111111;
>+        long[][] identifiers = new long[][] { new long[SUBARRAY_SIZE] };
>         int size;
> 
>-        public void add(long id)
>+        int findSubarrayForIndex(int index)
>         {
>-            if (identifiers == null)
>+            int array = index >> SUBARRAY_SHIFT;
>+            if (array >= identifiers.length)
>             {
>-                identifiers = new long[10000];
>-                size = 0;
>+                long[][] newIdentifiers = new long[identifiers.length * 2][];
>+                System.arraycopy(identifiers, 0, newIdentifiers, 0, identifiers.length);
>+                identifiers = newIdentifiers;
>             }
>-
>-            if (size + 1 > identifiers.length)
>+            if (identifiers[array] == null)
>             {
>-                int minCapacity = size + 1;
>-                int newCapacity = newCapacity(identifiers.length, minCapacity);
>-                if (newCapacity < minCapacity)
>+                identifiers[array] = new long[SUBARRAY_SIZE];
>+                long totalBytes = 0;
>+                for (long[] subarray : identifiers)
>                 {
>-                    // Avoid strange exceptions later
>-                    throw new OutOfMemoryError(MessageUtil.format(Messages.IndexWriter_Error_ArrayLength, minCapacity, newCapacity));
>+                    if (subarray == null)
>+                        continue;
>+                    totalBytes += subarray.length * 8L;
>                 }
>-                identifiers = copyOf(identifiers, newCapacity);
>             }
>+            return array;
>+        }
> 
>-            identifiers[size++] = id;
>+        int findIndexIntoSubarray(int index)
>+        {
>+            return index & SUBARRAY_MASK;
>+        }
>+
>+        public void add(long id)
>+        {
>+            int sub = findSubarrayForIndex(size);
>+            int idx = findIndexIntoSubarray(size);
>+            identifiers[sub][idx] = id;
>+            size++;
>+        }
>+
>+        void set(int index, long id)
>+        {
>+            int sub = findSubarrayForIndex(index);
>+            int idx = findIndexIntoSubarray(index);
>+            identifiers[sub][idx] = id;
>         }
> 
>         public void sort()
>         {
>-            Arrays.parallelSort(identifiers, 0, size);
>+            new IdentifierSortTask(0, size - 1).invoke();
>+        }
>+
>+        class IdentifierSortTask extends RecursiveAction
>+        {
>+            final int low, high;
>+
>+            public IdentifierSortTask(final int low, final int high)
>+            {
>+                this.low = low;
>+                this.high = high;
>+            }
>+
>+            // adapted from:
>+            // https://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html
>+            // Copyright Â© 2012-2019 vogella GmbH. Free use of the software examples is
>+            // granted under the terms of the Eclipse Public
>+            // License 2.0. This tutorial is published under the Creative Commons
>+            // Attribution-NonCommercial-ShareAlike 3.0 Germany license.
>+
>+            public void compute()
>+            {
>+                // index range could be already met
>+                if (low >= high)
>+                { return; }
>+
>+                // Compute direct, defer to JDK sort as soon as possible
>+                if (findSubarrayForIndex(low) == findSubarrayForIndex(high))
>+                {
>+                    Arrays.sort(identifiers[findSubarrayForIndex(low)], findIndexIntoSubarray(low),
>+                                    findIndexIntoSubarray(high) + 1);
>+                    return;
>+                }
>+
>+                int i = low, j = high;
>+                // Get the pivot element from the middle of the list
>+                long pivot = Identifier.this.get(low + (high - low) / 2);
>+
>+                // Divide into two lists
>+                while (i <= j)
>+                {
>+                    // If the current value from the left list is smaller than the pivot
>+                    // element then get the next element from the left list
>+                    while (Identifier.this.get(i) < pivot)
>+                    {
>+                        i++;
>+                    }
>+                    // If the current value from the right list is larger than the pivot
>+                    // element then get the next element from the right list
>+                    while (Identifier.this.get(j) > pivot)
>+                    {
>+                        j--;
>+                    }
>+
>+                    // If we have found a value in the left list which is larger than
>+                    // the pivot element and if we have found a value in the right list
>+                    // which is smaller than the pivot element then we exchange the
>+                    // values.
>+                    // As we are done we can increase i and j
>+                    if (i <= j)
>+                    {
>+                        exchange(i, j);
>+                        i++;
>+                        j--;
>+                    }
>+                }
>+                // Recursion
>+                invokeAll(new IdentifierSortTask(low, j), new IdentifierSortTask(i, high));
>+            }
>+
>+            void exchange(int i, int j)
>+            {
>+                long temp = Identifier.this.get(i);
>+                set(i, Identifier.this.get(j));
>+                set(j, temp);
>+            }
>         }
> 
>         public int size()
>@@ -123,7 +222,7 @@ public abstract class IndexWriter
>             if (index < 0 || index >= size)
>                 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); //$NON-NLS-1$//$NON-NLS-2$
> 
>-            return identifiers[index];
>+            return identifiers[findSubarrayForIndex(index)][findIndexIntoSubarray(index)];
>         }
> 
>         public int reverse(long val)
>@@ -165,7 +264,7 @@ public abstract class IndexWriter
> 
>                 public long next()
>                 {
>-                    return identifiers[index++];
>+                    return get(index++);
>                 }
> 
>             };

Actions: View | Diff

Attachments on bug 571331: 285606