refactor: Use RandomGenerator as randomness source

This change updates the modules of OpenDC to always accept
the `RandomGenerator` interface as source of randomness. This interface
is implemented by the slower `java.util.Random` class, but also by the
faster `java.util.SplittableRandom` class

15 files changed, 61 insertions, 37 deletions

diff --git a/opendc-compute/opendc-compute-service/src/main/kotlin/org/opendc/compute/service/scheduler/FilterScheduler.kt b/opendc-compute/opendc-compute-service/src/main/kotlin/org/opendc/compute/service/scheduler/FilterScheduler.kt
index 233f5ef6..0840ba7e 100644
--- a/opendc-compute/opendc-compute-service/src/main/kotlin/org/opendc/compute/service/scheduler/FilterScheduler.kt
+++ b/opendc-compute/opendc-compute-service/src/main/kotlin/org/opendc/compute/service/scheduler/FilterScheduler.kt
@@ -26,7 +26,8 @@ import org.opendc.compute.api.Server
 import org.opendc.compute.service.internal.HostView
 import org.opendc.compute.service.scheduler.filters.HostFilter
 import org.opendc.compute.service.scheduler.weights.HostWeigher
-import java.util.Random
+import java.util.SplittableRandom
+import java.util.random.RandomGenerator
 import kotlin.math.min
 
 /**
@@ -39,13 +40,13 @@ import kotlin.math.min
  * @param filters The list of filters to apply when searching for an appropriate host.
  * @param weighers The list of weighers to apply when searching for an appropriate host.
  * @param subsetSize The size of the subset of best hosts from which a target is randomly chosen.
- * @param random A [Random] instance for selecting
+ * @param random A [RandomGenerator] instance for selecting
  */
 public class FilterScheduler(
     private val filters: List<HostFilter>,
     private val weighers: List<HostWeigher>,
     private val subsetSize: Int = 1,
-    private val random: Random = Random(0)
+    private val random: RandomGenerator = SplittableRandom(0)
 ) : ComputeScheduler {
     /**
      * The pool of hosts available to the scheduler.
diff --git a/opendc-compute/opendc-compute-simulator/src/main/kotlin/org/opendc/compute/simulator/failure/StochasticVictimSelector.kt b/opendc-compute/opendc-compute-simulator/src/main/kotlin/org/opendc/compute/simulator/failure/StochasticVictimSelector.kt
index b6d466bd..4aba0e91 100644
--- a/opendc-compute/opendc-compute-simulator/src/main/kotlin/org/opendc/compute/simulator/failure/StochasticVictimSelector.kt
+++ b/opendc-compute/opendc-compute-simulator/src/main/kotlin/org/opendc/compute/simulator/failure/StochasticVictimSelector.kt
@@ -24,7 +24,9 @@ package org.opendc.compute.simulator.failure
 
 import org.apache.commons.math3.distribution.RealDistribution
 import org.opendc.compute.simulator.SimHost
-import java.util.Random
+import java.util.ArrayList
+import java.util.SplittableRandom
+import java.util.random.RandomGenerator
 import kotlin.math.roundToInt
 
 /**
@@ -32,12 +34,30 @@ import kotlin.math.roundToInt
  */
 public class StochasticVictimSelector(
     private val size: RealDistribution,
-    private val random: Random = Random(0)
+    private val random: RandomGenerator = SplittableRandom(0)
 ) : VictimSelector {
 
     override fun select(hosts: Set<SimHost>): List<SimHost> {
         val n = size.sample().roundToInt()
-        return hosts.shuffled(random).take(n)
+        val result = ArrayList<SimHost>(n)
+
+        val random = random
+        var samplesNeeded = n
+        var remainingHosts = hosts.size
+        val iterator = hosts.iterator()
+
+        while (iterator.hasNext() && samplesNeeded > 0) {
+            val host = iterator.next()
+
+            if (random.nextInt(remainingHosts) < samplesNeeded) {
+                result.add(host)
+                samplesNeeded--
+            }
+
+            remainingHosts--
+        }
+
+        return result
     }
 
     override fun toString(): String = "StochasticVictimSelector[$size]"
diff --git a/opendc-compute/opendc-compute-simulator/src/test/kotlin/org/opendc/compute/simulator/failure/HostFaultInjectorTest.kt b/opendc-compute/opendc-compute-simulator/src/test/kotlin/org/opendc/compute/simulator/failure/HostFaultInjectorTest.kt
index 90f534e6..a65c37cf 100644
--- a/opendc-compute/opendc-compute-simulator/src/test/kotlin/org/opendc/compute/simulator/failure/HostFaultInjectorTest.kt
+++ b/opendc-compute/opendc-compute-simulator/src/test/kotlin/org/opendc/compute/simulator/failure/HostFaultInjectorTest.kt
@@ -38,7 +38,7 @@ import kotlin.math.ln
 /**
  * Test suite for [HostFaultInjector] class.
  */
-internal class HostFaultInjectorTest {
+class HostFaultInjectorTest {
     /**
      * Simple test case to test that nothing happens when the injector is not started.
      */
diff --git a/opendc-experiments/opendc-experiments-base/src/main/kotlin/org/opendc/experiments/provisioner/ProvisioningContext.kt b/opendc-experiments/opendc-experiments-base/src/main/kotlin/org/opendc/experiments/provisioner/ProvisioningContext.kt
index 73897315..b8679872 100644
--- a/opendc-experiments/opendc-experiments-base/src/main/kotlin/org/opendc/experiments/provisioner/ProvisioningContext.kt
+++ b/opendc-experiments/opendc-experiments-base/src/main/kotlin/org/opendc/experiments/provisioner/ProvisioningContext.kt
@@ -25,6 +25,7 @@ package org.opendc.experiments.provisioner
 import org.opendc.experiments.MutableServiceRegistry
 import java.time.Clock
 import java.util.SplittableRandom
+import java.util.random.RandomGenerator
 import kotlin.coroutines.CoroutineContext
 
 /**
@@ -46,7 +47,7 @@ public interface ProvisioningContext {
     /**
      * A [SplittableRandom] instance used to seed the provisioners.
      */
-    public val seeder: SplittableRandom
+    public val seeder: RandomGenerator
 
     /**
      * A [MutableServiceRegistry] where the provisioned services are registered.
diff --git a/opendc-experiments/opendc-experiments-capelin/src/main/kotlin/org/opendc/experiments/capelin/topology/TopologyFactories.kt b/opendc-experiments/opendc-experiments-capelin/src/main/kotlin/org/opendc/experiments/capelin/topology/TopologyFactories.kt
index 0b4cafa6..3a2acbd7 100644
--- a/opendc-experiments/opendc-experiments-capelin/src/main/kotlin/org/opendc/experiments/capelin/topology/TopologyFactories.kt
+++ b/opendc-experiments/opendc-experiments-capelin/src/main/kotlin/org/opendc/experiments/capelin/topology/TopologyFactories.kt
@@ -34,8 +34,9 @@ import org.opendc.simulator.compute.power.CpuPowerModel
 import org.opendc.simulator.compute.power.CpuPowerModels
 import java.io.File
 import java.io.InputStream
-import java.util.Random
+import java.util.SplittableRandom
 import java.util.UUID
+import java.util.random.RandomGenerator
 import kotlin.math.roundToLong
 
 /**
@@ -49,7 +50,7 @@ private val reader = ClusterSpecReader()
 fun clusterTopology(
     file: File,
     powerModel: CpuPowerModel = CpuPowerModels.linear(350.0, 200.0),
-    random: Random = Random(0)
+    random: RandomGenerator = SplittableRandom(0)
 ): List<HostSpec> {
     return clusterTopology(reader.read(file), powerModel, random)
 }
@@ -60,7 +61,7 @@ fun clusterTopology(
 fun clusterTopology(
     input: InputStream,
     powerModel: CpuPowerModel = CpuPowerModels.linear(350.0, 200.0),
-    random: Random = Random(0)
+    random: RandomGenerator = SplittableRandom(0)
 ): List<HostSpec> {
     return clusterTopology(reader.read(input), powerModel, random)
 }
@@ -68,14 +69,14 @@ fun clusterTopology(
 /**
  * Construct a topology from the given list of [clusters].
  */
-fun clusterTopology(clusters: List<ClusterSpec>, powerModel: CpuPowerModel, random: Random = Random(0)): List<HostSpec> {
+fun clusterTopology(clusters: List<ClusterSpec>, powerModel: CpuPowerModel, random: RandomGenerator = SplittableRandom(0)): List<HostSpec> {
     return clusters.flatMap { it.toHostSpecs(random, powerModel) }
 }
 
 /**
  * Helper method to convert a [ClusterSpec] into a list of [HostSpec]s.
  */
-private fun ClusterSpec.toHostSpecs(random: Random, powerModel: CpuPowerModel): List<HostSpec> {
+private fun ClusterSpec.toHostSpecs(random: RandomGenerator, powerModel: CpuPowerModel): List<HostSpec> {
     val cpuSpeed = cpuSpeed
     val memoryPerHost = memCapacityPerHost.roundToLong()
 
diff --git a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/ComputeSchedulers.kt b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/ComputeSchedulers.kt
index bbc70489..125ba6ef 100644
--- a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/ComputeSchedulers.kt
+++ b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/ComputeSchedulers.kt
@@ -34,12 +34,13 @@ import org.opendc.compute.service.scheduler.weights.CoreRamWeigher
 import org.opendc.compute.service.scheduler.weights.InstanceCountWeigher
 import org.opendc.compute.service.scheduler.weights.RamWeigher
 import org.opendc.compute.service.scheduler.weights.VCpuWeigher
-import java.util.Random
+import java.util.SplittableRandom
+import java.util.random.RandomGenerator
 
 /**
  * Create a [ComputeScheduler] for the experiment.
  */
-public fun createComputeScheduler(name: String, seeder: Random, placements: Map<String, String> = emptyMap()): ComputeScheduler {
+public fun createComputeScheduler(name: String, seeder: RandomGenerator, placements: Map<String, String> = emptyMap()): ComputeScheduler {
     val cpuAllocationRatio = 16.0
     val ramAllocationRatio = 1.5
     return when (name) {
@@ -79,7 +80,7 @@ public fun createComputeScheduler(name: String, seeder: Random, placements: Map<
             filters = listOf(ComputeFilter(), VCpuFilter(cpuAllocationRatio), RamFilter(ramAllocationRatio)),
             weighers = emptyList(),
             subsetSize = Int.MAX_VALUE,
-            random = Random(seeder.nextLong())
+            random = SplittableRandom(seeder.nextLong())
         )
         "replay" -> ReplayScheduler(placements)
         else -> throw IllegalArgumentException("Unknown policy $name")
diff --git a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/ComputeWorkload.kt b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/ComputeWorkload.kt
index 2200880d..b7884293 100644
--- a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/ComputeWorkload.kt
+++ b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/ComputeWorkload.kt
@@ -22,7 +22,7 @@
 
 package org.opendc.experiments.compute
 
-import java.util.Random
+import java.util.random.RandomGenerator
 
 /**
  * An interface that describes how a workload is resolved.
@@ -31,5 +31,5 @@ public interface ComputeWorkload {
     /**
      * Resolve the workload into a list of [VirtualMachine]s to simulate.
      */
-    public fun resolve(loader: ComputeWorkloadLoader, random: Random): List<VirtualMachine>
+    public fun resolve(loader: ComputeWorkloadLoader, random: RandomGenerator): List<VirtualMachine>
 }
diff --git a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/FailureModel.kt b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/FailureModel.kt
index 81a5cf33..de2447c6 100644
--- a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/FailureModel.kt
+++ b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/FailureModel.kt
@@ -25,7 +25,7 @@ package org.opendc.experiments.compute
 import org.opendc.compute.service.ComputeService
 import org.opendc.compute.simulator.failure.HostFaultInjector
 import java.time.Clock
-import java.util.Random
+import java.util.random.RandomGenerator
 import kotlin.coroutines.CoroutineContext
 
 /**
@@ -39,6 +39,6 @@ public interface FailureModel {
         context: CoroutineContext,
         clock: Clock,
         service: ComputeService,
-        random: Random
+        random: RandomGenerator
     ): HostFaultInjector
 }
diff --git a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/FailureModels.kt b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/FailureModels.kt
index ff747066..a77047b0 100644
--- a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/FailureModels.kt
+++ b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/FailureModels.kt
@@ -33,7 +33,7 @@ import org.opendc.compute.simulator.failure.StartStopHostFault
 import org.opendc.compute.simulator.failure.StochasticVictimSelector
 import java.time.Clock
 import java.time.Duration
-import java.util.Random
+import java.util.random.RandomGenerator
 import kotlin.coroutines.CoroutineContext
 import kotlin.math.ln
 
@@ -49,7 +49,7 @@ public fun grid5000(failureInterval: Duration): FailureModel {
             context: CoroutineContext,
             clock: Clock,
             service: ComputeService,
-            random: Random
+            random: RandomGenerator
         ): HostFaultInjector {
             val rng = Well19937c(random.nextLong())
             val hosts = service.hosts.map { it as SimHost }.toSet()
diff --git a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/CompositeComputeWorkload.kt b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/CompositeComputeWorkload.kt
index 3a7a51f2..ca23a7c5 100644
--- a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/CompositeComputeWorkload.kt
+++ b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/CompositeComputeWorkload.kt
@@ -26,7 +26,7 @@ import mu.KotlinLogging
 import org.opendc.experiments.compute.ComputeWorkload
 import org.opendc.experiments.compute.ComputeWorkloadLoader
 import org.opendc.experiments.compute.VirtualMachine
-import java.util.Random
+import java.util.random.RandomGenerator
 
 /**
  * A [ComputeWorkload] that samples multiple workloads based on the total load of all workloads.
@@ -37,7 +37,7 @@ internal class CompositeComputeWorkload(val sources: Map<ComputeWorkload, Double
      */
     private val logger = KotlinLogging.logger {}
 
-    override fun resolve(loader: ComputeWorkloadLoader, random: Random): List<VirtualMachine> {
+    override fun resolve(loader: ComputeWorkloadLoader, random: RandomGenerator): List<VirtualMachine> {
         val traces = sources.map { (source, fraction) -> fraction to source.resolve(loader, random) }
 
         val totalLoad = traces.sumOf { (_, vms) -> vms.sumOf { it.totalLoad } }
diff --git a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/HpcSampledComputeWorkload.kt b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/HpcSampledComputeWorkload.kt
index a6055762..583405da 100644
--- a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/HpcSampledComputeWorkload.kt
+++ b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/HpcSampledComputeWorkload.kt
@@ -26,8 +26,8 @@ import mu.KotlinLogging
 import org.opendc.experiments.compute.ComputeWorkload
 import org.opendc.experiments.compute.ComputeWorkloadLoader
 import org.opendc.experiments.compute.VirtualMachine
-import java.util.Random
 import java.util.UUID
+import java.util.random.RandomGenerator
 
 /**
  * A [ComputeWorkload] that samples HPC VMs in the workload.
@@ -46,7 +46,7 @@ internal class HpcSampledComputeWorkload(val source: ComputeWorkload, val fracti
      */
     private val pattern = Regex("^(ComputeNode|cn).*")
 
-    override fun resolve(loader: ComputeWorkloadLoader, random: Random): List<VirtualMachine> {
+    override fun resolve(loader: ComputeWorkloadLoader, random: RandomGenerator): List<VirtualMachine> {
         val vms = source.resolve(loader, random)
 
         val (hpc, nonHpc) = vms.partition { entry ->
@@ -58,7 +58,6 @@ internal class HpcSampledComputeWorkload(val source: ComputeWorkload, val fracti
             .map { index ->
                 val res = mutableListOf<VirtualMachine>()
                 hpc.mapTo(res) { sample(it, index) }
-                res.shuffle(random)
                 res
             }
             .flatten()
@@ -67,7 +66,6 @@ internal class HpcSampledComputeWorkload(val source: ComputeWorkload, val fracti
             .map { index ->
                 val res = mutableListOf<VirtualMachine>()
                 nonHpc.mapTo(res) { sample(it, index) }
-                res.shuffle(random)
                 res
             }
             .flatten()
diff --git a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/LoadSampledComputeWorkload.kt b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/LoadSampledComputeWorkload.kt
index 793f1de9..ffb7e0c6 100644
--- a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/LoadSampledComputeWorkload.kt
+++ b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/LoadSampledComputeWorkload.kt
@@ -26,7 +26,7 @@ import mu.KotlinLogging
 import org.opendc.experiments.compute.ComputeWorkload
 import org.opendc.experiments.compute.ComputeWorkloadLoader
 import org.opendc.experiments.compute.VirtualMachine
-import java.util.Random
+import java.util.random.RandomGenerator
 
 /**
  * A [ComputeWorkload] that is sampled based on total load.
@@ -37,7 +37,7 @@ internal class LoadSampledComputeWorkload(val source: ComputeWorkload, val fract
      */
     private val logger = KotlinLogging.logger {}
 
-    override fun resolve(loader: ComputeWorkloadLoader, random: Random): List<VirtualMachine> {
+    override fun resolve(loader: ComputeWorkloadLoader, random: RandomGenerator): List<VirtualMachine> {
         val vms = source.resolve(loader, random)
         val res = mutableListOf<VirtualMachine>()
 
diff --git a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/TraceComputeWorkload.kt b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/TraceComputeWorkload.kt
index b4e9005f..d9e311cd 100644
--- a/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/TraceComputeWorkload.kt
+++ b/opendc-experiments/opendc-experiments-compute/src/main/kotlin/org/opendc/experiments/compute/internal/TraceComputeWorkload.kt
@@ -25,13 +25,13 @@ package org.opendc.experiments.compute.internal
 import org.opendc.experiments.compute.ComputeWorkload
 import org.opendc.experiments.compute.ComputeWorkloadLoader
 import org.opendc.experiments.compute.VirtualMachine
-import java.util.Random
+import java.util.random.RandomGenerator
 
 /**
  * A [ComputeWorkload] from a trace.
  */
 internal class TraceComputeWorkload(val name: String, val format: String) : ComputeWorkload {
-    override fun resolve(loader: ComputeWorkloadLoader, random: Random): List<VirtualMachine> {
+    override fun resolve(loader: ComputeWorkloadLoader, random: RandomGenerator): List<VirtualMachine> {
         return loader.get(name, format)
     }
 }
diff --git a/opendc-faas/opendc-faas-service/src/main/kotlin/org/opendc/faas/service/router/RandomRoutingPolicy.kt b/opendc-faas/opendc-faas-service/src/main/kotlin/org/opendc/faas/service/router/RandomRoutingPolicy.kt
index 5bd9d4d3..22bf7266 100644
--- a/opendc-faas/opendc-faas-service/src/main/kotlin/org/opendc/faas/service/router/RandomRoutingPolicy.kt
+++ b/opendc-faas/opendc-faas-service/src/main/kotlin/org/opendc/faas/service/router/RandomRoutingPolicy.kt
@@ -24,13 +24,15 @@ package org.opendc.faas.service.router
 
 import org.opendc.faas.service.FunctionObject
 import org.opendc.faas.service.deployer.FunctionInstance
-import kotlin.random.Random
+import java.util.SplittableRandom
+import java.util.random.RandomGenerator
 
 /**
  * A [RoutingPolicy] that selects a random function instance.
  */
-public class RandomRoutingPolicy(private val random: Random = Random(0)) : RoutingPolicy {
+public class RandomRoutingPolicy(private val random: RandomGenerator = SplittableRandom(0)) : RoutingPolicy {
     override fun select(instances: List<FunctionInstance>, function: FunctionObject): FunctionInstance {
-        return instances.random(random)
+        val idx = random.nextInt(instances.size)
+        return instances.elementAt(idx)
     }
 }
diff --git a/opendc-faas/opendc-faas-simulator/src/main/kotlin/org/opendc/faas/simulator/delay/StochasticDelayInjector.kt b/opendc-faas/opendc-faas-simulator/src/main/kotlin/org/opendc/faas/simulator/delay/StochasticDelayInjector.kt
index d3b31bb9..de7b4aa5 100644
--- a/opendc-faas/opendc-faas-simulator/src/main/kotlin/org/opendc/faas/simulator/delay/StochasticDelayInjector.kt
+++ b/opendc-faas/opendc-faas-simulator/src/main/kotlin/org/opendc/faas/simulator/delay/StochasticDelayInjector.kt
@@ -23,13 +23,13 @@
 package org.opendc.faas.simulator.delay
 
 import org.opendc.faas.service.deployer.FunctionInstance
-import java.util.Random
+import java.util.random.RandomGenerator
 import kotlin.math.abs
 
 /*
  * Interface for instance deployment delay estimation.
  */
-public class StochasticDelayInjector(private val model: ColdStartModel, private val random: Random) : DelayInjector {
+public class StochasticDelayInjector(private val model: ColdStartModel, private val random: RandomGenerator) : DelayInjector {
     override fun getColdStartDelay(instance: FunctionInstance): Long {
         val (mean, sd) = model.coldStartParam(instance.function.memorySize.toInt())
         return abs(random.nextGaussian() * sd + mean).toLong()