From 16caf2ca135da7b4ce5c2e2dbd8b2c5a4f88e847 Mon Sep 17 00:00:00 2001
From: Fabian Mastenbroek <mail.fabianm@gmail.com>
Date: Mon, 11 Oct 2021 20:45:25 +0200
Subject: fix(simulator): Fix queue resizing logic

This change fixes two issues with the resizing logic of the specialized
queue implementations used by the FlowEngine implementation.
---
 .../main/kotlin/org/opendc/simulator/flow/internal/FlowDeque.kt    | 7 +++++--
 .../kotlin/org/opendc/simulator/flow/internal/FlowTimerQueue.kt    | 7 ++++++-
 2 files changed, 11 insertions(+), 3 deletions(-)

(limited to 'opendc-simulator/opendc-simulator-flow/src/main')

diff --git a/opendc-simulator/opendc-simulator-flow/src/main/kotlin/org/opendc/simulator/flow/internal/FlowDeque.kt b/opendc-simulator/opendc-simulator-flow/src/main/kotlin/org/opendc/simulator/flow/internal/FlowDeque.kt
index c6cba4b7..94232954 100644
--- a/opendc-simulator/opendc-simulator-flow/src/main/kotlin/org/opendc/simulator/flow/internal/FlowDeque.kt
+++ b/opendc-simulator/opendc-simulator-flow/src/main/kotlin/org/opendc/simulator/flow/internal/FlowDeque.kt
@@ -25,7 +25,10 @@ package org.opendc.simulator.flow.internal
 import java.util.*
 
 /**
- * A specialized [ArrayDeque] for [FlowConsumerContextImpl] implementations.
+ * A specialized [ArrayDeque] that tracks the [FlowConsumerContextImpl] instances that have updated in an interpreter
+ * cycle.
+ *
+ * By using a specialized class, we reduce the overhead caused by type-erasure.
  */
 internal class FlowDeque(initialCapacity: Int = 256) {
     /**
@@ -106,7 +109,7 @@ internal class FlowDeque(initialCapacity: Int = 256) {
 
         val a = arrayOfNulls<FlowConsumerContextImpl>(newCapacity)
 
-        _elements.copyInto(a, 0, p, r)
+        _elements.copyInto(a, 0, p, n)
         _elements.copyInto(a, r, 0, p)
 
         _elements = a
diff --git a/opendc-simulator/opendc-simulator-flow/src/main/kotlin/org/opendc/simulator/flow/internal/FlowTimerQueue.kt b/opendc-simulator/opendc-simulator-flow/src/main/kotlin/org/opendc/simulator/flow/internal/FlowTimerQueue.kt
index 22a390e6..47061a91 100644
--- a/opendc-simulator/opendc-simulator-flow/src/main/kotlin/org/opendc/simulator/flow/internal/FlowTimerQueue.kt
+++ b/opendc-simulator/opendc-simulator-flow/src/main/kotlin/org/opendc/simulator/flow/internal/FlowTimerQueue.kt
@@ -24,6 +24,9 @@ package org.opendc.simulator.flow.internal
 
 /**
  * Specialized priority queue for flow timers.
+ *
+ * By using a specialized priority queue, we reduce the overhead caused by the default priority queue implementation
+ * being generic.
  */
 internal class FlowTimerQueue(initialCapacity: Int = 256) {
     /**
@@ -46,9 +49,11 @@ internal class FlowTimerQueue(initialCapacity: Int = 256) {
      */
     fun add(ctx: FlowConsumerContextImpl, deadline: Long) {
         val i = size
-        val deadlines = _deadlines
+        var deadlines = _deadlines
         if (i >= deadlines.size) {
             grow()
+            // Re-fetch the resized array
+            deadlines = _deadlines
         }
 
         siftUp(deadlines, _pending, i, ctx, deadline)
-- 
cgit v1.2.3