Attachment #285606 for bug #571331

View | Details | Raw Unified | Return to bug 571331
Collapse All | Expand All




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;



    public static class Identifier implements IIndexReader.IOne2LongIndex
    {
        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;

        int findSubarrayForIndex(int index)
        {
            int array = index >> SUBARRAY_SHIFT;
            if (array >= identifiers.length)
            {
                long[][] newIdentifiers = new long[identifiers.length * 2][];
                System.arraycopy(identifiers, 0, newIdentifiers, 0, identifiers.length);
                identifiers = newIdentifiers;
            }
            if (identifiers[array] == null)
            if (size + 1 > identifiers.length)
            {
                identifiers[array] = new long[SUBARRAY_SIZE];
                long totalBytes = 0;
                for (long[] subarray : identifiers)
                {
                    if (subarray == null)
                        continue;
                    totalBytes += subarray.length * 8L;
                }
                identifiers = copyOf(identifiers, newCapacity);
            }
            return array;
        }

        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()
        {
            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()

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

            return identifiers[findSubarrayForIndex(index)][findIndexIntoSubarray(index)];
        }

        public int reverse(long val)


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

            };

Return to bug 571331

Lines 32-37 import java.util.concurrent.ExecutionException; Link Here

(-)a/plugins/org.eclipse.mat.parser/src/org/eclipse/mat/parser/index/IndexWriter.java (-17 / +116 lines)
32	import java.util.concurrent.ExecutorService;	32	import java.util.concurrent.ExecutorService;
33	import java.util.concurrent.Executors;	33	import java.util.concurrent.Executors;
34	import java.util.concurrent.Future;	34	import java.util.concurrent.Future;
		35	import java.util.concurrent.RecursiveAction;
