src/main/java/com/google/devtools/build/lib/runtime/CriticalPathComputer.java - bazel - Git at Google

 // Copyright 2014 Google Inc. All rights reserved.
 //
 // Licensed 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 com.google.devtools.build.lib.runtime;

 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Maps;
 import com.google.common.eventbus.Subscribe;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionCompletionEvent;
 import com.google.devtools.build.lib.actions.ActionMetadata;
 import com.google.devtools.build.lib.actions.ActionMiddlemanEvent;
 import com.google.devtools.build.lib.actions.ActionStartedEvent;
 import com.google.devtools.build.lib.actions.Actions;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.CachedActionEvent;
 import com.google.devtools.build.lib.util.Clock;

 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.PriorityQueue;
 import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.TimeUnit;

 import javax.annotation.concurrent.ThreadSafe;

 /**
  * Computes the critical path in the action graph based on events published to the event bus.
  *
  * <p>After instantiation, this object needs to be registered on the event bus to work.
  */
 @ThreadSafe
 public abstract class CriticalPathComputer<C extends AbstractCriticalPathComponent<C>,
                                            A extends AggregatedCriticalPath<C>> {

   /** Number of top actions to record. */
   static final int SLOWEST_COMPONENTS_SIZE = 30;
   // outputArtifactToComponent is accessed from multiple event handlers.
   protected final ConcurrentMap<Artifact, C> outputArtifactToComponent = Maps.newConcurrentMap();

   /** Maximum critical path found. */
   private C maxCriticalPath;
   private final Clock clock;

   /**
    * The list of slowest individual components, ignoring the time to build dependencies.
    *
    * <p>This data is a useful metric when running non highly incremental builds, where multiple
    * tasks could run un parallel and critical path would only record the longest path.
    */
   private final PriorityQueue<C> slowestComponents = new PriorityQueue<>(SLOWEST_COMPONENTS_SIZE,
       new Comparator<C>() {
         @Override
         public int compare(C o1, C o2) {
           return Long.compare(o1.getActionWallTime(), o2.getActionWallTime());
         }
       }
   );

   private final Object lock = new Object();

   protected CriticalPathComputer(Clock clock) {
     this.clock = clock;
     maxCriticalPath = null;
   }

   /**
    * Creates a critical path component for an action.
    * @param action the action for the critical path component
    * @param startTimeMillis time when the action started to run
    */
   protected abstract C createComponent(Action action, long startTimeMillis);

   /**
    * Return the critical path stats for the current command execution.
    *
    * <p>This method allows us to calculate lazily the aggregate statistics of the critical path,
    * avoiding the memory and cpu penalty for doing it for all the actions executed.
    */
   public abstract A aggregate();

   /**
    * Record an action that has started to run.
    *
    * @param event information about the started action
    */
   @Subscribe
   public void actionStarted(ActionStartedEvent event) {
     Action action = event.getAction();
     C component = createComponent(action, TimeUnit.NANOSECONDS.toMillis(event.getNanoTimeStart()));
     for (Artifact output : action.getOutputs()) {
       C old = outputArtifactToComponent.put(output, component);
       Preconditions.checkState(old == null, "Duplicate output artifact found. This could happen"
           + " if a previous event registered the action %s. Artifact: %s", action, output);
     }
   }

   /**
    * Record a middleman action execution. Even if middleman are almost instant, we record them
    * because they depend on other actions and we need them for constructing the critical path.
    *
    * <p>For some rules with incorrect configuration transitions we might get notified several times
    * for the same middleman. This should only happen if the actions are shared.
    */
   @Subscribe
   public void middlemanAction(ActionMiddlemanEvent event) {
     Action action = event.getAction();
     C component = createComponent(action, TimeUnit.NANOSECONDS.toMillis(event.getNanoTimeStart()));
     boolean duplicate = false;
     for (Artifact output : action.getOutputs()) {
       C old = outputArtifactToComponent.putIfAbsent(output, component);
       if (old != null) {
         if (!Actions.canBeShared(action, old.getAction())) {
           throw new IllegalStateException("Duplicate output artifact found for middleman."
               + "This could happen  if a previous event registered the action.\n"
               + "Old action: " + old.getAction() + "\n\n"
               + "New action: " + action + "\n\n"
               + "Artifact: " + output + "\n");
         }
         duplicate = true;
       }
     }
     if (!duplicate) {
       finalizeActionStat(action, component);
     }
   }

   /**
    * Record an action that was not executed because it was in the (disk) cache. This is needed so
    * that we can calculate correctly the dependencies tree if we have some cached actions in the
    * middle of the critical path.
    */
   @Subscribe
   public void actionCached(CachedActionEvent event) {
     Action action = event.getAction();
     C component = createComponent(action, TimeUnit.NANOSECONDS.toMillis(event.getNanoTimeStart()));
     for (Artifact output : action.getOutputs()) {
       outputArtifactToComponent.put(output, component);
     }
     finalizeActionStat(action, component);
   }

   /**
    * Records the elapsed time stats for the action. For each input artifact, it finds the real
    * dependent artifacts and records the critical path stats.
    */
   @Subscribe
   public void actionComplete(ActionCompletionEvent event) {
     ActionMetadata action = event.getActionMetadata();
     C component = Preconditions.checkNotNull(
         outputArtifactToComponent.get(action.getPrimaryOutput()));
     finalizeActionStat(action, component);
   }

   /** Maximum critical path component found during the build. */
   protected C getMaxCriticalPath() {
     synchronized (lock) {
       return maxCriticalPath;
     }
   }

   /**
    * The list of slowest individual components, ignoring the time to build dependencies.
    */
   public ImmutableList<C> getSlowestComponents() {
     ArrayList<C> list;
     synchronized (lock) {
       list = new ArrayList<>(slowestComponents);
       Collections.sort(list, slowestComponents.comparator());
     }
     return ImmutableList.copyOf(list).reverse();
   }

   private void finalizeActionStat(ActionMetadata action, C component) {
     component.setFinishTimeMillis(getTime());
     for (Artifact input : action.getInputs()) {
       addArtifactDependency(component, input);
     }

     synchronized (lock) {
       if (isBiggestCriticalPath(component)) {
         maxCriticalPath = component;
       }

       if (slowestComponents.size() == SLOWEST_COMPONENTS_SIZE) {
         // The new component is faster than any of the slow components, avoid insertion.
         if (slowestComponents.peek().getActionWallTime() >= component.getActionWallTime()) {
           return;
         }
         // Remove the head element to make space (The fastest component in the queue).
         slowestComponents.remove();
       }
       slowestComponents.add(component);
     }
   }

   private long getTime() {
     return TimeUnit.NANOSECONDS.toMillis(clock.nanoTime());
   }

   private boolean isBiggestCriticalPath(C newCriticalPath) {
     synchronized (lock) {
       return maxCriticalPath == null
           || maxCriticalPath.getAggregatedWallTime() < newCriticalPath.getAggregatedWallTime();
     }
   }

   /**
    * If "input" is a generated artifact, link its critical path to the one we're building.
    */
   private void addArtifactDependency(C actionStats, Artifact input) {
     C depComponent = outputArtifactToComponent.get(input);
     if (depComponent != null) {
       actionStats.addDepInfo(depComponent);
     }
   }
 }
	// Copyright 2014 Google Inc. All rights reserved.
	//
	// Licensed 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 com.google.devtools.build.lib.runtime;

	import com.google.common.base.Preconditions;
	import com.google.common.collect.ImmutableList;
	import com.google.common.collect.Maps;
	import com.google.common.eventbus.Subscribe;
	import com.google.devtools.build.lib.actions.Action;
	import com.google.devtools.build.lib.actions.ActionCompletionEvent;
	import com.google.devtools.build.lib.actions.ActionMetadata;
	import com.google.devtools.build.lib.actions.ActionMiddlemanEvent;
	import com.google.devtools.build.lib.actions.ActionStartedEvent;
	import com.google.devtools.build.lib.actions.Actions;
	import com.google.devtools.build.lib.actions.Artifact;
	import com.google.devtools.build.lib.actions.CachedActionEvent;
	import com.google.devtools.build.lib.util.Clock;

	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.PriorityQueue;
	import java.util.concurrent.ConcurrentMap;
	import java.util.concurrent.TimeUnit;

	import javax.annotation.concurrent.ThreadSafe;

	/**
	* Computes the critical path in the action graph based on events published to the event bus.
	*
	* <p>After instantiation, this object needs to be registered on the event bus to work.
	*/
	@ThreadSafe
	public abstract class CriticalPathComputer<C extends AbstractCriticalPathComponent<C>,
	A extends AggregatedCriticalPath<C>> {

	/** Number of top actions to record. */
	static final int SLOWEST_COMPONENTS_SIZE = 30;
	// outputArtifactToComponent is accessed from multiple event handlers.
	protected final ConcurrentMap<Artifact, C> outputArtifactToComponent = Maps.newConcurrentMap();

	/** Maximum critical path found. */
	private C maxCriticalPath;
	private final Clock clock;

	/**
	* The list of slowest individual components, ignoring the time to build dependencies.
	*
	* <p>This data is a useful metric when running non highly incremental builds, where multiple
	* tasks could run un parallel and critical path would only record the longest path.
	*/
	private final PriorityQueue<C> slowestComponents = new PriorityQueue<>(SLOWEST_COMPONENTS_SIZE,
	new Comparator<C>() {
	@Override
	public int compare(C o1, C o2) {
	return Long.compare(o1.getActionWallTime(), o2.getActionWallTime());
	}
	}
	);

	private final Object lock = new Object();

	protected CriticalPathComputer(Clock clock) {
	this.clock = clock;
	maxCriticalPath = null;
	}

	/**
	* Creates a critical path component for an action.
	* @param action the action for the critical path component
	* @param startTimeMillis time when the action started to run
	*/
	protected abstract C createComponent(Action action, long startTimeMillis);

	/**
	* Return the critical path stats for the current command execution.
	*
	* <p>This method allows us to calculate lazily the aggregate statistics of the critical path,
	* avoiding the memory and cpu penalty for doing it for all the actions executed.
	*/
	public abstract A aggregate();

	/**
	* Record an action that has started to run.
	*
	* @param event information about the started action
	*/
	@Subscribe
	public void actionStarted(ActionStartedEvent event) {
	Action action = event.getAction();
	C component = createComponent(action, TimeUnit.NANOSECONDS.toMillis(event.getNanoTimeStart()));
	for (Artifact output : action.getOutputs()) {
	C old = outputArtifactToComponent.put(output, component);
	Preconditions.checkState(old == null, "Duplicate output artifact found. This could happen"
	+ " if a previous event registered the action %s. Artifact: %s", action, output);
	}
	}

	/**
	* Record a middleman action execution. Even if middleman are almost instant, we record them
	* because they depend on other actions and we need them for constructing the critical path.
	*
	* <p>For some rules with incorrect configuration transitions we might get notified several times
	* for the same middleman. This should only happen if the actions are shared.
	*/
	@Subscribe
	public void middlemanAction(ActionMiddlemanEvent event) {
	Action action = event.getAction();
	C component = createComponent(action, TimeUnit.NANOSECONDS.toMillis(event.getNanoTimeStart()));
	boolean duplicate = false;
	for (Artifact output : action.getOutputs()) {
	C old = outputArtifactToComponent.putIfAbsent(output, component);
	if (old != null) {
	if (!Actions.canBeShared(action, old.getAction())) {
	throw new IllegalStateException("Duplicate output artifact found for middleman."
	+ "This could happen if a previous event registered the action.\n"
	+ "Old action: " + old.getAction() + "\n\n"
	+ "New action: " + action + "\n\n"
	+ "Artifact: " + output + "\n");
	}
	duplicate = true;
	}
	}
	if (!duplicate) {
	finalizeActionStat(action, component);
	}
	}

	/**
	* Record an action that was not executed because it was in the (disk) cache. This is needed so
	* that we can calculate correctly the dependencies tree if we have some cached actions in the
	* middle of the critical path.
	*/
	@Subscribe
	public void actionCached(CachedActionEvent event) {
	Action action = event.getAction();
	C component = createComponent(action, TimeUnit.NANOSECONDS.toMillis(event.getNanoTimeStart()));
	for (Artifact output : action.getOutputs()) {
	outputArtifactToComponent.put(output, component);
	}
	finalizeActionStat(action, component);
	}

	/**
	* Records the elapsed time stats for the action. For each input artifact, it finds the real
	* dependent artifacts and records the critical path stats.
	*/
	@Subscribe
	public void actionComplete(ActionCompletionEvent event) {
	ActionMetadata action = event.getActionMetadata();
	C component = Preconditions.checkNotNull(
	outputArtifactToComponent.get(action.getPrimaryOutput()));
	finalizeActionStat(action, component);
	}

	/** Maximum critical path component found during the build. */
	protected C getMaxCriticalPath() {
	synchronized (lock) {
	return maxCriticalPath;
	}
	}

	/**
	* The list of slowest individual components, ignoring the time to build dependencies.
	*/
	public ImmutableList<C> getSlowestComponents() {
	ArrayList<C> list;
	synchronized (lock) {
	list = new ArrayList<>(slowestComponents);
	Collections.sort(list, slowestComponents.comparator());
	}
	return ImmutableList.copyOf(list).reverse();
	}

	private void finalizeActionStat(ActionMetadata action, C component) {
	component.setFinishTimeMillis(getTime());
	for (Artifact input : action.getInputs()) {
	addArtifactDependency(component, input);
	}

	synchronized (lock) {
	if (isBiggestCriticalPath(component)) {
	maxCriticalPath = component;
	}

	if (slowestComponents.size() == SLOWEST_COMPONENTS_SIZE) {
	// The new component is faster than any of the slow components, avoid insertion.
	if (slowestComponents.peek().getActionWallTime() >= component.getActionWallTime()) {
	return;
	}
	// Remove the head element to make space (The fastest component in the queue).
	slowestComponents.remove();
	}
	slowestComponents.add(component);
	}
	}

	private long getTime() {
	return TimeUnit.NANOSECONDS.toMillis(clock.nanoTime());
	}

	private boolean isBiggestCriticalPath(C newCriticalPath) {
	synchronized (lock) {
	return maxCriticalPath == null
	\|\| maxCriticalPath.getAggregatedWallTime() < newCriticalPath.getAggregatedWallTime();
	}
	}

	/**
	* If "input" is a generated artifact, link its critical path to the one we're building.
	*/
	private void addArtifactDependency(C actionStats, Artifact input) {
	C depComponent = outputArtifactToComponent.get(input);
	if (depComponent != null) {
	actionStats.addDepInfo(depComponent);
	}
	}
	}