MapBench.java

/*
 * Licensed to Elasticsearch under one or more contributor
 * license agreements. See the NOTICE file distributed with
 * this work for additional information regarding copyright
 * ownership. Elasticsearch licenses this file to you under
 * the Apache License, Version 2.0 (the "License"); you may
 * not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.elasticsearch.benchmark;

import org.elasticsearch.common.unit.TimeValue;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.TimeUnit;

public class MapBench {

    private static interface AMap {

        Object get(Object key);
        void put(Object key, Object value);

    }

    // Adds are constant-time
    private static class JavaCHM implements AMap {

        private final ConcurrentMap<Object, Object> map = new ConcurrentHashMap<>();

        @Override
        public Object get(Object key) {
            return map.get(key);
        }

        @Override
        public void put(Object key, Object value) {
        }

    }

    // Adds are linear
    private static class ImmutableMap implements AMap {

        private Map<Object, Object> map = new HashMap<Object, Object>();

        @Override
        public Object get(Object key) {
            return map.get(key);
        }

        @Override
        public void put(Object key, Object value) {
            map = new HashMap<>(map);
            map.put(key, value);
            map = Collections.unmodifiableMap(map);
        }

    }

    // Adds are O(sqrt(n))
    private static class DelayedImmutableMap implements AMap {

        private Map<Object, Object> main = new HashMap<Object, Object>();
        private Map<Object, Object> delta = new HashMap<Object, Object>();
        private int maxDeltaSize = 10;

        @Override
        public Object get(Object key) {
            if (delta.containsKey(key)) {
                return delta.get(key);
            } else {
                return main.get(key);
            }
        }

        @Override
        public void put(Object key, Object value) {
            if (delta.size() > maxDeltaSize) {
                main = new HashMap<>(main);
                main.putAll(delta);
                main.put(key,  value);
                main = Collections.unmodifiableMap(main);
                delta = new HashMap<Object, Object>();
                // sqrt is the optimal maximum size
                // the amortized cost of adding an element into this map is O(d + n/d) where
                // n is the total size and d the maximum size of the deltas
                // the minimum value happens when d = sqrt(n)
                maxDeltaSize = (int) Math.sqrt(main.size());
            } else {
                delta = new HashMap<>(delta);
                delta.put(key, value);
                delta = Collections.unmodifiableMap(delta);
            }
        }

    }

    public static void benchAdd(AMap map, Random r, Object[] objects, int iterations) {
        for (int i = 0; i < iterations; ++i) {
            final Object key = objects[r.nextInt(objects.length)];
            map.put(key, key);
        }
    }

    public static void main(String[] args) {
        final Object[] objects = new Object[100000];
        for (int i = 0; i < objects.length; ++i) {
            objects[i] = i;
        }
        for (int i = 0; i < 5; ++i) {
            for (AMap map : Arrays.asList(new JavaCHM(), new ImmutableMap(), new DelayedImmutableMap())) {
                Random r = new Random(0);
                long start = System.nanoTime();
                benchAdd(map, r, objects, 50000);
                long end = System.nanoTime();

                int h = 0;
                for (Object o : objects) {
                    Object v = map.get(o);
                    if (v != null) {
                        h += v.hashCode();
                    }
                }
                System.out.println(map + " " + new TimeValue(end - start, TimeUnit.NANOSECONDS) + " hash=" + h);
            }
        }
    }

}