35	import java.util.concurrent.TimeUnit;	36	import java.util.concurrent.TimeUnit;
36	import java.util.function.Supplier;	37	import java.util.function.Supplier;
37		38
Lines 82-116 public abstract class IndexWriter Link Here
82		83
83	public static class Identifier implements IIndexReader.IOne2LongIndex	84	public static class Identifier implements IIndexReader.IOne2LongIndex
84	{	85	{
85	long[] identifiers;	86	private static final int SUBARRAY_SIZE = 4 * 1024 * 1024; // 8 bytes, 32MB chunks
		87	private static final int SUBARRAY_SHIFT = 22;
		88	private static final int SUBARRAY_MASK = 0b00111111_11111111_11111111;
		89	long[][] identifiers = new long[][] { new long[SUBARRAY_SIZE] };
86	int size;	90	int size;
87		91
88	public void add(long id)	92	int findSubarrayForIndex(int index)
89	{	93	{
90	if (identifiers == null)	94	int array = index >> SUBARRAY_SHIFT;
		95	if (array >= identifiers.length)
91	{	96	{
92	identifiers = new long[10000];	97	long[][] newIdentifiers = new long[identifiers.length * 2][];
93	size = 0;	98	System.arraycopy(identifiers, 0, newIdentifiers, 0, identifiers.length);
		99	identifiers = newIdentifiers;
94	}	100	}
95		101	if (identifiers[array] == null)
96	if (size + 1 > identifiers.length)
97	{	102	{
98	int minCapacity = size + 1;	103	identifiers[array] = new long[SUBARRAY_SIZE];
99	int newCapacity = newCapacity(identifiers.length, minCapacity);	104	long totalBytes = 0;
100	if (newCapacity < minCapacity)	105	for (long[] subarray : identifiers)
101	{	106	{
102	// Avoid strange exceptions later	107	if (subarray == null)
103	throw new OutOfMemoryError(MessageUtil.format(Messages.IndexWriter_Error_ArrayLength, minCapacity, newCapacity));	108	continue;
		109	totalBytes += subarray.length * 8L;
104	}	110	}
105	identifiers = copyOf(identifiers, newCapacity);
106	}	111	}
		112	return array;
		113	}
107		114
108	identifiers[size++] = id;	115	int findIndexIntoSubarray(int index)
		116	{
		117	return index & SUBARRAY_MASK;
		118	}
		119
		120	public void add(long id)
		121	{
		122	int sub = findSubarrayForIndex(size);
		123	int idx = findIndexIntoSubarray(size);
		124	identifiers[sub][idx] = id;
		125	size++;
		126	}
		127
		128	void set(int index, long id)
		129	{
		130	int sub = findSubarrayForIndex(index);
		131	int idx = findIndexIntoSubarray(index);
		132	identifiers[sub][idx] = id;
109	}	133	}
110		134
111	public void sort()	135	public void sort()
112	{	136	{
113	Arrays.parallelSort(identifiers, 0, size);	137	new IdentifierSortTask(0, size - 1).invoke();
		138	}
		139
		140	class IdentifierSortTask extends RecursiveAction
		141	{
		142	final int low, high;
		143
		144	public IdentifierSortTask(final int low, final int high)
		145	{
		146	this.low = low;
		147	this.high = high;
		148	}
		149
		150	// adapted from:
		151	// https://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html
		152	// Copyright © 2012-2019 vogella GmbH. Free use of the software examples is
		153	// granted under the terms of the Eclipse Public
		154	// License 2.0. This tutorial is published under the Creative Commons
		155	// Attribution-NonCommercial-ShareAlike 3.0 Germany license.
		156
		157	public void compute()
		158	{
		159	// index range could be already met
		160	if (low >= high)
		161	{ return; }
		162
		163	// Compute direct, defer to JDK sort as soon as possible
		164	if (findSubarrayForIndex(low) == findSubarrayForIndex(high))
		165	{
		166	Arrays.sort(identifiers[findSubarrayForIndex(low)], findIndexIntoSubarray(low),
		167	findIndexIntoSubarray(high) + 1);
		168	return;
		169	}
		170
		171	int i = low, j = high;
		172	// Get the pivot element from the middle of the list
		173	long pivot = Identifier.this.get(low + (high - low) / 2);
		174
		175	// Divide into two lists
		176	while (i <= j)
		177	{
		178	// If the current value from the left list is smaller than the pivot
		179	// element then get the next element from the left list
		180	while (Identifier.this.get(i) < pivot)
		181	{
		182	i++;
		183	}
		184	// If the current value from the right list is larger than the pivot
		185	// element then get the next element from the right list
		186	while (Identifier.this.get(j) > pivot)
		187	{
		188	j--;
		189	}
		190
		191	// If we have found a value in the left list which is larger than
		192	// the pivot element and if we have found a value in the right list
		193	// which is smaller than the pivot element then we exchange the
		194	// values.
		195	// As we are done we can increase i and j
		196	if (i <= j)
		197	{
		198	exchange(i, j);
		199	i++;
		200	j--;
		201	}
202	}
203	// Recursion
204	invokeAll(new IdentifierSortTask(low, j), new IdentifierSortTask(i, high));
205	}
206
207	void exchange(int i, int j)
208	{
209	long temp = Identifier.this.get(i);
210	set(i, Identifier.this.get(j));
211	set(j, temp);
212	}
114	}	213	}
115		214
116	public int size()	215	public int size()
Lines 123-129 public abstract class IndexWriter Link Here
123	if (index < 0 \|\| index >= size)	222	if (index < 0 \|\| index >= size)
124	throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); //$NON-NLS-1$//$NON-NLS-2$	223	throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); //$NON-NLS-1$//$NON-NLS-2$
125		224
126	return identifiers[index];	225	return identifiers[findSubarrayForIndex(index)][findIndexIntoSubarray(index)];
127	}	226	}
128		227
129	public int reverse(long val)	228	public int reverse(long val)
Lines 165-171 public abstract class IndexWriter Link Here
165		264
166	public long next()	265	public long next()
167	{	266	{
168	return identifiers[index++];	267	return get(index++);
169	}	268	}
170		269
171	};	270	};