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 '''