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

Question

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

请帮我看看 CompletableFuture 的 allOf 方法到底做了什么。

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

它不进行二分搜索——它正在构建一棵 平衡二叉树，叶子的输入期货和内部节点在其两个 children 都完成了。

出于代码中不明显的某种原因，代码的作者一定已经决定将恰好两个期货之间的 allOf(_,_) 视为他的原始操作是最有效的，如果他被要求allOf(...) 介于两个以上的期货之间，他将其制造为这些二进制原语的级联。

树应该是平衡的，这样无论最后一个要完成的未来是什么，在未来的top 可以完成。这在某些情况下提高了性能，因为它确保在我们完全完成之前可以处理尽可能多的工作，此时（如果我们幸运的话）CPU 可能只是闲置，等待异步完成。

树的平衡是通过让 topmost 内部节点在其左侧 child 与右侧 child 下的叶子数量大致相同来完成的 --所以 children 都得到原始数组的大约一半，然后代码递归地从数组的每一半构建一棵树。分成两半看起来有点像二进制搜索的索引计算。

基本结构被设计为
的特殊情况略微模糊

当一些原始期货已经完成时，使用分配更少的优化代码路径，并且

确保 allOf(_) 的结果与恰好 one 元素 return 一个 fresh CompleteableFuture。在大多数情况下，它只适用于 return 单个元素，但作者一定想确保库的用户可以依赖 object 是新鲜的，如果他们将它们用作哈希映射，或其他依赖于能够从输入中分辨出输出的逻辑，以及

只有一个 throw new NullPointerException(); 通过使用 ?: 和内联赋值而不是诚实的 if 语句。这可能以牺牲可读性为代价产生略小的字节码。不能推荐作为一种学习风格，除非您亲自支付生成的字节码的存储成本...

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

Why does the CompletableFuture allOf method do a binary search?

java

concurrency

completable-future