public interface DominatorBenchmark {

  void performBenchmark(Blackhole bh, List<?> sampledGraphsNative);

  List<?> convertDataToNativeFormat(List<ISet> sampledGraphs);

} @BenchmarkMode(Mode.SingleShotTime)
@OutputTimeUnit(TimeUnit.SECONDS)
@State(Scope.Thread)
public class JmhCfgDominatorBenchmarks {

  @Param
  public DominatorBenchmarkEnum dominatorBenchmarkEnum;

  /*
   * (for (i <- 0 to 23) yield s"'${Math.pow(2, i).toInt}'").mkString(", ").replace("'", "\"")
   *
   * Note: total entries in DATA_SET_FULL_FILE_NAME: 5018
   */
  @Param({"4096", "2048", "1024", "512", "256", "128"})
  protected int size;

  @Param({"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"})
  protected int run = 0;

  private DominatorBenchmark dominatorBenchmark;

  private final String DATA_SET_FULL_FILE_NAME = "data/wordpress-cfgs-as-graphs.bin";
  private IMap DATA_SET_FULL;

  public static final String DATA_SET_SINGLE_FILE_NAME = "data/single.bin";
  private ISet DATA_SET_SINGLE;

  private List<ISet> sampledGraphs;
  private List<?> sampledGraphsNative;

  @Setup(Level.Trial)
  public void setUp() throws Exception {
    System.out.println("\n>> setUp >>");

    deserializeFullDataSet();
    setUpTestSetWithRandomContent(size, run);

    // convert data to remove PDB dependency
    dominatorBenchmark = dominatorBenchmarkEnum.getBenchmark();
    sampledGraphsNative = dominatorBenchmark.convertDataToNativeFormat(sampledGraphs);

    System.out.println("<< setUp <<");
  }

  protected void deserializeFullDataSet() {
    final IValueFactory vf = io.usethesource.vallang.impl.persistent.ValueFactory.getInstance();

    try {
      final int bufferSize = 512 * 1024 * 1024;

      DATA_SET_FULL = (IMap) new BinaryValueReader().read(vf,
          new BufferedInputStream(new FileInputStream(DATA_SET_FULL_FILE_NAME), bufferSize));
    } catch (IOException e) {
      throw new RuntimeException(e);
    }

    // System.err.println("Global data initialized.");
    // System.err.println("Total number of entries: " +
    // DATA_SET_FULL.size());
    // System.err.println();
  }

