benchmark-ArrayDequeue-LinkedList.java

package org.sample;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.infra.Blackhole;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.StringJoiner;

import static java.util.Collections.singletonMap;

public class MyBenchmark {

    @State(Scope.Benchmark)
    public static class MyMap {

        static Map<String, Object> map;

        static {
            Object value = "Marios";
            map = new HashMap<>();
            map.put("a", singletonMap("b", singletonMap("c", singletonMap("d", singletonMap("e", singletonMap("f", singletonMap("g", value)))))));
            map.put("a.b", singletonMap("c.d", singletonMap("e", singletonMap("f", singletonMap("g", value)))));
            map.put("a.b.c", singletonMap("b", singletonMap("c.d.e", singletonMap("f", singletonMap("g", value)))));
            map.put("a.b.c.d", singletonMap("b", singletonMap("c.d.e.f", singletonMap("g", value))));
            map.put("a.b.c.d.e", singletonMap("b", singletonMap("c.d.e.f.g", value)));
            map.put("a.b.c.d.e.f", singletonMap("b", singletonMap("c", singletonMap("d.e", singletonMap("f", singletonMap("g", value))))));
            map.put("a.b.c.d.e.f.g", singletonMap("b", singletonMap("c", singletonMap("d.e.f", singletonMap("g", value)))));
        }
    }

    @Benchmark
    public void testArrayDequeue(Blackhole bh) {
        bh.consume(extractFromSourceDequeue(new String[] {"a", "b", "c", "d", "e", "f", "g"}, MyMap.map));
    }

    @Benchmark
    public void testLinkedList(Blackhole bh) {
        bh.consume(extractFromSourceLinkedList(new String[] {"a", "b", "c", "d", "e", "f", "g"}, MyMap.map));
    }

    private static Object extractFromSourceDequeue(String[] path, Map<String, Object> map) {
        Object value = null;
        Deque<Map<String, Object>> queue = new ArrayDeque<>();
        Deque<Integer> idxQueue = new ArrayDeque<>();

        queue.add(map);
        idxQueue.add(-1);

        while (!queue.isEmpty()) {
            int idx = idxQueue.removeLast();
            Map<String, Object> subMap = queue.removeLast();

            StringJoiner sj = new StringJoiner(".");
            for (int i = idx + 1; i < path.length; i++) {
                sj.add(path[i]);
                Object node = subMap.get(sj.toString());
                if (node instanceof Map) {
                    // Add the sub-map to the queue along with the current path index
                    queue.add((Map<String, Object>) node);
                    idxQueue.add(i);
                } else if (node != null) {
                    value = node;
                }
            }
        }
        return value;
    }

    private static Object extractFromSourceLinkedList(String[] path, Map<String, Object> map) {
        Object value = null;
        Deque<Map<String, Object>> queue = new LinkedList<>();
        Deque<Integer> idxQueue = new LinkedList<>();

        queue.add(map);
        idxQueue.add(-1);

        while (!queue.isEmpty()) {
            int idx = idxQueue.removeLast();
            Map<String, Object> subMap = queue.removeLast();

            StringJoiner sj = new StringJoiner(".");
            for (int i = idx + 1; i < path.length; i++) {
                sj.add(path[i]);
                Object node = subMap.get(sj.toString());
                if (node instanceof Map) {
                    // Add the sub-map to the queue along with the current path index
                    queue.add((Map<String, Object>) node);
                    idxQueue.add(i);
                } else if (node != null) {
                    value = node;
                }
            }
        }
        return value;
    }
}