You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@groovy.apache.org by pa...@apache.org on 2026/08/30 01:29:32 UTC

(groovy) 02/02: GROOVY-12320: ChannelSelect: add fair() and random() choice among ready channels

This is an automated email from the ASF dual-hosted git repository.

paulk-asert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/groovy.git

commit 784b0ef6523e868067490fd2917c75653ac4dada
Author: Paul King <pa...@asert.com.au>
AuthorDate: Sun Aug 30 07:30:49 2026 +1000

    GROOVY-12320: ChannelSelect: add fair() and random() choice among ready channels
    
    select() takes the first-listed channel when several are ready, because a
    ready channel completes synchronously during registration. That is a
    priority select, now documented as such; a channel that always has a value
    waiting starves the channels listed after it, which is the case the CSP
    literature guards against with a fair alternative.
    
    fair() returns a select over the same channels whose registration order
    starts at the channel after the one that last won, so any channel that is
    ready is taken within n calls (the rotating policy of JCSP's fairSelect).
    random() shuffles the registration order, so every ready channel is equally
    likely to be met first (the policy of Go's select; a random start with a
    cyclic scan, as in GPars, would favour a ready channel by the run of
    not-ready channels before it). random() is stateless, so it is equally fair
    from any number of threads, but gives no bound on how long a ready channel
    may be passed over. When no channel is ready the first arrival still wins
    under every policy.
---
 src/main/java/groovy/concurrent/ChannelSelect.java |  96 ++++++++++++++++--
 src/spec/doc/_core-async-channels.adoc             |  21 ++++
 .../groovy/concurrent/ChannelSelectTest.groovy     | 107 +++++++++++++++++++++
 3 files changed, 218 insertions(+), 6 deletions(-)

diff --git a/src/main/java/groovy/concurrent/ChannelSelect.java b/src/main/java/groovy/concurrent/ChannelSelect.java
index 946165fa40..1950997ea7 100644
--- a/src/main/java/groovy/concurrent/ChannelSelect.java
+++ b/src/main/java/groovy/concurrent/ChannelSelect.java
@@ -24,6 +24,7 @@ import org.apache.groovy.runtime.async.GroovyPromise;
 import java.util.List;
 import java.util.Objects;
 import java.util.concurrent.CompletableFuture;
+import java.util.concurrent.ThreadLocalRandom;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.concurrent.atomic.AtomicInteger;
 
@@ -51,10 +52,18 @@ import java.util.concurrent.atomic.AtomicInteger;
  */
 public final class ChannelSelect {
 
+    /** How to choose when several channels are ready at the same time. */
+    private enum Policy { PRIORITY, FAIR, RANDOM }
+
     private final List<AsyncChannel<?>> channels;
+    private final Policy policy;
+    /** index of the last winner; only maintained under {@link Policy#FAIR} */
+    private final AtomicInteger lastWinner;
 
-    private ChannelSelect(List<AsyncChannel<?>> channels) {
+    private ChannelSelect(List<AsyncChannel<?>> channels, Policy policy) {
         this.channels = channels;
+        this.policy = policy;
+        this.lastWinner = policy == Policy.FAIR ? new AtomicInteger(-1) : null;
     }
 
     /**
@@ -69,7 +78,50 @@ public final class ChannelSelect {
         if (channels.length == 0) {
             throw new IllegalArgumentException("At least one channel is required");
         }
-        return new ChannelSelect(List.of(channels));
+        return new ChannelSelect(List.of(channels), Policy.PRIORITY);
+    }
+
+    /**
+     * Returns a select over the same channels that chooses fairly among
+     * channels that are ready at the same time.
+     * <p>
+     * By default {@link #select()} prefers the channel listed first, so a
+     * channel that always has a value waiting starves the ones after it. A
+     * fair select instead starts each call at the channel after the one
+     * that last won, so every channel that is ready is taken within
+     * {@code n} calls, where {@code n} is the number of channels. This is
+     * the rotating policy of JCSP's {@code fairSelect}. When no channel is
+     * ready, the first value to arrive wins under either policy.
+     * <p>
+     * The rotation state lives in the returned instance, so keep and reuse
+     * it across calls (typically in a loop); a shared instance may be used
+     * from several threads, in which case the rotation is best effort.
+     *
+     * @return a fair ChannelSelect over the same channels
+     * @see #random()
+     * @since 6.0.0
+     */
+    public ChannelSelect fair() {
+        return new ChannelSelect(channels, Policy.FAIR);
+    }
+
+    /**
+     * Returns a select over the same channels that chooses uniformly at
+     * random among channels that are ready at the same time.
+     * <p>
+     * This is the policy of Go's {@code select} and GPars' {@code Select}.
+     * Unlike {@link #fair()} it keeps no state between calls, so it is
+     * exactly as fair from any number of threads and cannot fall into
+     * lock-step with the producers, but it offers no bound on how long a
+     * ready channel may be passed over. When no channel is ready, the first
+     * value to arrive wins under either policy.
+     *
+     * @return a randomly choosing ChannelSelect over the same channels
+     * @see #fair()
+     * @since 6.0.0
+     */
+    public ChannelSelect random() {
+        return new ChannelSelect(channels, Policy.RANDOM);
     }
 
     /**
@@ -82,7 +134,9 @@ public final class ChannelSelect {
      * channels are left untouched: their contents and order are preserved,
      * and nothing remains registered on them once the result completes.
      * When several channels already hold a value, the one listed first is
-     * taken. Cancelling the result (for example through
+     * taken (see {@link #fair()} for a rotating choice and {@link #random()}
+     * for a random one). Cancelling the
+     * result (for example through
      * {@link Awaitable#orTimeout(long, java.util.concurrent.TimeUnit)})
      * withdraws the pending receives, so a timed-out select consumes
      * nothing.
@@ -104,8 +158,13 @@ public final class ChannelSelect {
         AtomicInteger closedCount = new AtomicInteger();
         Awaitable<?>[] branches = new Awaitable<?>[count];
 
-        for (int i = 0; i < count && !winner.isDone(); i++) {
-            final int index = i;
+        // a ready channel completes synchronously during registration, so the
+        // registration order is the priority order: rotate it under fair(),
+        // shuffle it under random() (a random start alone would favour a
+        // ready channel by the run of not-ready channels before it)
+        int[] order = registrationOrder(count);
+        for (int k = 0; k < count && !winner.isDone(); k++) {
+            final int index = order[k];
             AsyncChannel<?> ch = channels.get(index);
             final boolean claimable = ch instanceof DefaultAsyncChannel;
             Awaitable<?> branch = claimable
@@ -128,10 +187,35 @@ public final class ChannelSelect {
             });
         }
         // branches registered after the win, and cancellation of the result itself
-        winner.whenComplete((result, error) -> withdraw(branches));
+        winner.whenComplete((result, error) -> {
+            withdraw(branches);
+            if (result != null && lastWinner != null) lastWinner.set(result.index);
+        });
         return GroovyPromise.of(winner);
     }
 
+    private int[] registrationOrder(int count) {
+        int[] order = new int[count];
+        switch (policy) {
+            case PRIORITY -> {
+                for (int i = 0; i < count; i++) order[i] = i;
+            }
+            case FAIR -> {
+                int start = Math.floorMod(lastWinner.get() + 1, count);
+                for (int i = 0; i < count; i++) order[i] = (start + i) % count;
+            }
+            case RANDOM -> { // Fisher-Yates: every ready channel is equally likely to be met first
+                ThreadLocalRandom random = ThreadLocalRandom.current();
+                for (int i = 0; i < count; i++) {
+                    int j = random.nextInt(i + 1);
+                    order[i] = order[j];
+                    order[j] = i;
+                }
+            }
+        }
+        return order;
+    }
+
     private static void withdraw(Awaitable<?>[] branches) {
         for (Awaitable<?> branch : branches) {
             if (branch != null) branch.cancel();
diff --git a/src/spec/doc/_core-async-channels.adoc b/src/spec/doc/_core-async-channels.adoc
index f2a4243001..a3513d00ab 100644
--- a/src/spec/doc/_core-async-channels.adoc
+++ b/src/spec/doc/_core-async-channels.adoc
@@ -134,6 +134,27 @@ channels are left untouched. When several channels already have a value
 waiting, the one listed first is taken. If every channel is closed and
 drained, `select()` fails with `ChannelClosedException`.
 
+That priority by list order means a channel that always has a value
+waiting starves the channels listed after it. `fair()` returns a select
+that rotates instead — each call starts at the channel after the one
+that last won, like JCSP's `fairSelect` — so keep the instance across
+calls:
+
+[source,groovy]
+----
+def sel = ChannelSelect.from(requests, control).fair()
+while (true) {
+    def result = await sel.select()
+    // control is served even while requests never runs dry
+}
+----
+
+`random()` chooses uniformly at random among the ready channels instead,
+as Go's `select` does. It keeps no state between calls, so it is equally
+fair from any number of threads, but it gives no bound on how long a
+ready channel may be passed over; `fair()` guarantees every ready channel
+is taken within _n_ calls.
+
 [[async-broadcast-channel]]
 == BroadcastChannel
 
diff --git a/src/test/groovy/groovy/concurrent/ChannelSelectTest.groovy b/src/test/groovy/groovy/concurrent/ChannelSelectTest.groovy
index 548f6945b7..6505381ba8 100644
--- a/src/test/groovy/groovy/concurrent/ChannelSelectTest.groovy
+++ b/src/test/groovy/groovy/concurrent/ChannelSelectTest.groovy
@@ -299,6 +299,113 @@ final class ChannelSelectTest {
         '''
     }
 
+    @Test
+    void testFairSelectRotatesAmongReadyChannels() {
+        assertScript '''
+            import groovy.concurrent.AsyncChannel
+            import groovy.concurrent.ChannelSelect
+
+            def a = AsyncChannel.create(20)
+            def b = AsyncChannel.create(20)
+            def c = AsyncChannel.create(20)
+            for (i in 0..<20) { a.send('a' + i); b.send('b' + i); c.send('c' + i) }
+
+            def sel = ChannelSelect.from(a, b, c).fair()
+            def order = []
+            for (i in 0..<9) {
+                order << (await sel.select()).index
+            }
+            assert order == [0, 1, 2, 0, 1, 2, 0, 1, 2]
+
+            // each channel gave up its values in order
+            assert [await(a.receive()), await(b.receive()), await(c.receive())] == ['a3', 'b3', 'c3']
+
+            // a continuously ready channel cannot starve a ready peer
+            def busy = AsyncChannel.create(1000)
+            def peer = AsyncChannel.create(1)
+            for (i in 0..<1000) busy.send(i)
+            peer.send('me too')
+            def fairSel = ChannelSelect.from(busy, peer).fair()
+            def taken = (0..<2).collect { (await fairSel.select()).index }
+            assert taken.contains(1)
+
+            // the default policy is priority by list order
+            def prio = ChannelSelect.from(a, b, c)
+            assert (0..<5).collect { (await prio.select()).index } == [0, 0, 0, 0, 0]
+        '''
+    }
+
+    @Test
+    void testRandomSelectSpreadsAmongReadyChannels() {
+        assertScript '''
+            import groovy.concurrent.AsyncChannel
+            import groovy.concurrent.ChannelSelect
+
+            int rounds = 300
+            def a = AsyncChannel.create(rounds)
+            def b = AsyncChannel.create(rounds)
+            def c = AsyncChannel.create(rounds)
+            for (i in 0..<rounds) { a.send('a' + i); b.send('b' + i); c.send('c' + i) }
+
+            def sel = ChannelSelect.from(a, b, c).random()
+            def wins = [0, 0, 0]
+            def taken = [[], [], []]
+            for (i in 0..<rounds) {
+                def result = await sel.select()
+                wins[result.index]++
+                taken[result.index] << result.value
+            }
+            // every channel is chosen (the chance of one being skipped in 300 draws is (2/3)^300)
+            assert wins.every { it > 0 }
+            // and each channel gave up its values in order
+            taken.eachWithIndex { values, index ->
+                assert values == (0..<values.size()).collect { 'abc'[index] + it }
+            }
+        '''
+
+        // uniform among the ready channels, not weighted by the not-ready gaps between them
+        assertScript '''
+            import groovy.concurrent.AsyncChannel
+            import groovy.concurrent.ChannelSelect
+
+            int rounds = 600
+            def a = AsyncChannel.create(rounds)
+            def b = AsyncChannel.create(rounds)
+            def empty = AsyncChannel.create(1)
+            for (i in 0..<rounds) { a.send(i); b.send(i) }
+
+            // a random start with a cyclic scan would give a two thirds, b one third
+            def sel = ChannelSelect.from(a, b, empty).random()
+            def wins = [0, 0, 0]
+            for (i in 0..<rounds) {
+                wins[(await sel.select()).index]++
+            }
+            // expected 300 each with a standard deviation of about 12; 230 is 6 sigma below
+            assert wins[2] == 0 && wins[0] >= 230 && wins[1] >= 230 : wins
+        '''
+    }
+
+    @Test
+    void testFairSelectStillTakesTheFirstArrival() {
+        assertScript '''
+            import groovy.concurrent.AsyncChannel
+            import groovy.concurrent.ChannelSelect
+
+            def a = AsyncChannel.create(4)
+            def b = AsyncChannel.create(4)
+            def sel = ChannelSelect.from(a, b).fair()
+
+            async { Thread.sleep(50); b.send('b-first') }
+            def result = await sel.select()
+            assert result.index == 1 && result.value == 'b-first'
+            assert a.toString().contains('waitingReceivers=0')
+
+            async { Thread.sleep(50); a.send('a-next') }
+            result = await sel.select()
+            assert result.index == 0 && result.value == 'a-next'
+        '''
+    }
+
     @Test
     void testConcurrentSelectsDeliverEveryValueExactlyOnce() {
         assertScript '''