  protected void deserializeSingleDataSet() {
    final IValueFactory vf = io.usethesource.vallang.impl.persistent.ValueFactory.getInstance();

    try {
      final int bufferSize = 512 * 1024 * 1024;

      DATA_SET_SINGLE = (ISet) new BinaryValueReader().read(vf,
          new BufferedInputStream(new FileInputStream(DATA_SET_SINGLE_FILE_NAME), bufferSize));
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  protected void setUpTestSetWithRandomContent(int size, int run) throws Exception {
    if (size == 1) {
      deserializeSingleDataSet();
      sampledGraphs = Arrays.asList(DATA_SET_SINGLE);
    }

    // int seedForThisTrial = BenchmarkUtils.seedFromSizeAndRun(size, run);

    // same seed for different sizes to achieve subsume relationship
    int seedForThisTrial = BenchmarkUtils.seedFromSizeAndRun(0, run);

    Random rand = new Random(seedForThisTrial);
    System.out.println(String.format("Seed for this trial: %d.", seedForThisTrial));

    // select sample based on random indices
    Set<Integer> sampledIndices = new HashSet<>(size * 2);

    while (sampledIndices.size() <= size) {
      sampledIndices.add(rand.nextInt(DATA_SET_FULL.size()));
    }

    // sample data
    sampledGraphs = new ArrayList<>(size);

    int dataSetCursor = 0;
    for (Iterator<IValue> dataSetIterator = DATA_SET_FULL.iterator(); dataSetIterator
        .hasNext(); dataSetCursor++) {
      if (sampledIndices.contains(dataSetCursor)) {
        IValue mapKey = dataSetIterator.next();
        ISet mapValue = (ISet) DATA_SET_FULL.get(mapKey);

        // /**** REMOVE ANNOTATIONS ***/
        // IValueFactory vf = io.usethesource.vallang.impl.persistent.ValueFactory.getInstance();
        //
        // ISetWriter bldr = vf.setWriter();
        // for (IValue untypedTuple : mapValue) {
        // ITuple tuple = (ITuple) untypedTuple;
        //
        // IConstructor keyCleaned = ((IConstructor)
        // tuple.get(0)).asAnnotatable().removeAnnotations();
        // IConstructor valCleaned = ((IConstructor)
        // tuple.get(1)).asAnnotatable().removeAnnotations();
        //
        // ITuple cleanedTuple = vf.tuple(keyCleaned, valCleaned);
        //
        // bldr.insert(cleanedTuple);
        // }
        // mapValue = bldr.done();
        // /***************************/

        sampledGraphs.add(mapValue);
      } else {
        dataSetIterator.next();
      }
    }
  }

  public static long memoryInBytes_multimap = 0;
  public static long memoryInBytes_mapWithNestedSets = 0;

  public static long unique = 0;
  public static long tuples = 0;
  public static long tuples_one2one = 0;

  @Benchmark
  public void timeDominatorCalculation(Blackhole bh) {
    dominatorBenchmark.performBenchmark(bh, sampledGraphsNative);
  }

  @Benchmark
  public void timeDominatorCalculationInstrumented(Blackhole bh) {
    memoryInBytes_multimap = 0;
    memoryInBytes_mapWithNestedSets = 0;

    unique = 0;
    tuples = 0;
    tuples_one2one = 0;

    dominatorBenchmark.performBenchmark(bh, sampledGraphsNative);

    System.out.println("memoryInBytes_multimap:          " + memoryInBytes_multimap);
    System.out.println("memoryInBytes_mapWithNestedSets: " + memoryInBytes_mapWithNestedSets);

    // System.out.println("unique:" + unique);
    // System.out.println("tuples:" + tuples);
    // System.out.println("tuples_one2one:" + tuples_one2one);
    //
    // System.out.println("ratio:" + 1.0 * tuples / unique);

    System.out.println(String.format("csv;unique;tuples;tuples_one2one"));
    System.out.println(String.format("csv;%d;%d;%d", unique, tuples, tuples_one2one));
  }

  public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
        .include(
            ".*" + JmhCfgDominatorBenchmarks.class.getSimpleName() + ".(timeDominatorCalculation$)")
        .warmupIterations(0).measurementIterations(1).mode(Mode.AverageTime).forks(1)
        .timeUnit(TimeUnit.SECONDS)
//        .param("size", "1")
//        .param("size", "16")
//        .param("size", "128")
//        .param("size", "1024")
//        .param("size", "2048")
        .param("size", "4096")
        .param("run", "0")
//        .param("run", "1")
//        .param("run", "2")
//        .param("dominatorBenchmarkEnum", "CHART")
//        // .param("dominatorBenchmarkEnum", "CLOJURE_LAZY")
//        // .param("dominatorBenchmarkEnum", "SCALA")
//        // .param("dominatorBenchmarkEnum", "VF_CHAMP_MULTIMAP_INSTRUMENTED")
//        // .param("dominatorBenchmarkEnum", "VF_CHAMP_MULTIMAP_HHAMT_NEW")
//        .param("dominatorBenchmarkEnum", "VF_CHAMP_MULTIMAP_HCHAMP")
        .param("dominatorBenchmarkEnum", "VF_CHAMP_MULTIMAP_HHAMT")
//        .param("dominatorBenchmarkEnum", "VF_CHAMP_MULTIMAP_HHAMT_INTERLINKED")
//        .param("dominatorBenchmarkEnum", "VF_CHAMP_MULTIMAP_HHAMT_SPECIALIZED")
//        // .param("dominatorBenchmarkEnum", "VF_CHAMP_MULTIMAP_HHAMT_SPECIALIZED_INTERLINKED")
//        // .param("dominatorBenchmarkEnum", "VF_CHAMP_MULTIMAP_HHAMT_SPECIALIZED_INTERLINKED_INSTR")
//        // .output("JmhCfgDominatorBenchmarks.log")
        .shouldDoGC(true).build();

    new Runner(opt).run();
  }

} public final class Timing {

  private long start;

  public Timing() {
    super();
  }

  public void start() {
    start = getCpuTime();
  }

  public long duration() {
    long now = getCpuTime();
    long diff = now - start;
    start = now;
    return diff;
  }

  public static long getCpuTime() {
    ThreadMXBean bean = ManagementFactory.getThreadMXBean();
    return bean.isCurrentThreadCpuTimeSupported() ?
        bean.getCurrentThreadCpuTime() : 0L;
  }

  /**
   * Get user time in nanoseconds.
   */
  public static long getUserTime() {
    ThreadMXBean bean = ManagementFactory.getThreadMXBean();
    return bean.isCurrentThreadCpuTimeSupported() ?
        bean.getCurrentThreadUserTime() : 0L;
  }

  /**
   * Get system time in nanoseconds.
   */
  public static long getSystemTime() {
    ThreadMXBean bean = ManagementFactory.getThreadMXBean();
    return bean.isCurrentThreadCpuTimeSupported() ?
        (bean.getCurrentThreadCpuTime() - bean.getCurrentThreadUserTime()) : 0L;
  }
} public static final String DATA_SET_SINGLE_FILE_NAME = "data/single.bin"; public final static Set.Immutable EMPTY = Immutable.of(); public static <K extends Iterable<?>, T> Set.Immutable<T> carrier(Set.Immutable<K> set1) {
  Set.Transient<Object> builder = Transient.of();

  for (K iterable : set1) {
    for (Object nested : iterable) {
      builder.__insert(nested);
    }
  }

  return (Set.Immutable<T>) builder.freeze();
} public static <K> Set.Immutable<K> intersect(Set.Immutable<Set.Immutable<K>> sets) {
  if (sets == null || sets.isEmpty() || sets.contains(EMPTY)) {
    return EMPTY;
  }

  Set.Immutable<K> first = sets.iterator().next();
  sets = sets.__remove(first);

  Set.Immutable<K> result = first;
  for (Set.Immutable<K> elem : sets) {
    result = Util_Default_Instrumented.intersect(result, elem);
  }

  return result;
} public static <K extends IValue> Set.Immutable<K> project(Set.Immutable<ITuple> set1, int field) {
  Set.Transient<K> builder = Transient.of();

  for (ITuple tuple : set1) {
    builder.__insert((K) tuple.select(field));
  }

  return builder.freeze();
} public static <K> Set.Immutable<K> subtract(Set.Immutable<K> set1, Set.Immutable<K> set2) {
  if (set1 == null && set2 == null) {
    return Immutable.of();
  }
  if (set1 == set2) {
    return Immutable.of();
  }
  if (set1 == null) {
    return Immutable.of();
  }
  if (set2 == null) {
    return set1;
  }

  final Set.Transient<K> tmp = set1.asTransient();
  boolean modified = false;

  for (K key : set2) {
    if (tmp.__remove(key)) {
      modified = true;
    }
  }

  if (modified) {
    return tmp.freeze();
  } else {
    return set1;
  }
} public static <K, V> io.usethesource.capsule.Map.Immutable<K, Set.Immutable<V>> toMap(
    Set.Immutable<ITuple> st) {
  Map<K, Set.Transient<V>> hm = new HashMap<>();

  for (ITuple t : st) {
    K key = (K) t.get(0);
    V val = (V) t.get(1);
    Set.Transient<V> wValSet = hm.get(key);
    if (wValSet == null) {
      wValSet = Transient.of();
      hm.put(key, wValSet);
    }
    wValSet.__insert(val);
  }

  io.usethesource.capsule.Map.Transient<K, Set.Immutable<V>> w =
      io.usethesource.capsule.Map.Transient.of();
  for (K k : hm.keySet()) {
    w.__put(k, hm.get(k).freeze());
  }
  return w.freeze();
} public static <K, V> SetMultimap.Immutable<K, V> toMultimap(Set.Immutable<ITuple> st) {
  SetMultimap.Transient<K, V> mm = TrieSetMultimap_HHAMT.transientOf();

  for (ITuple t : st) {
    K key = (K) t.get(0);
    V val = (V) t.get(1);

    mm.__insert(key, val);
  }

  return mm.freeze();
} public static <K> Set.Immutable<K> union(Set.Immutable<K> set1, Set.Immutable<K> set2) {
  if (set1 == null && set2 == null) {
    return Immutable.of();
  }
  if (set1 == null) {
    return set2;
  }
  if (set2 == null) {
    return set1;
  }

  if (set1 == set2) {
    return set1;
  }

  final Set.Immutable<K> smaller;
  final Set.Immutable<K> bigger;

  final Set.Immutable<K> unmodified;

  if (set2.size() >= set1.size()) {
    unmodified = set2;
    smaller = set1;
    bigger = set2;
  } else {
    unmodified = set1;
    smaller = set2;
    bigger = set1;
  }

  final Set.Transient<K> tmp = bigger.asTransient();
  boolean modified = false;

  for (K key : smaller) {
    if (tmp.__insert(key)) {
      modified = true;
    }
  }

  if (modified) {
    return tmp.freeze();
  } else {
    return unmodified;
  }
}
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import dom.DominatorBenchmark;
import dom.JmhCfgDominatorBenchmarks;
import io.usethesource.capsule.Set;
import io.usethesource.capsule.Set.Immutable;
import io.usethesource.capsule.Set.Transient;
import io.usethesource.capsule.SetMultimap;
import io.usethesource.capsule.experimental.multimap.TrieSetMultimap_HHAMT;
import io.usethesource.vallang.IConstructor;
import io.usethesource.vallang.IMap;
import io.usethesource.vallang.IMapWriter;
import io.usethesource.vallang.ISet;
import io.usethesource.vallang.ISetWriter;
import io.usethesource.vallang.ITuple;
import io.usethesource.vallang.IValue;
import io.usethesource.vallang.IValueFactory;
import io.usethesource.vallang.io.old.BinaryValueReader;
import org.openjdk.jmh.infra.Blackhole;
import org.rascalmpl.interpreter.utils.Timing;
import static dom.AllDominatorsRunner.DATA_SET_SINGLE_FILE_NAME;
import static dom.multimap.Util_Default_Instrumented.EMPTY;
import static dom.multimap.Util_Default_Instrumented.carrier;
import static dom.multimap.Util_Default_Instrumented.intersect;
import static dom.multimap.Util_Default_Instrumented.project;
import static dom.multimap.Util_Default_Instrumented.subtract;
import static dom.multimap.Util_Default_Instrumented.toMap;
import static dom.multimap.Util_Default_Instrumented.toMultimap;
import static dom.multimap.Util_Default_Instrumented.union;
/**
 * Copyright (c) Michael Steindorfer <Centrum Wiskunde & Informatica> and Contributors.
 * All rights reserved.
 *
 * This file is licensed under the BSD 2-Clause License, which accompanies this project
 * and is available under https://opensource.org/licenses/BSD-2-Clause.
 */
package dom.multimap;




public class DominatorsSetMultimap_Default_Instrumented implements DominatorBenchmark {

