ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/DefaultDirectedGraphBenchmark.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF 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.apache.calcite.benchmarks;

import org.apache.calcite.util.graph.DefaultDirectedGraph;
import org.apache.calcite.util.graph.DefaultEdge;
import org.apache.calcite.util.graph.DirectedGraph;

import com.google.common.collect.Lists;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.concurrent.TimeUnit;

/**
 * Benchmarks for {@link org.apache.calcite.util.graph.DefaultDirectedGraph}.
 */
public class DefaultDirectedGraphBenchmark {

  /** Node in the graph. */
  private static class Node {
    final int id;

    private Node(int id) {
      this.id = id;
    }

    @Override public boolean equals(Object o) {
      return o == this
          || o instanceof Node
          && ((Node) o).id == id;
    }

    @Override public int hashCode() {
      return Objects.hash(id);
    }
  }

  /**
   * State object for the benchmarks.
   */
  @State(Scope.Benchmark)
  public static class GraphState {

    static final int NUM_LAYERS = 8;

    DirectedGraph<Node, DefaultEdge> graph;

    List<Node> nodes;

    List<Node> tenNodes;
    List<Node> twentyNodes;
    List<Node> thirtyNodes;
    List<Node> fortyNodes;
    List<Node> fiftyNodes;
    List<Node> sixtyNodes;
    List<Node> seventyNodes;
    List<Node> eightyNodes;
    List<Node> ninetyNodes;

    @Setup(Level.Invocation)
    public void setUp() {
      nodes = new ArrayList<>();

      // create a binary tree
      graph = DefaultDirectedGraph.create();

      // create nodes
      int curId = 1;
      Node root = new Node(curId++);
      nodes.add(root);
      graph.addVertex(root);
      List<Node> prevLayerNodes = Lists.newArrayList(root);

      for (int i = 1; i < NUM_LAYERS; i++) {
        List<Node> curLayerNodes = new ArrayList<>();
        for (Node node : prevLayerNodes) {
          Node leftChild = new Node(curId++);
          Node rightChild = new Node(curId++);

          curLayerNodes.add(leftChild);
          curLayerNodes.add(rightChild);

          nodes.add(leftChild);
          nodes.add(rightChild);

          graph.addVertex(leftChild);
          graph.addVertex(rightChild);

          graph.addEdge(node, leftChild);
          graph.addEdge(node, rightChild);
        }
        prevLayerNodes = curLayerNodes;
      }

      int tenNodeCount = (int) (nodes.size() * 0.1);
      int twentyNodeCount = (int) (nodes.size() * 0.2);
      int thirtyNodeCount = (int) (nodes.size() * 0.3);
      int fortyNodeCount = (int) (nodes.size() * 0.4);
      int fiftyNodeCount = (int) (nodes.size() * 0.5);
      int sixtyNodeCount = (int) (nodes.size() * 0.6);
      int seventyNodeCount = (int) (nodes.size() * 0.7);
      int eightyNodeCount = (int) (nodes.size() * 0.8);
      int ninetyNodeCount = (int) (nodes.size() * 0.9);
      tenNodes = nodes.subList(0, tenNodeCount);
      twentyNodes = nodes.subList(0, twentyNodeCount);
      thirtyNodes = nodes.subList(0, thirtyNodeCount);
      fortyNodes = nodes.subList(0, fortyNodeCount);
      fiftyNodes = nodes.subList(0, fiftyNodeCount);
      sixtyNodes = nodes.subList(0, sixtyNodeCount);
      seventyNodes = nodes.subList(0, seventyNodeCount);
      eightyNodes = nodes.subList(0, eightyNodeCount);
      ninetyNodes = nodes.subList(0, ninetyNodeCount);
    }
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public int getInwardEdgesBenchmark(GraphState state) {
    int sum = 0;
    int curId = 1;
    for (int i = 0; i < GraphState.NUM_LAYERS; i++) {
      // get the first node in each layer
      Node curNode = state.nodes.get(curId - 1);
      sum += state.graph.getInwardEdges(curNode).size();
      curId *= 2;
    }
    return sum;
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public int getOutwardEdgesBenchmark(GraphState state) {
    int sum = 0;
    int curId = 1;
    for (int i = 0; i < GraphState.NUM_LAYERS; i++) {
      // get the first node in each layer
      Node curNode = state.nodes.get(curId - 1);
      sum += state.graph.getOutwardEdges(curNode).size();
      curId *= 2;
    }
    return sum;
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public boolean addVertexBenchmark(GraphState state) {
    return state.graph.addVertex(new Node(100));
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public DefaultEdge addEdgeBenchmark(GraphState state) {
    return state.graph.addEdge(state.nodes.get(0), state.nodes.get(5));
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public DefaultEdge getEdgeBenchmark(GraphState state) {
    return state.graph.getEdge(state.nodes.get(0), state.nodes.get(1));
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public boolean removeEdgeBenchmark(GraphState state) {
    return state.graph.removeEdge(state.nodes.get(0), state.nodes.get(1));
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices10Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.tenNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices20Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.twentyNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices30Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.thirtyNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices40Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.fortyNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices50Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.fiftyNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices60Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.sixtyNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices70Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.seventyNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices80Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.eightyNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices90Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.ninetyNodes);
  }

  @Benchmark
  @BenchmarkMode(Mode.AverageTime)
  @OutputTimeUnit(TimeUnit.MICROSECONDS)
  public void removeAllVertices100Benchmark(GraphState state) {
    state.graph.removeAllVertices(state.nodes);
  }

  public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
        .include(DefaultDirectedGraphBenchmark.class.getName())
        .forks(1)
        .build();

    new Runner(opt).run();
  }
}