[Scheduler] Fix de-opt caused by out-of-bounds access (#21147)

Tom910 · acdlite · web-flow · commit 316aa3686544 · 2021-04-05T21:05:02.000-07:00
Scheduler's heap implementation sometimes accesses indices that are out of bounds (larger than the size of the array). This causes a VM de-opt. This change fixes the de-opt by always checking the index before accessing the array. In exchange, we can remove the typecheck on the returned element. Background: https://v8.dev/blog/elements-kinds#avoid-reading-beyond-the-length-of-the-array Co-authored-by: Andrew Clark <git@andrewclark.io>
diff --git a/packages/scheduler/src/SchedulerMinHeap.js b/packages/scheduler/src/SchedulerMinHeap.js
@@ -20,30 +20,28 @@ export function push(heap: Heap, node: Node): void {
 }
 
 export function peek(heap: Heap): Node | null {
-  const first = heap[0];
-  return first === undefined ? null : first;
+  return heap.length === 0 ? null : heap[0];
 }
 
 export function pop(heap: Heap): Node | null {
-  const first = heap[0];
-  if (first !== undefined) {
-    const last = heap.pop();
-    if (last !== first) {
-      heap[0] = last;
-      siftDown(heap, last, 0);
-    }
-    return first;
-  } else {
+  if (heap.length === 0) {
     return null;
   }
+  const first = heap[0];
+  const last = heap.pop();
+  if (last !== first) {
+    heap[0] = last;
+    siftDown(heap, last, 0);
+  }
+  return first;
 }
 
 function siftUp(heap, node, i) {
   let index = i;
-  while (true) {
+  while (index > 0) {
     const parentIndex = (index - 1) >>> 1;
     const parent = heap[parentIndex];
-    if (parent !== undefined && compare(parent, node) > 0) {
+    if (compare(parent, node) > 0) {
       // The parent is larger. Swap positions.
       heap[parentIndex] = node;
       heap[index] = parent;
@@ -58,15 +56,16 @@ function siftUp(heap, node, i) {
 function siftDown(heap, node, i) {
   let index = i;
   const length = heap.length;
-  while (index < length) {
+  const halfLength = length >>> 1;
+  while (index < halfLength) {
     const leftIndex = (index + 1) * 2 - 1;
     const left = heap[leftIndex];
     const rightIndex = leftIndex + 1;
     const right = heap[rightIndex];
 
     // If the left or right node is smaller, swap with the smaller of those.
-    if (left !== undefined && compare(left, node) < 0) {
-      if (right !== undefined && compare(right, left) < 0) {
+    if (compare(left, node) < 0) {
+      if (rightIndex < length && compare(right, left) < 0) {
         heap[index] = right;
         heap[rightIndex] = node;
         index = rightIndex;
@@ -75,7 +74,7 @@ function siftDown(heap, node, i) {
         heap[leftIndex] = node;
         index = leftIndex;
       }
-    } else if (right !== undefined && compare(right, node) < 0) {
+    } else if (rightIndex < length && compare(right, node) < 0) {
       heap[index] = right;
       heap[rightIndex] = node;
       index = rightIndex;
