为什么 CompletableFuture allOf 方法会进行二分查找？

Question

我想知道allOf方法是否CompletableFuture进行轮询或进入等待状态，直到所有CompletableFutures传递给该方法的方法都完成执行。allOf我查看了方法的代码IntelliJ，它正在进行某种二进制搜索。

请帮助我找出方法allOf的CompletableFuture实际作用。

public static CompletableFuture<Void> allOf(CompletableFuture<?>... cfs) {

    return andTree(cfs, 0, cfs.length - 1);

}

/** Recursively constructs a tree of completions. */

static CompletableFuture<Void> andTree(CompletableFuture<?>[] cfs, int lo, int hi) {

    CompletableFuture<Void> d = new CompletableFuture<Void>();

    if (lo > hi) // empty

        d.result = NIL;

    else {

        CompletableFuture<?> a, b;

        int mid = (lo + hi) >>> 1;

        if ((a = (lo == mid ? cfs[lo] :

                  andTree(cfs, lo, mid))) == null ||

            (b = (lo == hi ? a : (hi == mid+1) ? cfs[hi] :

                  andTree(cfs, mid+1, hi)))  == null)

            throw new NullPointerException();

        if (!d.biRelay(a, b)) {

            BiRelay<?,?> c = new BiRelay<>(d, a, b);

            a.bipush(b, c);

            c.tryFire(SYNC);

        }

    }

    return d;

}

/** Pushes completion to this and b unless both done. */

final void bipush(CompletableFuture<?> b, BiCompletion<?,?,?> c) {

    if (c != null) {

        Object r;

        while ((r = result) == null && !tryPushStack(c))

            lazySetNext(c, null); // clear on failure

        if (b != null && b != this && b.result == null) {

            Completion q = (r != null) ? c : new CoCompletion(c);

            while (b.result == null && !b.tryPushStack(q))

                lazySetNext(q, null); // clear on failure

        }

    }

}

final CompletableFuture<V> tryFire(int mode) {

    CompletableFuture<V> d;

    CompletableFuture<T> a;

    CompletableFuture<U> b;

    if ((d = dep) == null ||

        !d.orApply(a = src, b = snd, fn, mode > 0 ? null : this))

        return null;

    dep = null; src = null; snd = null; fn = null;

    return d.postFire(a, b, mode);

}

Answer 1

它不进行二分搜索——它正在构建一个平衡的二叉树，在叶子上输入 futures，当它的两个孩子都完成时，每个内部节点都完成。出于代码中不明显的某种原因，代码的作者一定已经决定将allOf(_,_)恰好两个期货作为他的原始操作来考虑是最有效的，如果他要求在allOf(...)两个以上的期货之间，他正在制造它作为这些二进制原语的级联。这棵树应该是平衡的，无论最后一个要完成的未来是什么，在顶部的未来可以完成之前，只有少数层次要崩溃。这在某些情况下提高了性能，因为它确保在我们完全完成之前可以处理尽可能多的工作，此时（如果我们幸运的话）CPU 可能只是闲置，等待异步操作完全的。树的平衡是通过让最顶层的内部节点在其左子节点下的叶子数量与在其右子节点下的叶子数量一样多来完成的——因此两个子节点都获得原始数组的大约一半，然后代码递归地从每一半构建一棵树阵列。分成两半看起来有点像二进制搜索的索引计算。基本结构被似乎设计为当一些原始期货已经完成时，使用分配更少的优化代码路径，并且确保allOf(_)只有一个元素的结果将返回一个新的 CompleteableFuture. 对于大多数目的，只返回单个元素就可以了，但作者一定想确保库的用户可以依赖新鲜的对象，如果他们将它们用作散列映射中的键，或其他依赖的逻辑能够从输入中分辨出输出，以及throw new NullPointerException();通过使用?:和内联赋值而不是诚实的if陈述只有一个。这可能会以牺牲可读性为代价产生略小的字节码。