return x > 0 & (x & (x - 1)) == 0;
  }

  /**
   * Returns 1 if {@code x < y} as unsigned longs, and 0 otherwise. Assumes that x - y fits into a
   * signed long. The implementation is branch-free, and benchmarks suggest it is measurably faster
   * than the straightforward ternary expression.
   */
  @VisibleForTesting
  static int lessThanBranchFree(long x, long y) {
    // Returns the sign bit of x - y.

import java.util.concurrent.atomic.AtomicInteger;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.jspecify.annotations.NullUnmarked;
import org.jspecify.annotations.Nullable;

/** Benchmarks for {@link ExecutionList}. */
@VmOptions({"-Xms8g", "-Xmx8g"})
@NullUnmarked
public class ExecutionListBenchmark {
  private static final int NUM_THREADS = 10; // make a param?

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentSkipListMap;
import org.jspecify.annotations.NullUnmarked;

/**
 * Helper classes for various benchmarks.
 *
 * @author Christopher Swenson
 */
@NullUnmarked
final class BenchmarkHelpers {
  /** So far, this is the best way to test various implementations of {@link Set} subclasses. */

 * #offer} and a call to {@link #topK}, with O(k) memory. In comparison, quickselect has the same
 * asymptotics but requires O(n) memory, and a {@code PriorityQueue} implementation takes O(n log
 * k). In benchmarks, this implementation performs at least as well as either implementation, and
 * degrades more gracefully for worst-case input.
 *
 * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple

   * than this method, and this method in turn generally performs better than copying the list and
   * calling {@link Collections#sort(List)}.
   */
  // TODO(kevinb): rerun benchmarks including new options
  public <E extends T> List<E> sortedCopy(Iterable<E> elements) {
    @SuppressWarnings("unchecked") // does not escape, and contains only E's
    E[] array = (E[]) Iterables.toArray(elements);

 * weak references.
 *
 * <p><strong>Performance</strong>
 *
 * <p>The extra bookkeeping done by cycle detecting locks comes at some cost to performance.
 * Benchmarks (as of December 2011) show that:
 *
 * <ul>
 *   <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting lock takes 38ns as
 *       opposed to the 24ns taken by a plain lock.

 * weak references.
 *
 * <p><strong>Performance</strong>
 *
 * <p>The extra bookkeeping done by cycle detecting locks comes at some cost to performance.
 * Benchmarks (as of December 2011) show that:
 *
 * <ul>
 *   <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting lock takes 38ns as
 *       opposed to the 24ns taken by a plain lock.

  @ParametricNullness
  static <V extends @Nullable Object, X extends Exception> V getChecked(
      Future<V> future, Class<X> exceptionClass, long timeout, TimeUnit unit) throws X {
    // TODO(cpovirk): benchmark a version of this method that accepts a GetCheckedTypeValidator
    bestGetCheckedTypeValidator().validateClass(exceptionClass);
    try {
      return future.get(timeout, unit);
    } catch (InterruptedException e) {

  @ParametricNullness
  static <V extends @Nullable Object, X extends Exception> V getChecked(
      Future<V> future, Class<X> exceptionClass, long timeout, TimeUnit unit) throws X {
    // TODO(cpovirk): benchmark a version of this method that accepts a GetCheckedTypeValidator
    bestGetCheckedTypeValidator().validateClass(exceptionClass);
    try {
      return future.get(timeout, unit);
    } catch (InterruptedException e) {

    checkNotNull(list);
    checkNotNull(presentBehavior);
    checkNotNull(absentBehavior);
    if (!(list instanceof RandomAccess)) {
      list = new ArrayList<>(list);
    }
    // TODO(lowasser): benchmark when it's best to do a linear search

    int lower = 0;
    int upper = list.size() - 1;

    while (lower <= upper) {
      int middle = (lower + upper) >>> 1;