--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.base/src/com/sun/max/profile/ValueMetrics.java	Sat Dec 17 19:59:18 2011 +0100
@@ -0,0 +1,730 @@
+/*
+ * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.sun.max.profile;
+
+import java.util.*;
+import java.util.Arrays;
+
+import com.sun.max.*;
+import com.sun.max.profile.Metrics.*;
+import com.sun.max.program.*;
+
+/**
+ * This class is a container for a number of inner classes that support recording
+ * metrics about the distribution (i.e. frequency) of values. For example,
+ * these utilities can be used to gather the distribution of compilation times,
+ * object sizes, heap allocations, etc. Several different distribution implementations
+ * are available, with different time and space tradeoffs and different approximations,
+ * ranging from exact distributions to only distributions within a limited range.
+ */
+public class ValueMetrics {
+
+    public static final Approximation EXACT = new Approximation();
+    public static final Approximation TRACE = new IntegerTraceApproximation(1024);
+
+    public static class Approximation {
+    }
+
+    public static class FixedApproximation extends Approximation {
+        protected final Object[] values;
+        public FixedApproximation(Object... values) {
+            this.values = values.clone();
+        }
+    }
+
+    public static class IntegerRangeApproximation extends Approximation {
+        protected final int lowValue;
+        protected final int highValue;
+        public IntegerRangeApproximation(int low, int high) {
+            lowValue = low;
+            highValue = high;
+        }
+    }
+
+    public static class IntegerTraceApproximation extends Approximation {
+        protected final int bufferSize;
+        public IntegerTraceApproximation(int bufferSize) {
+            this.bufferSize = bufferSize;
+        }
+    }
+
+    /**
+     * This class and its descendants allow recording of a distribution of integer values.
+     * Various implementations implement different approximations with different time and
+     * space tradeoffs. Because this class and its descendants record distributions only
+     * for integers, it can be more efficient than using boxed (e.g. {@code java.lang.Integer}) values.
+     *
+     */
+    public abstract static class IntegerDistribution extends Distribution<Integer> {
+
+        public abstract void record(int value);
+    }
+
+    public static class FixedRangeIntegerDistribution extends IntegerDistribution {
+        protected final int lowValue;
+        protected final int[] counts;
+        protected int missed;
+
+        public FixedRangeIntegerDistribution(int low, int high) {
+            lowValue = low;
+            counts = new int[high - low];
+        }
+
+        @Override
+        public void record(int value) {
+            total++;
+            final int index = value - lowValue;
+            if (index >= 0 && index < counts.length) {
+                counts[index]++;
+            } else {
+                missed++;
+            }
+        }
+
+        @Override
+        public int getCount(Integer value) {
+            final int index = value - lowValue;
+            if (index >= 0 && index < counts.length) {
+                return counts[index];
+            }
+            return missed > 0 ? -1 : 0;
+        }
+
+        @Override
+        public Map<Integer, Integer> asMap() {
+            final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
+            for (int i = 0; i != counts.length; ++i) {
+                map.put(lowValue + i, counts[i]);
+            }
+            return map;
+        }
+
+        @Override
+        public void reset() {
+            super.reset();
+            missed = 0;
+            Arrays.fill(counts, 0);
+        }
+    }
+
+    public static class FixedSetIntegerDistribution extends IntegerDistribution {
+
+        private final int[] set;
+        private final int[] count;
+        protected int missed;
+
+        public FixedSetIntegerDistribution(int[] set) {
+            // TODO: sort() and binarySearch for large sets.
+            this.set = set.clone();
+            count = new int[set.length];
+        }
+
+        @Override
+        public void record(int value) {
+            total++;
+            for (int i = 0; i < set.length; i++) {
+                if (set[i] == value) {
+                    count[i]++;
+                    return;
+                }
+            }
+            missed++;
+        }
+
+        @Override
+        public int getCount(Integer value) {
+            final int val = value;
+            for (int i = 0; i < set.length; i++) {
+                if (set[i] == val) {
+                    return count[i];
+                }
+            }
+            return missed > 0 ? -1 : 0;
+        }
+
+        @Override
+        public Map<Integer, Integer> asMap() {
+            final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
+            for (int i = 0; i != count.length; ++i) {
+                map.put(set[i], count[i]);
+            }
+            return map;
+        }
+
+        @Override
+        public void reset() {
+            super.reset();
+            missed = 0;
+            Arrays.fill(set, 0);
+            Arrays.fill(count, 0);
+        }
+    }
+
+    /**
+     * The trace integer distribution class collects an exact distribution of integer
+     * values by internally recording every integer value in order in a fixed size buffer.
+     * When the buffer fills up, its contents are sorted and then reduced into a
+     * sorted list of value/count pairs. This results in an exact distribution
+     * with a tunable size/performance tradeoff, since a larger buffer means
+     * fewer reduction steps.
+     *
+     * This implementation is <b>not thread safe</b>. It may lose updates and potentially
+     * generate exceptions if used in a multi-threaded scenario. To make updates
+     * to this distribution thread safe, {@linkplain ValueMetrics#threadSafe(IntegerDistribution) wrap}
+     * it with a {@link ThreadsafeIntegerDistribution}.
+     *
+     */
+    public static class TraceIntegerDistribution extends IntegerDistribution {
+        private final int[] buffer;
+        private int cursor;
+
+        private int[] values;
+        private int[] counts;
+
+        public TraceIntegerDistribution(int bufferSize) {
+            assert bufferSize > 0;
+            buffer = new int[bufferSize];
+        }
+
+        @Override
+        public void record(int value) {
+            total++;
+            buffer[cursor++] = value;
+            if (cursor == buffer.length) {
+                reduce();
+            }
+        }
+
+        @Override
+        public int getCount(Integer value) {
+            reduce();
+            final int index = Arrays.binarySearch(values, value);
+            if (index < 0) {
+                return 0;
+            }
+            return counts[index];
+        }
+
+        @Override
+        public Map<Integer, Integer> asMap() {
+            reduce();
+            // TODO: another map implementation might be better.
+            final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
+            if (values != null) {
+                for (int i = 0; i < values.length; i++) {
+                    map.put(values[i], counts[i]);
+                }
+            }
+            return map;
+        }
+
+        @Override
+        public void reset() {
+            super.reset();
+            cursor = 0;
+            Arrays.fill(buffer, 0);
+            Arrays.fill(values, 0);
+            Arrays.fill(counts, 0);
+        }
+
+        private void reduce() {
+            if (cursor == 0) {
+                // no recorded values to reduce
+                return;
+            }
+            // compression needed.
+            Arrays.sort(buffer, 0, cursor);
+            if (values != null) {
+                // there are already some entries. need to merge counts
+                removeExistingValues();
+                if (cursor > 0) {
+                    final int[] ovalues = values;
+                    final int[] ocounts = counts;
+                    reduceBuffer(buffer);
+                    mergeValues(ovalues, ocounts, values, counts);
+                }
+            } else {
+                // there currently aren't any entry arrays. reduce the buffer to generate the first ones.
+                reduceBuffer(buffer);
+            }
+            cursor = 0;
+        }
+
+        private void removeExistingValues() {
+            // increment counts for values that already occur in the entry arrays
+            // and leave leftover values in the buffer
+            int valuesPos = 0;
+            final int ocursor = cursor;
+            cursor = 0;
+            for (int i = 0; i < ocursor; i++) {
+                final int nvalue = buffer[i];
+                while (valuesPos < values.length && values[valuesPos] < nvalue) {
+                    valuesPos++;
+                }
+                if (valuesPos < values.length && values[valuesPos] == nvalue) {
+                    counts[valuesPos]++;
+                } else {
+                    // retain the new values in the buffer
+                    buffer[cursor++] = nvalue;
+                }
+            }
+        }
+
+        private void mergeValues(int[] avalues, int[] acounts, int[] bvalues, int[] bcounts) {
+            final int[] nvalues = new int[avalues.length + values.length];
+            final int[] ncounts = new int[acounts.length + counts.length];
+
+            int a = 0;
+            int b = 0;
+            int n = 0;
+            while (n < nvalues.length) {
+                while (a < avalues.length && (b == bvalues.length || avalues[a] < bvalues[b])) {
+                    nvalues[n] = avalues[a];
+                    ncounts[n] = acounts[a];
+                    n++;
+                    a++;
+                }
+                while (b < bvalues.length && (a == avalues.length || bvalues[b] < avalues[a])) {
+                    nvalues[n] = bvalues[b];
+                    ncounts[n] = bcounts[b];
+                    n++;
+                    b++;
+                }
+            }
+            assert n == nvalues.length && a == avalues.length && b == bvalues.length;
+            values = nvalues;
+            counts = ncounts;
+        }
+
+        private void reduceBuffer(int[] buf) {
+            // count the unique values
+            int last1 = buf[0];
+            int unique = 1;
+            for (int i1 = 1; i1 < cursor; i1++) {
+                if (buffer[i1] != last1) {
+                    unique++;
+                    last1 = buffer[i1];
+                }
+            }
+            // create the values arrays and populate them
+            values = new int[unique];
+            counts = new int[unique];
+            int last = buffer[0];
+            int count = 1;
+            int pos = 0;
+            for (int i = 1; i < cursor; i++) {
+                if (buffer[i] != last) {
+                    values[pos] = last;
+                    counts[pos] = count;
+                    pos++;
+                    count = 1;
+                    last = buffer[i];
+                } else {
+                    count++;
+                }
+            }
+            assert pos == values.length - 1;
+            values[pos] = last;
+            counts[pos] = count;
+        }
+    }
+
+    public static class HashedIntegerDistribution extends IntegerDistribution {
+        private Map<Integer, Distribution> map;
+
+        private Map<Integer, Distribution> map() {
+            if (map == null) {
+                map = new HashMap<Integer, Distribution>();
+            }
+            return map;
+        }
+
+        @Override
+        public void record(int value) {
+            total++;
+            final Integer integer = value;
+            Distribution distribution = map().get(integer);
+            if (distribution == null) {
+                distribution = new Distribution();
+                map().put(integer, distribution);
+            }
+            distribution.total++;
+        }
+        @Override
+        public int getCount(Integer value) {
+            final Distribution distribution = map().get(value);
+            if (distribution != null) {
+                return distribution.total;
+            }
+            return 0;
+        }
+
+        @Override
+        public Map<Integer, Integer> asMap() {
+            final Map<Integer, Integer> result = new HashMap<Integer, Integer>();
+            for (Map.Entry<Integer, Distribution> entry : map().entrySet()) {
+                result.put(entry.getKey(), entry.getValue().total);
+            }
+            return result;
+        }
+
+        @Override
+        public void reset() {
+            super.reset();
+            map = null;
+        }
+    }
+
+    /**
+     * This class and its descendants support profiling of individual objects. Reference
+     * equality is used here exclusively. Various implementations with different size and space
+     * tradeoffs offer various levels of accuracy.
+     *
+     */
+    public abstract static class ObjectDistribution<T> extends Distribution<T> {
+        public abstract void record(T value);
+    }
+
+    public static class HashedObjectDistribution<T> extends ObjectDistribution<T> {
+        private Map<T, Distribution> map;
+        private Map<T, Distribution> map() {
+            if (map == null) {
+                map = new IdentityHashMap<T, Distribution>();
+            }
+            return map;
+        }
+
+        public HashedObjectDistribution() {
+        }
+
+        @Override
+        public void record(T value) {
+            total++;
+            Distribution distribution = map().get(value);
+            if (distribution == null) {
+                distribution = new Distribution();
+                map().put(value, distribution);
+            }
+            distribution.total++;
+        }
+        @Override
+        public int getCount(T value) {
+            final Distribution distribution = map().get(value);
+            if (distribution != null) {
+                return distribution.total;
+            }
+            return 0;
+        }
+
+        @Override
+        public Map<T, Integer> asMap() {
+            final Map<T, Integer> result = new IdentityHashMap<T, Integer>();
+            for (Map.Entry<T, Distribution> entry : map().entrySet()) {
+                result.put(entry.getKey(), entry.getValue().total);
+            }
+            return result;
+        }
+
+        @Override
+        public void reset() {
+            super.reset();
+            map = null;
+        }
+    }
+
+    public static class FixedSetObjectDistribution<T> extends ObjectDistribution<T> {
+
+        private final T[] set;
+        private final int[] count;
+        private int missed;
+
+        public FixedSetObjectDistribution(T[] set) {
+            this.set = set.clone();
+            count = new int[set.length];
+        }
+
+        @Override
+        public void record(T value) {
+            total++;
+            for (int i = 0; i < set.length; i++) {
+                if (set[i] == value) {
+                    count[i]++;
+                    return;
+                }
+            }
+            missed++;
+        }
+        @Override
+        public int getCount(T value) {
+            for (int i = 0; i < set.length; i++) {
+                if (set[i] == value) {
+                    return count[i];
+                }
+            }
+            return missed > 0 ? -1 : 0;
+        }
+
+        @Override
+        public Map<T, Integer> asMap() {
+            final Map<T, Integer> map = new IdentityHashMap<T, Integer>();
+            for (int i = 0; i != count.length; ++i) {
+                map.put(set[i], count[i]);
+            }
+            return map;
+        }
+
+        @Override
+        public void reset() {
+            super.reset();
+            missed = 0;
+            Arrays.fill(set, 0);
+            Arrays.fill(count, 0);
+        }
+    }
+
+    /**
+     * This method creates a new distribution for the occurrence of integer values.
+     *
+     * @param name the name of the metric; if non-null, then a global metric of the specified
+     * name will be returned {@see GlobalMetrics}
+     * @param approx the approximation level that is requested. Different approximation levels
+     * have different time and space tradeoffs versus accuracy.
+     * @return a new integer distribution object that can be used to record occurrences of integers
+     */
+    public static IntegerDistribution newIntegerDistribution(String name, Approximation approx) {
+        if (name != null) {
+            final IntegerDistribution prev = GlobalMetrics.getMetric(name, IntegerDistribution.class);
+            if (prev != null) {
+                return prev;
+            }
+            return GlobalMetrics.setMetric(name, IntegerDistribution.class, createIntegerDistribution(approx));
+        }
+        return createIntegerDistribution(approx);
+    }
+
+    private static IntegerDistribution createIntegerDistribution(Approximation approx) throws ProgramError {
+        if (approx instanceof FixedApproximation) {
+            final FixedApproximation fixedApprox = (FixedApproximation) approx;
+            final int[] values = new int[fixedApprox.values.length];
+            for (int i = 0; i < values.length; i++) {
+                values[i] = (Integer) fixedApprox.values[i];
+            }
+            return new FixedSetIntegerDistribution(values);
+        }
+        if (approx instanceof IntegerRangeApproximation) {
+            final IntegerRangeApproximation fixedApprox = (IntegerRangeApproximation) approx;
+            return new FixedRangeIntegerDistribution(fixedApprox.lowValue, fixedApprox.highValue);
+        }
+        if (approx == EXACT) {
+            return new HashedIntegerDistribution();
+        }
+        if (approx instanceof IntegerTraceApproximation) {
+            final IntegerTraceApproximation traceApprox = (IntegerTraceApproximation) approx;
+            return new TraceIntegerDistribution(traceApprox.bufferSize);
+        }
+        return new HashedIntegerDistribution();
+    }
+
+    /**
+     * This is a utility method to create an integer distribution over a range of specified integers.
+     *
+     * @param name the name of the metric
+     * @param low the lowest value to be recorded in the range (inclusive)
+     * @param high the highest value to be recorded (inclusive)
+     * @return a new integer distribution object that will record exact profiles for the integers in the
+     * specified range
+     */
+    public static IntegerDistribution newIntegerDistribution(String name, int low, int high) {
+        return newIntegerDistribution(name, new IntegerRangeApproximation(low, high));
+    }
+
+    /**
+     * This utility method creates a new integer distribution with the {@link #EXACT} approximation.
+     * Note that the implementation of this integer distribution may consume excessive time and/or
+     * space for unstructured distributions.
+     *
+     * @param name the name of the metric; if non-null, then a shared, global metric of the specified name will be returned
+     * @return a new integer distribution that records an exact profile
+     */
+    public static IntegerDistribution newIntegerDistribution(String name) {
+        return newIntegerDistribution(name, EXACT);
+    }
+
+    /**
+     * This utility method creates an integer distribution that records only the specified set of
+     * values, with all other values being not recorded.
+     *
+     * @param name the name of the metric; if non-null, then a shared, global metric of the specified name will be returned
+     * @param values the set of integer values to be recored
+     * @return a new integer distribution recorder
+     */
+    public static IntegerDistribution newIntegerDistribution(String name, int[] values) {
+        final Object[] vals = new Object[values.length];
+        for (int i = 0; i < vals.length; i++) {
+            vals[i] = values[i];
+        }
+        return newIntegerDistribution(name, new FixedApproximation(vals));
+    }
+
+    /**
+     * This method creates a new distribution capable of recording individual objects.
+     *
+     * @param <T> the type of objects being profiled
+     * @param name the name of the metric; if non-null, then a shared, global metric of the specified name will be
+     * returned
+     * @param approx the approximation for the distribution
+     * @return a new distribution capable of profiling the occurrence of objects
+     */
+    public static <T> ObjectDistribution<T> newObjectDistribution(String name, Approximation approx) {
+        if (name != null) {
+            final ObjectDistribution<T> prev = Utils.cast(GlobalMetrics.getMetric(name, ObjectDistribution.class));
+            if (prev != null) {
+                return prev;
+            }
+            return Utils.cast(GlobalMetrics.setMetric(name, ObjectDistribution.class, createObjectDistribution(approx)));
+        }
+        return createObjectDistribution(approx);
+    }
+
+    private static <T> ObjectDistribution<T> createObjectDistribution(Approximation approx) {
+        if (approx instanceof FixedApproximation) {
+            final FixedApproximation fixedApprox = (FixedApproximation) approx;
+            final T[] values = Utils.cast(fixedApprox.values);
+            return new FixedSetObjectDistribution<T>(values);
+        }
+        if (approx == EXACT) {
+            return new HashedObjectDistribution<T>();
+        }
+        // default is to use the hashed object distribution
+        return new HashedObjectDistribution<T>();
+    }
+
+    /**
+     * This is a utility method to create a new object distribution that only records occurrences of
+     * objects in the specified set.
+     *
+     * @param <T> the type of the objects being profiled
+     * @param name the name of the metric
+     * @param set the set of objects for which to record exact profiling information
+     * @return a new distribution capable of producing an exact profile of the occurence of the specified objects
+     */
+    public static <T> ObjectDistribution<T> newObjectDistribution(String name, T... set) {
+        return newObjectDistribution(name, new FixedApproximation(set));
+    }
+
+    /**
+     * This is utility method to create a new object distribution with an exact profile.
+     *
+     * @param <T> the type of the objects being profiled
+     * @param name the name of metric
+     * @return a new distribution capable of producing an exact profile of the occurrences of all of the specified
+     * objects.
+     */
+    public static <T> ObjectDistribution<T> newObjectDistribution(String name) {
+        return newObjectDistribution(name, EXACT);
+    }
+
+    public static class ThreadsafeIntegerDistribution extends IntegerDistribution {
+
+        private final IntegerDistribution distribution;
+
+        public ThreadsafeIntegerDistribution(IntegerDistribution distribution) {
+            this.distribution = distribution;
+        }
+        @Override
+        public void record(int value) {
+            synchronized (distribution) {
+                distribution.record(value);
+            }
+        }
+        @Override
+        public int getCount(Integer value) {
+            synchronized (distribution) {
+                return distribution.getCount(value);
+            }
+        }
+
+        @Override
+        public Map<Integer, Integer> asMap() {
+            synchronized (distribution) {
+                return distribution.asMap();
+            }
+        }
+        @Override
+        public void reset() {
+            super.reset();
+            distribution.reset();
+        }
+
+    }
+
+    private static class ThreadsafeObjectDistribution<T> extends ObjectDistribution<T> {
+
+        private final ObjectDistribution<T> distribution;
+
+        ThreadsafeObjectDistribution(ObjectDistribution<T> distribution) {
+            this.distribution = distribution;
+        }
+        @Override
+        public void record(T value) {
+            synchronized (distribution) {
+                distribution.record(value);
+            }
+        }
+        @Override
+        public int getCount(T value) {
+            synchronized (distribution) {
+                return distribution.getCount(value);
+            }
+        }
+
+        @Override
+        public Map<T, Integer> asMap() {
+            synchronized (distribution) {
+                return distribution.asMap();
+            }
+        }
+    }
+
+    /**
+     * This method creates a wrapper around the specified integer distribution that ensures
+     * access to the distribution is synchronized.
+     *
+     * @param distribution the distribution to wrap in a synchronization
+     * @return a synchronized view of the distribution
+     */
+    public static IntegerDistribution threadSafe(IntegerDistribution distribution) {
+        return new ThreadsafeIntegerDistribution(distribution);
+    }
+
+    /**
+     * This method creates a wrapper around the specified integer distribution that ensures
+     * access to the distribution is synchronized.
+     *
+     * @param distribution the distribution to wrap in a synchronization
+     * @return a synchronized view of the distribution
+     */
+    public static <T> ObjectDistribution<T> threadSafe(ObjectDistribution<T> distribution) {
+        return new ThreadsafeObjectDistribution<T>(distribution);
+    }
+}