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 6cd7a58e..2d41f9a5 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 @@ -34,6 +34,9 @@ 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.SynchronousQueue; +import java.util.concurrent.ThreadPoolExecutor; import java.util.concurrent.TimeUnit; import java.util.function.Supplier; @@ -82,155 +85,22 @@ public abstract class IndexWriter // integer based indices // ////////////////////////////////////////////////////////////// - public static class Identifier implements IIndexReader.IOne2LongIndex + public static class Identifier extends MemoryMappedLongArray implements IIndexReader.IOne2LongIndex { - long[] identifiers; - int size; - - 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]; + // all implementations in extended class + public Identifier() { + super(null, 0, Integer.MAX_VALUE); } - public int reverse(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 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 int reverse(long val) { + return super.indexOf(val); } } - public static class IntIndexCollectorUncompressed - { - int[] dataElements; - - 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 static class SizeIndexCollectorUncompressed { + final MemoryMappedIntArray wrapped; + public SizeIndexCollectorUncompressed(int size) { + wrapped = new MemoryMappedIntArray(null, size, size); } /** @@ -280,18 +150,22 @@ public abstract class IndexWriter public void set(int index, long value) { - set(index, compress(value)); + wrapped.set(index, compress(value)); + } + + public int get(int index) + { + return wrapped.get(index); } public long getSize(int index) { - int v = get(index); - return expand(v); + return expand(wrapped.get(index)); } public IIndexReader.IOne2SizeIndex writeTo(File indexFile) throws IOException { - return new SizeIndexReader(new IntIndexStreamer().writeTo(indexFile, dataElements)); + return new SizeIndexReader(new IntIndexStreamer().writeTo(indexFile, wrapped.iterator())); } } 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 new file mode 100644 index 00000000..f6b9e726 --- /dev/null +++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IntArray.java @@ -0,0 +1,125 @@ +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); + } + } +} \ 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 new file mode 100644 index 00000000..5e32cf65 --- /dev/null +++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/LongArray.java @@ -0,0 +1,125 @@ +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); + } + } +} \ No newline at end of file diff --git a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedArraySupport.java b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedArraySupport.java new file mode 100644 index 00000000..0a966003 --- /dev/null +++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedArraySupport.java @@ -0,0 +1,135 @@ +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 { + // 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 castFn; + + public MemoryMappedArraySupport(String filename, final int initialCapacity, final int maxCapacity, + final long sizeOfElement, final Function castFn, final Class 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)); + } +} \ 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 new file mode 100644 index 00000000..86330e1f --- /dev/null +++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedIntArray.java @@ -0,0 +1,83 @@ +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 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); + } +} \ 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 new file mode 100644 index 00000000..d16db471 --- /dev/null +++ b/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/MemoryMappedLongArray.java @@ -0,0 +1,81 @@ +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 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); + } +} \ No newline at end of file