  private Set.Immutable setofdomsets(SetMultimap.Immutable dom, Set.Immutable preds) {
    Set.Transient result = Transient.of();

    for (Object p : preds) {
      Set.Immutable ps = dom.get(p);

      result.__insert(ps == null ? EMPTY : ps);
    }

    return result.freeze();
  }

  public Set.Immutable<IConstructor> top(Set.Immutable<ITuple> graph) {
    return subtract(project(graph, 0), project(graph, 1));
  }

  public IConstructor getTop(Set.Immutable<ITuple> graph) {
    for (IConstructor candidate : top(graph)) {
      switch (candidate.getName()) {
        case "methodEntry":
        case "functionEntry":
        case "scriptEntry":
          return candidate;
      }
    }

    throw new NoSuchElementException("No candidate found.");
  }

  public SetMultimap.Immutable<IConstructor, IConstructor> calculateDominators(
      Set.Immutable<ITuple> graph) {

    // long totalNrOfUniqueKeys = 0;
    // long totalNrOfTuple = 0;

    // long unique = 0;
    // long tuples = 0;
    // long one2one = 0;

    IConstructor n0 = getTop(graph);
    Set.Immutable<IConstructor> nodes = carrier(graph);

    SetMultimap.Immutable<IConstructor, IConstructor> preds = toMultimap(project(graph, 1, 0));

    {

      Predicate<Object> predicate = Predicates.not(Predicates.instanceOf(IValue.class));

      JmhCfgDominatorBenchmarks.memoryInBytes_multimap +=
          objectexplorer.MemoryMeasurer.measureBytes(preds, predicate);
      // Footprint memoryFootprint_multimap = objectexplorer.ObjectGraphMeasurer.measure(preds,
      // predicate);

      Object mapWithNestedSets = toMap(project(graph, 1, 0));

      JmhCfgDominatorBenchmarks.memoryInBytes_mapWithNestedSets +=
          objectexplorer.MemoryMeasurer.measureBytes(mapWithNestedSets, predicate);
      // Footprint memoryFootprint_mapWithNestedSets =
      // objectexplorer.ObjectGraphMeasurer.measure(mapWithNestedSets, predicate);
    }

    Iterator<Entry<IConstructor, Object>> it = preds.nativeEntryIterator();

    while (it.hasNext()) {
      Entry<IConstructor, Object> tuple = it.next();

      Object singletonOrSet = tuple.getValue();

      if (singletonOrSet instanceof Set.Immutable) {
        JmhCfgDominatorBenchmarks.unique++;
        JmhCfgDominatorBenchmarks.tuples += ((Set.Immutable) singletonOrSet).size();
      } else {
        JmhCfgDominatorBenchmarks.unique++;
        JmhCfgDominatorBenchmarks.tuples++;
        JmhCfgDominatorBenchmarks.tuples_one2one++;
      }
    }

    SetMultimap.Transient<IConstructor, IConstructor> w = TrieSetMultimap_HHAMT.transientOf();
    w.__insert(n0, n0);
    // JmhCfgDominatorBenchmarks.unique++;
    // JmhCfgDominatorBenchmarks.tuples++;
    // JmhCfgDominatorBenchmarks.one2one++;
    for (IConstructor n : nodes.__remove(n0)) {
      w.__put(n, nodes); // TODO: implement method to put a whole set at once!
      // JmhCfgDominatorBenchmarks.unique++;
      // JmhCfgDominatorBenchmarks.tuples+=nodes.size();
    }
    SetMultimap.Immutable<IConstructor, IConstructor> dom = w.freeze();

    SetMultimap.Immutable<IConstructor, IConstructor> prev = TrieSetMultimap_HHAMT.of();

    /*
     * solve (dom) for (n <- nodes) dom[n] = {n} + intersect({dom[p] | p <- preds[n]?{}});
     */
    while (!prev.equals(dom)) {
      prev = dom;
      // System.out.println(prev.size());

      SetMultimap.Transient<IConstructor, IConstructor> newDom =
          TrieSetMultimap_HHAMT.transientOf();

      for (IConstructor n : nodes) {
        Set.Immutable ps = preds.get(n);
        if (ps == null) {
          ps = EMPTY;
        }
        // System.out.println(" ps: " + ps.size());
        Set.Immutable<Set.Immutable<IConstructor>> sos = setofdomsets(dom, ps);
        // System.out.println(" sos: " + sos.size());
        Set.Immutable<IConstructor> intersected = intersect(sos);
        // System.out.println(" intersected: " + intersected.size());

        if (!intersected.isEmpty()) {
          Set.Immutable<IConstructor> newValue = union(intersected, Immutable.of(n));
          newDom.__put(n, newValue); // TODO: implement method to put a whole set at once!
          // JmhCfgDominatorBenchmarks.unique++;
          // JmhCfgDominatorBenchmarks.tuples+=newValue.size();
        } else {
          newDom.__insert(n, n); // TODO: implement method to put a
          // whole set at once!
          // JmhCfgDominatorBenchmarks.unique++;
          // JmhCfgDominatorBenchmarks.tuples++;
          // JmhCfgDominatorBenchmarks.one2one++;
        }
      }

      dom = newDom.freeze();
      // return dom; // TODO: remove
    }

    // System.out.println("unique:" + unique);
    // System.out.println("tuples:" + tuples);
    // System.out.println("one2one:" + one2one);
    //
    // System.out.println("ratio:" + tuples / unique);

    return dom;
  }

  public static void main(String[] args) throws FileNotFoundException, IOException {
    testOne();
    // assertDominatorsEqual();
  }

  public static IMap testOne() throws IOException, FileNotFoundException {
    IValueFactory vf = io.usethesource.vallang.impl.persistent.ValueFactory.getInstance();

    ISet data =
        (ISet) new BinaryValueReader().read(vf, new FileInputStream(DATA_SET_SINGLE_FILE_NAME));