Attachment #286016 for bug #572512




import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.SynchronousQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
import java.util.function.Supplier;


    // integer based indices
    // //////////////////////////////////////////////////////////////

    public static class Identifier extends MemoryMappedLongArray implements IIndexReader.IOne2LongIndex
    {
        // all implementations in extended class
        public Identifier() {
            super(null, 0, Integer.MAX_VALUE);
        public void add(long id)
        {
            if (identifiers == null)
            {
                identifiers = new long[10000];
                size = 0;
            }

            if (size + 1 > identifiers.length)
            {
                int minCapacity = size + 1;
                int newCapacity = newCapacity(identifiers.length, minCapacity);
                if (newCapacity < minCapacity)
                {
                    // Avoid strange exceptions later
                    throw new OutOfMemoryError(MessageUtil.format(Messages.IndexWriter_Error_ArrayLength, minCapacity, newCapacity));
                }
                identifiers = copyOf(identifiers, newCapacity);
            }

            identifiers[size++] = id;
        }

        public void sort()
        {
            Arrays.parallelSort(identifiers, 0, size);
        }

        public int size()
        {
            return size;
        }

        public long get(int index)
        {
            if (index < 0 || index >= size)
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); //$NON-NLS-1$//$NON-NLS-2$

            return identifiers[index];
        }

        public int reverse(long val) {
            return super.indexOf(val);
            int a, c;
            for (a = 0, c = size; a < c;)
            {
                // Avoid overflow problems by using unsigned divide by 2
                int b = (a + c) >>> 1;
                long probeVal = get(b);
                if (val < probeVal)
                {
                    c = b;
                }
                else if (probeVal < val)
                {
                    a = b + 1;
                }
                else
                {
                    return b;
                }
            }
            // Negative index indicates not found (and where to insert)
            return -1 - a;
        }

        public IteratorLong iterator()
        {
            return new IteratorLong()
            {

                int index = 0;

                public boolean hasNext()
                {
                    return index < size;
                }

                public long next()
                {
                    return identifiers[index++];
                }

            };
        }

        public long[] getNext(int index, int length)
        {
            long answer[] = new long[length];
            for (int ii = 0; ii < length; ii++)
                answer[ii] = identifiers[index + ii];
            return answer;
        }

        public void close() throws IOException
        {}

        public void delete()
        {
            identifiers = null;
        }

        public void unload() throws IOException
        {
            throw new UnsupportedOperationException();
        }
    }

    public static class SizeIndexCollectorUncompressed {
        final MemoryMappedIntArray wrapped;
        public SizeIndexCollectorUncompressed(int size) {
            wrapped = new MemoryMappedIntArray(null, size, size);
        public IntIndexCollectorUncompressed(int size)
        {
            dataElements = new int[size];
        }

        public void set(int index, int value)
        {
            dataElements[index] = value;
        }

        public int get(int index)
        {
            return dataElements[index];
        }

        public IIndexReader.IOne2OneIndex writeTo(File indexFile) throws IOException
        {
            return new IntIndexStreamer().writeTo(indexFile, dataElements);
        }
    }

    /**
     * Store sizes of objects by
     * compressing the size to a 32-bit int.
     * @since 1.0
     */
    public static class SizeIndexCollectorUncompressed extends IntIndexCollectorUncompressed
    {

        public SizeIndexCollectorUncompressed(int size)
        {
            super(size);
        }

        /**


        public void set(int index, long value)
        {
            wrapped.set(index, compress(value));
        }

        public int get(int index)
        {
            return wrapped.get(index);
        }

        public long getSize(int index)
        {
            return expand(wrapped.get(index));
            return expand(v);
        }

        public IIndexReader.IOne2SizeIndex writeTo(File indexFile) throws IOException
        {
            return new SizeIndexReader(new IntIndexStreamer().writeTo(indexFile, wrapped.iterator()));
        }
    }





package org.eclipse.mat.parser.index;

import java.util.Arrays;
import java.util.concurrent.RecursiveAction;
import org.eclipse.mat.collect.IteratorInt;

public interface IntArray
{
    public int get(int index);

    public void set(int index, int value);

    public int size();

    static class IntArrayIterator implements IteratorInt
    {
        final IntArray array;
        int index;
        IntArrayIterator(final IntArray array)
        {
            this.array = array;
            this.index = 0;
        }

        public boolean hasNext() {
            return index < array.size();
        }

        public int next() {
            return array.get(index++);
        }
    }

    static class IntArraySortTask extends RecursiveAction
    {
        final static int SORT_DIRECT_SIZE = 64*1024; // 64*1024 elements

        final int low, high;
        final IntArray array;

        public IntArraySortTask(final IntArray array, final int low, final int high)
        {
            this.array = array;
            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.

        void directCompute()
        {
            int[] toSort = new int[high - low + 1];
            for(int i = low; i <= high; i++) {
                toSort[i - low] = array.get(i);
            }

            Arrays.sort(toSort);

            for(int i = low; i <= high; i++) {
                array.set(i, toSort[i - low]);
            }
        }

        public void compute()
        {
            // index range could be already met
            if (low >= high)
            { return; }

            // Compute direct, defer to JDK sort as soon as possible
            if ((high - low) <= SORT_DIRECT_SIZE)
            {
                directCompute();
                return;
            }

            int i = low, j = high;
            // Get the pivot element from the middle of the list
            int pivot = array.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 (array.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 (array.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 IntArraySortTask(array, low, j), new IntArraySortTask(array, i, high));
        }

        void exchange(int i, int j)
        {
            int temp = array.get(i);
            array.set(i, array.get(j));
            array.set(j, temp);
        }
    }
}




package org.eclipse.mat.parser.index;

import java.util.Arrays;
import java.util.concurrent.RecursiveAction;
import org.eclipse.mat.collect.IteratorLong;

public interface LongArray
{
    public long get(int index);

    public void set(int index, long value);

    public int size();

    static class LongArrayIterator implements IteratorLong
    {
        final LongArray array;
        int index;
        LongArrayIterator(final LongArray array)
        {
            this.array = array;
            this.index = 0;
        }

        public boolean hasNext() {
            return index < array.size();
        }

        public long next() {
            return array.get(index++);
        }
    }

    static class LongArraySortTask extends RecursiveAction
    {
        final static int SORT_DIRECT_SIZE = 64*1024; // 64 * 1024 elements

        final int low, high;
        final LongArray array;

        public LongArraySortTask(final LongArray array, final int low, final int high)
        {
            this.array = array;
            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.

        void directCompute()
        {
            long[] toSort = new long[high - low + 1];
            for(int i = low; i <= high; i++) {
                toSort[i - low] = array.get(i);
            }

            Arrays.sort(toSort);

            for(int i = low; i <= high; i++) {
                array.set(i, toSort[i - low]);
            }
        }

        public void compute()
        {
            // index range could be already met
            if (low >= high)
            { return; }

            // Compute direct, defer to JDK sort as soon as possible
            if ((high - low) <= SORT_DIRECT_SIZE)
            {
                directCompute();
                return;
            }

            int i = low, j = high;
            // Get the pivot element from the middle of the list
            long pivot = array.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 (array.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 (array.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 LongArraySortTask(array, low, j), new LongArraySortTask(array, i, high));
        }

        void exchange(int i, int j)
        {
            long temp = array.get(i);
            array.set(i, array.get(j));
            array.set(j, temp);
        }
    }
}




package org.eclipse.mat.parser.index;

import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.lang.reflect.Array;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel.MapMode;
import java.util.function.Function;

public class MemoryMappedArraySupport<T> {
    // this is limited to a 2GB length array, and identifiers are x bytes => x*2GB file at most
    // but, we are constrained to at most 2GB-indexing into ByteBuffer, so need to sub-map
    final static int MB = 1*1024*1024;
    final static long BUFFER_SIZE = 1024L*MB;
    final static long FILE_EXTEND_LENGTH = 64*MB;
    final static long MAX_ELEMENTS = 2L*1024*MB;

    final T[] buffers;

    final RandomAccessFile file;
    final String filename;
    int nextWriteIndex = 0;
    long lengthCache = 0;
    final int maxCapacity;
    final long sizeOfElement;
    final Function<ByteBuffer, T> castFn;

    public MemoryMappedArraySupport(String filename, final int initialCapacity, final int maxCapacity,
            final long sizeOfElement, final Function<ByteBuffer, T> castFn, final Class<T> clazz) {
        if (filename == null) {
            try {
                File file = File.createTempFile("mat_memory_mapped_array", null, null);
                file.deleteOnExit();
                filename = file.getName();
            } catch (IOException e) {
                throw new RuntimeException("could not create temporary array store", e);
            }
        }
        this.filename = filename;
        try {
            file = new RandomAccessFile(filename, "rw");
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        this.maxCapacity = maxCapacity;
        this.nextWriteIndex = initialCapacity;
        this.castFn = castFn;
        this.sizeOfElement = sizeOfElement;
        this.buffers = (T[]) Array.newInstance(clazz, (int) ((MAX_ELEMENTS * sizeOfElement) / BUFFER_SIZE));

        // fill any buffers
        for(int i = 0; i < bufferNumber(initialCapacity - 1); i++) {
            createBufferIfNull(i);
        }

        ensureExists(initialCapacity - 1);
        if (initialCapacity > 0) {
            // backfill any buffers
            for(int i = 0; i < bufferNumber(initialCapacity - 1); i++) {
                createBufferIfNull(i);
            }
        }
    }

    int offsetIntoBuffer(int index) {
	    return (int) (((long)index) % (BUFFER_SIZE/sizeOfElement));
    }

    int bufferNumber(int index) {
        return (int) (((long)index) / (BUFFER_SIZE/sizeOfElement));
    }

    public int size() {
        return nextWriteIndex;
    }

    public void unload() /*throws IOException*/ {
        for(int i = 0; i < buffers.length; i++) {
            buffers[i] = null;
        }
    }

    public void close() throws IOException {
        unload();
        file.close();
    }

    public void delete() {
        new File(filename).delete();
    }

    long fileLength() {
        return lengthCache;
    }

    void fileSetLength(long length) {
        try {
            file.setLength(length);
            lengthCache = length;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    void checkExists(int index) {
        if (((index + 1) * sizeOfElement) > fileLength() || (index < 0)) {
            throw new IndexOutOfBoundsException("index = " + index + ", file length = " + fileLength());
        }
    }

    void createBufferIfNull(int bufferIndex) {
        if (buffers[bufferIndex] == null) {
            try {
                ByteBuffer newBuffer = file.getChannel().map(MapMode.READ_WRITE, bufferIndex*BUFFER_SIZE, BUFFER_SIZE);
                buffers[bufferIndex] = castFn.apply(newBuffer);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }

    void ensureExists(int index) {
        if (index > maxCapacity) {
            throw new IndexOutOfBoundsException("too many elements for array. index = " + index + ", maxCapacity = " + maxCapacity);
        }

        long requiredLength = (index + 1) * sizeOfElement;
        while (requiredLength > fileLength()) {
            fileSetLength(fileLength() + FILE_EXTEND_LENGTH);
        }

        createBufferIfNull(bufferNumber(index));
    }
}




package org.eclipse.mat.parser.index;

import java.nio.IntBuffer;
import java.nio.ByteBuffer;
import java.util.function.Function;
import org.eclipse.mat.collect.IteratorInt;

public class MemoryMappedIntArray extends MemoryMappedArraySupport<IntBuffer> implements IntArray {
    final static int SIZEOF_INT = 4;

    public MemoryMappedIntArray(final String filename, final int initialCapacity, final int maxCapacity)
    {
        super(filename, initialCapacity, maxCapacity, SIZEOF_INT, ByteBuffer::asIntBuffer, IntBuffer.class);
    }

    public int get(int index) {
        checkExists(index);
        return buffers[bufferNumber(index)].get(offsetIntoBuffer(index));
    }

    public int indexOf(int val)
    {
        int a, c;
        for (a = 0, c = size(); a < c;)
        {
            // Avoid overflow problems by using unsigned divide by 2
            int b = (a + c) >>> 1;
            int probeVal = get(b);
            if (val < probeVal)
            {
                c = b;
            }
            else if (probeVal < val)
            {
                a = b + 1;
            }
            else
            {
                return b;
            }
        }
        // Negative index indicates not found (and where to insert)
        return -1 - a;
    }

    public int[] getNext(int index, int length) {
        int[] answers = new int[length];
        for(int i = 0; i < length; i++) {
            answers[i] = get(index + i);
        }
        return answers;
    }

    // public

    public void add(int value) {
        ensureExists(nextWriteIndex);
        buffers[bufferNumber(nextWriteIndex)].put(offsetIntoBuffer(nextWriteIndex), value);
        nextWriteIndex++;
    }

    public void sort() {
        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++)
        {
            answers[i] = get(indices[i]);
        }
        return answers;
    }

    public void set(int index, int value) {
        checkExists(index);
        buffers[bufferNumber(index)].put(offsetIntoBuffer(index), value);
    }
}




package org.eclipse.mat.parser.index;

import java.nio.LongBuffer;
import java.nio.ByteBuffer;
import java.util.function.Function;
import org.eclipse.mat.collect.IteratorLong;

public class MemoryMappedLongArray extends MemoryMappedArraySupport<LongBuffer> implements LongArray {
    final static long SIZEOF_LONG = 8L;

    public MemoryMappedLongArray(final String filename, final int initialCapacity, final int maxCapacity)
    {
        super(filename, initialCapacity, maxCapacity, SIZEOF_LONG, ByteBuffer::asLongBuffer, LongBuffer.class);
    }

    public long get(int index) {
        checkExists(index);
        return buffers[bufferNumber(index)].get(offsetIntoBuffer(index));
    }

    public int indexOf(long val)
    {
        int a, c;
        for (a = 0, c = size(); a < c;)
        {
            // Avoid overflow problems by using unsigned divide by 2
            int b = (a + c) >>> 1;
            long probeVal = get(b);
            if (val < probeVal)
            {
                c = b;
            }
            else if (probeVal < val)
            {
                a = b + 1;
            }
            else
            {
                return b;
            }
        }
        // Negative index indicates not found (and where to insert)
        return -1 - a;
    }

    public long[] getNext(int index, int length) {
        long[] answers = new long[length];
        for(int i = 0; i < length; i++) {
            answers[i] = get(index + i);
        }
        return answers;
    }

    public void add(long value) {
        ensureExists(nextWriteIndex);
        buffers[bufferNumber(nextWriteIndex)].put(offsetIntoBuffer(nextWriteIndex), value);
        nextWriteIndex++;
    }

    public void sort() {
        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++)
        {
            answers[i] = get(indices[i]);
        }
        return answers;
    }

    public void set(int index, long value) {
        checkExists(index);
        buffers[bufferNumber(index)].put(offsetIntoBuffer(index), value);
    }
}

Return to bug 572512

Lines 34-39 import java.util.concurrent.ExecutionException; Link Here

(-)a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IndexWriter.java (-147 / +21 lines)
34	import java.util.concurrent.ExecutorService;	34	import java.util.concurrent.ExecutorService;
35	import java.util.concurrent.Executors;	35	import java.util.concurrent.Executors;
36	import java.util.concurrent.Future;	36	import java.util.concurrent.Future;
		37	import java.util.concurrent.RecursiveAction;
		38	import java.util.concurrent.SynchronousQueue;
		39	import java.util.concurrent.ThreadPoolExecutor;
37	import java.util.concurrent.TimeUnit;	40	import java.util.concurrent.TimeUnit;
38	import java.util.function.Supplier;	41	import java.util.function.Supplier;
39		42
Lines 82-236 public abstract class IndexWriter Link Here
82	// integer based indices	85	// integer based indices
83	// //////////////////////////////////////////////////////////////	86	// //////////////////////////////////////////////////////////////
84		87
85	public static class Identifier implements IIndexReader.IOne2LongIndex	88	public static class Identifier extends MemoryMappedLongArray implements IIndexReader.IOne2LongIndex
86	{	89	{
87	long[] identifiers;	90	// all implementations in extended class
88	int size;	91	public Identifier() {
89		92	super(null, 0, Integer.MAX_VALUE);
90	public void add(long id)
91	{
92	if (identifiers == null)
93	{
94	identifiers = new long[10000];
95	size = 0;
96	}
97
98	if (size + 1 > identifiers.length)
99	{
100	int minCapacity = size + 1;
101	int newCapacity = newCapacity(identifiers.length, minCapacity);
102	if (newCapacity < minCapacity)
103	{
104	// Avoid strange exceptions later
105	throw new OutOfMemoryError(MessageUtil.format(Messages.IndexWriter_Error_ArrayLength, minCapacity, newCapacity));
106	}
107	identifiers = copyOf(identifiers, newCapacity);
108	}
109
110	identifiers[size++] = id;
111	}
112
113	public void sort()
114	{
115	Arrays.parallelSort(identifiers, 0, size);
116	}
117
118	public int size()
119	{
120	return size;
121	}
122
123	public long get(int index)
124	{
125	if (index < 0 \|\| index >= size)
126	throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); //$NON-NLS-1$//$NON-NLS-2$
127
128	return identifiers[index];
129	}	93	}
130		94
131	public int reverse(long val)	95	public int reverse(long val) {
132	{	96	return super.indexOf(val);
133	int a, c;
134	for (a = 0, c = size; a < c;)
135	{
136	// Avoid overflow problems by using unsigned divide by 2
137	int b = (a + c) >>> 1;
138	long probeVal = get(b);
139	if (val < probeVal)
140	{
141	c = b;
142	}
143	else if (probeVal < val)
144	{
145	a = b + 1;
146	}
147	else
148	{
149	return b;
150	}
151	}
152	// Negative index indicates not found (and where to insert)
153	return -1 - a;
154	}
155
156	public IteratorLong iterator()
157	{
158	return new IteratorLong()
159	{
160
161	int index = 0;
162
163	public boolean hasNext()
164	{
165	return index < size;
166	}
167
168	public long next()
169	{
170	return identifiers[index++];
171	}
172
173	};
174	}
175
176	public long[] getNext(int index, int length)
177	{
178	long answer[] = new long[length];
179	for (int ii = 0; ii < length; ii++)
180	answer[ii] = identifiers[index + ii];
181	return answer;
182	}
183
184	public void close() throws IOException
185	{}
186
187	public void delete()
188	{
189	identifiers = null;
190	}
191
192	public void unload() throws IOException
193	{
194	throw new UnsupportedOperationException();
195	}	97	}
196	}	98	}
197		99
198	public static class IntIndexCollectorUncompressed	100	public static class SizeIndexCollectorUncompressed {
199	{	101	final MemoryMappedIntArray wrapped;
200	int[] dataElements;	102	public SizeIndexCollectorUncompressed(int size) {
201		103	wrapped = new MemoryMappedIntArray(null, size, size);
202	public IntIndexCollectorUncompressed(int size)
203	{
204	dataElements = new int[size];
205	}
206
207	public void set(int index, int value)
208	{
209	dataElements[index] = value;
210	}
211
212	public int get(int index)
213	{
214	return dataElements[index];
215	}
216
217	public IIndexReader.IOne2OneIndex writeTo(File indexFile) throws IOException
218	{
219	return new IntIndexStreamer().writeTo(indexFile, dataElements);
220	}
221	}
222
223	/**
224	* Store sizes of objects by
225	* compressing the size to a 32-bit int.
226	* @since 1.0
227	*/
228	public static class SizeIndexCollectorUncompressed extends IntIndexCollectorUncompressed
229	{
230
231	public SizeIndexCollectorUncompressed(int size)
232	{
233	super(size);
234	}	104	}
235		105
236	/**	106	/**
Lines 280-297 public abstract class IndexWriter Link Here
280		150
281	public void set(int index, long value)	151	public void set(int index, long value)
282	{	152	{
283	set(index, compress(value));	153	wrapped.set(index, compress(value));
		154	}
		155
		156	public int get(int index)
		157	{
		158	return wrapped.get(index);
284	}	159	}
285		160
286	public long getSize(int index)	161	public long getSize(int index)
287	{	162	{
288	int v = get(index);	163	return expand(wrapped.get(index));
289	return expand(v);
290	}	164	}
291		165
292	public IIndexReader.IOne2SizeIndex writeTo(File indexFile) throws IOException	166	public IIndexReader.IOne2SizeIndex writeTo(File indexFile) throws IOException
293	{	167	{
294	return new SizeIndexReader(new IntIndexStreamer().writeTo(indexFile, dataElements));	168	return new SizeIndexReader(new IntIndexStreamer().writeTo(indexFile, wrapped.iterator()));
295	}	169	}
296	}	170	}
297		171

Added Link Here

(-)a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IntArray.java (+125 lines)
1	package org.eclipse.mat.parser.index;
2
3	import java.util.Arrays;
4	import java.util.concurrent.RecursiveAction;
5	import org.eclipse.mat.collect.IteratorInt;
6
7	public interface IntArray
8	{
9	public int get(int index);
10
11	public void set(int index, int value);
12
13	public int size();
14
15	static class IntArrayIterator implements IteratorInt
16	{
17	final IntArray array;
18	int index;
19	IntArrayIterator(final IntArray array)
20	{
21	this.array = array;
22	this.index = 0;
23	}
24
25	public boolean hasNext() {
26	return index < array.size();
27	}
28
29	public int next() {
30	return array.get(index++);
31	}
32	}
33
34	static class IntArraySortTask extends RecursiveAction
35	{
36	final static int SORT_DIRECT_SIZE = 641024; // 641024 elements
37
38	final int low, high;
39	final IntArray array;
40
41	public IntArraySortTask(final IntArray array, final int low, final int high)
42	{
43	this.array = array;
44	this.low = low;
45	this.high = high;
46	}
47
48	// adapted from:
49	// https://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html
50	// Copyright © 2012-2019 vogella GmbH. Free use of the software examples is
51	// granted under the terms of the Eclipse Public
52	// License 2.0. This tutorial is published under the Creative Commons
53	// Attribution-NonCommercial-ShareAlike 3.0 Germany license.
54
55	void directCompute()
56	{
57	int[] toSort = new int[high - low + 1];
58	for(int i = low; i <= high; i++) {
59	toSort[i - low] = array.get(i);
60	}
61
62	Arrays.sort(toSort);
63
64	for(int i = low; i <= high; i++) {
65	array.set(i, toSort[i - low]);
66	}
67	}
68
69	public void compute()
70	{
71	// index range could be already met
72	if (low >= high)
73	{ return; }
74
75	// Compute direct, defer to JDK sort as soon as possible
76	if ((high - low) <= SORT_DIRECT_SIZE)
77	{
78	directCompute();
79	return;
80	}
81
82	int i = low, j = high;
83	// Get the pivot element from the middle of the list
84	int pivot = array.get(low + (high - low) / 2);
85
86	// Divide into two lists
87	while (i <= j)
88	{
89	// If the current value from the left list is smaller than the pivot
90	// element then get the next element from the left list
91	while (array.get(i) < pivot)
92	{
93	i++;
94	}
95	// If the current value from the right list is larger than the pivot
96	// element then get the next element from the right list
97	while (array.get(j) > pivot)
98	{
99	j--;
100	}
101
102	// If we have found a value in the left list which is larger than
103	// the pivot element and if we have found a value in the right list
104	// which is smaller than the pivot element then we exchange the
105	// values.
106	// As we are done we can increase i and j
107	if (i <= j)
108	{
109	exchange(i, j);
110	i++;
111	j--;
112	}
113	}
114	// Recursion
115	invokeAll(new IntArraySortTask(array, low, j), new IntArraySortTask(array, i, high));
116	}
117
118	void exchange(int i, int j)
119	{
120	int temp = array.get(i);
121	array.set(i, array.get(j));
122	array.set(j, temp);
123	}
124	}
125	}

Added Link Here

(-)a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/LongArray.java (+125 lines)
1	package org.eclipse.mat.parser.index;
2
3	import java.util.Arrays;
4	import java.util.concurrent.RecursiveAction;
5	import org.eclipse.mat.collect.IteratorLong;
6
7	public interface LongArray
8	{
9	public long get(int index);
10
11	public void set(int index, long value);
12
13	public int size();
14
15	static class LongArrayIterator implements IteratorLong
16	{
17	final LongArray array;
18	int index;
19	LongArrayIterator(final LongArray array)
20	{
21	this.array = array;
22	this.index = 0;
23	}
24
25	public boolean hasNext() {
26	return index < array.size();
27	}
28
29	public long next() {
30	return array.get(index++);
31	}
32	}
33
34	static class LongArraySortTask extends RecursiveAction
35	{
36	final static int SORT_DIRECT_SIZE = 641024; // 64 1024 elements
37
38	final int low, high;
39	final LongArray array;
40
41	public LongArraySortTask(final LongArray array, final int low, final int high)
42	{
43	this.array = array;
44	this.low = low;
45	this.high = high;
46	}
47
48	// adapted from:
49	// https://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html
50	// Copyright © 2012-2019 vogella GmbH. Free use of the software examples is
51	// granted under the terms of the Eclipse Public
52	// License 2.0. This tutorial is published under the Creative Commons
53	// Attribution-NonCommercial-ShareAlike 3.0 Germany license.
54
55	void directCompute()
56	{
57	long[] toSort = new long[high - low + 1];
58	for(int i = low; i <= high; i++) {
59	toSort[i - low] = array.get(i);
60	}
61
62	Arrays.sort(toSort);
63
64	for(int i = low; i <= high; i++) {
65	array.set(i, toSort[i - low]);
66	}
67	}
68
69	public void compute()
70	{
71	// index range could be already met
72	if (low >= high)
73	{ return; }
74
75	// Compute direct, defer to JDK sort as soon as possible
76	if ((high - low) <= SORT_DIRECT_SIZE)
77	{
78	directCompute();
79	return;
80	}
81
82	int i = low, j = high;
83	// Get the pivot element from the middle of the list
84	long pivot = array.get(low + (high - low) / 2);
85
86	// Divide into two lists
87	while (i <= j)
88	{
89	// If the current value from the left list is smaller than the pivot
90	// element then get the next element from the left list
91	while (array.get(i) < pivot)
92	{
93	i++;
94	}
95	// If the current value from the right list is larger than the pivot
96	// element then get the next element from the right list
97	while (array.get(j) > pivot)
98	{
99	j--;
100	}
101
102	// If we have found a value in the left list which is larger than
103	// the pivot element and if we have found a value in the right list
104	// which is smaller than the pivot element then we exchange the
105	// values.
106	// As we are done we can increase i and j
107	if (i <= j)
108	{
109	exchange(i, j);
110	i++;
111	j--;
112	}
113	}
114	// Recursion
115	invokeAll(new LongArraySortTask(array, low, j), new LongArraySortTask(array, i, high));
116	}
117
118	void exchange(int i, int j)
119	{
120	long temp = array.get(i);
121	array.set(i, array.get(j));
122	array.set(j, temp);
123	}
124	}
125	}

Added Link Here

(-)a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedArraySupport.java (+135 lines)
1	package org.eclipse.mat.parser.index;
2
3	import java.io.File;
4	import java.io.IOException;
5	import java.io.RandomAccessFile;
6	import java.lang.reflect.Array;
7	import java.nio.ByteBuffer;
8	import java.nio.channels.FileChannel.MapMode;
9	import java.util.function.Function;
10
11	public class MemoryMappedArraySupport<T> {
12	// this is limited to a 2GB length array, and identifiers are x bytes => x*2GB file at most
13	// but, we are constrained to at most 2GB-indexing into ByteBuffer, so need to sub-map
14	final static int MB = 110241024;
15	final static long BUFFER_SIZE = 1024L*MB;
16	final static long FILE_EXTEND_LENGTH = 64*MB;
17	final static long MAX_ELEMENTS = 2L1024MB;
18
19	final T[] buffers;
20
21	final RandomAccessFile file;
22	final String filename;
23	int nextWriteIndex = 0;
24	long lengthCache = 0;
25	final int maxCapacity;
26	final long sizeOfElement;
27	final Function<ByteBuffer, T> castFn;
28
29	public MemoryMappedArraySupport(String filename, final int initialCapacity, final int maxCapacity,
30	final long sizeOfElement, final Function<ByteBuffer, T> castFn, final Class<T> clazz) {
31	if (filename == null) {
32	try {
33	File file = File.createTempFile("mat_memory_mapped_array", null, null);
34	file.deleteOnExit();
35	filename = file.getName();
36	} catch (IOException e) {
37	throw new RuntimeException("could not create temporary array store", e);
38	}
39	}
40	this.filename = filename;
41	try {
42	file = new RandomAccessFile(filename, "rw");
43	} catch (IOException e) {
44	throw new RuntimeException(e);
45	}
46	this.maxCapacity = maxCapacity;
47	this.nextWriteIndex = initialCapacity;
48	this.castFn = castFn;
49	this.sizeOfElement = sizeOfElement;
50	this.buffers = (T[]) Array.newInstance(clazz, (int) ((MAX_ELEMENTS * sizeOfElement) / BUFFER_SIZE));
51
52	// fill any buffers
53	for(int i = 0; i < bufferNumber(initialCapacity - 1); i++) {
54	createBufferIfNull(i);
55	}
56
57	ensureExists(initialCapacity - 1);
58	if (initialCapacity > 0) {
59	// backfill any buffers
60	for(int i = 0; i < bufferNumber(initialCapacity - 1); i++) {
61	createBufferIfNull(i);
62	}
63	}
64	}
65
66	int offsetIntoBuffer(int index) {
67	return (int) (((long)index) % (BUFFER_SIZE/sizeOfElement));
68	}
69
70	int bufferNumber(int index) {
71	return (int) (((long)index) / (BUFFER_SIZE/sizeOfElement));
72	}
73
74	public int size() {
75	return nextWriteIndex;
76	}
77
78	public void unload() /throws IOException/ {
79	for(int i = 0; i < buffers.length; i++) {
80	buffers[i] = null;
81	}
82	}
83
84	public void close() throws IOException {
85	unload();
86	file.close();
87	}
88
89	public void delete() {
90	new File(filename).delete();
91	}
92
93	long fileLength() {
94	return lengthCache;
95	}
96
97	void fileSetLength(long length) {
98	try {
99	file.setLength(length);
100	lengthCache = length;
101	} catch (IOException e) {
102	throw new RuntimeException(e);
103	}
104	}
105
106	void checkExists(int index) {
107	if (((index + 1) * sizeOfElement) > fileLength() \|\| (index < 0)) {
108	throw new IndexOutOfBoundsException("index = " + index + ", file length = " + fileLength());
109	}
110	}
111
112	void createBufferIfNull(int bufferIndex) {
113	if (buffers[bufferIndex] == null) {
114	try {
115	ByteBuffer newBuffer = file.getChannel().map(MapMode.READ_WRITE, bufferIndex*BUFFER_SIZE, BUFFER_SIZE);
116	buffers[bufferIndex] = castFn.apply(newBuffer);
117	} catch (IOException e) {
118	throw new RuntimeException(e);
119	}
120	}
121	}
122
123	void ensureExists(int index) {
124	if (index > maxCapacity) {
125	throw new IndexOutOfBoundsException("too many elements for array. index = " + index + ", maxCapacity = " + maxCapacity);
126	}
127
128	long requiredLength = (index + 1) * sizeOfElement;
129	while (requiredLength > fileLength()) {
130	fileSetLength(fileLength() + FILE_EXTEND_LENGTH);
131	}
132
133	createBufferIfNull(bufferNumber(index));
134	}
135	}

Added Link Here

(-)a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedIntArray.java (+83 lines)
1	package org.eclipse.mat.parser.index;
2
3	import java.nio.IntBuffer;
4	import java.nio.ByteBuffer;
5	import java.util.function.Function;
6	import org.eclipse.mat.collect.IteratorInt;
7
8	public class MemoryMappedIntArray extends MemoryMappedArraySupport<IntBuffer> implements IntArray {
9	final static int SIZEOF_INT = 4;
10
11	public MemoryMappedIntArray(final String filename, final int initialCapacity, final int maxCapacity)
12	{
13	super(filename, initialCapacity, maxCapacity, SIZEOF_INT, ByteBuffer::asIntBuffer, IntBuffer.class);
14	}
15
16	public int get(int index) {
17	checkExists(index);
18	return buffers[bufferNumber(index)].get(offsetIntoBuffer(index));
19	}
20
21	public int indexOf(int val)
22	{
23	int a, c;
24	for (a = 0, c = size(); a < c;)
25	{
26	// Avoid overflow problems by using unsigned divide by 2
27	int b = (a + c) >>> 1;
28	int probeVal = get(b);
29	if (val < probeVal)
30	{
31	c = b;
32	}
33	else if (probeVal < val)
34	{
35	a = b + 1;
36	}
37	else
38	{
39	return b;
40	}
41	}
42	// Negative index indicates not found (and where to insert)
43	return -1 - a;
44	}
45
46	public int[] getNext(int index, int length) {
47	int[] answers = new int[length];
48	for(int i = 0; i < length; i++) {
49	answers[i] = get(index + i);
50	}
51	return answers;
52	}
53
54	// public
55
56	public void add(int value) {
57	ensureExists(nextWriteIndex);
58	buffers[bufferNumber(nextWriteIndex)].put(offsetIntoBuffer(nextWriteIndex), value);
59	nextWriteIndex++;
60	}
61
62	public void sort() {
63	new IntArray.IntArraySortTask(this, 0, size() - 1).invoke();
64	}
65
66	public IteratorInt iterator() {
67	return new IntArray.IntArrayIterator(this);
68	}
69
70	public int[] getAll(int[] indices) {
71	int[] answers = new int[indices.length];
72	for(int i = 0; i < indices.length; i++)
73	{
74	answers[i] = get(indices[i]);
75	}
76	return answers;
77	}
78
79	public void set(int index, int value) {
80	checkExists(index);
81	buffers[bufferNumber(index)].put(offsetIntoBuffer(index), value);
82	}
83	}

Added Link Here

(-)a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedLongArray.java (+81 lines)
1	package org.eclipse.mat.parser.index;
2
3	import java.nio.LongBuffer;
4	import java.nio.ByteBuffer;
5	import java.util.function.Function;
6	import org.eclipse.mat.collect.IteratorLong;
7
8	public class MemoryMappedLongArray extends MemoryMappedArraySupport<LongBuffer> implements LongArray {
9	final static long SIZEOF_LONG = 8L;
10
11	public MemoryMappedLongArray(final String filename, final int initialCapacity, final int maxCapacity)
12	{
13	super(filename, initialCapacity, maxCapacity, SIZEOF_LONG, ByteBuffer::asLongBuffer, LongBuffer.class);
14	}
15
16	public long get(int index) {
17	checkExists(index);
18	return buffers[bufferNumber(index)].get(offsetIntoBuffer(index));
19	}
20
21	public int indexOf(long val)
22	{
23	int a, c;
24	for (a = 0, c = size(); a < c;)
25	{
26	// Avoid overflow problems by using unsigned divide by 2
27	int b = (a + c) >>> 1;
28	long probeVal = get(b);
29	if (val < probeVal)
30	{
31	c = b;
32	}
33	else if (probeVal < val)
34	{
35	a = b + 1;
36	}
37	else
38	{
39	return b;
40	}
41	}
42	// Negative index indicates not found (and where to insert)
43	return -1 - a;
44	}
45
46	public long[] getNext(int index, int length) {
47	long[] answers = new long[length];
48	for(int i = 0; i < length; i++) {
49	answers[i] = get(index + i);
50	}
51	return answers;
52	}
53
54	public void add(long value) {
55	ensureExists(nextWriteIndex);
56	buffers[bufferNumber(nextWriteIndex)].put(offsetIntoBuffer(nextWriteIndex), value);
57	nextWriteIndex++;
58	}
59
60	public void sort() {
61	new LongArray.LongArraySortTask(this, 0, size() - 1).invoke();
62	}
63
64	public IteratorLong iterator() {
65	return new LongArray.LongArrayIterator(this);
66	}
67
68	public long[] getAll(int[] indices) {
69	long[] answers = new long[indices.length];
70	for(int i = 0; i < indices.length; i++)
71	{
72	answers[i] = get(indices[i]);
73	}
74	return answers;
75	}
76
77	public void set(int index, long value) {
78	checkExists(index);
79	buffers[bufferNumber(index)].put(offsetIntoBuffer(index), value);
80	}
81	}