Repository: facebook/react
Pull request: [perf] Improve SchedulerMinHeap implementation

Migrated to a new algorithm that does not go beyond the array, thus de-optimization of this piece of code is not happening

<!--
  Thanks for submitting a pull request!
  We appreciate you spending the time to work on these changes. Please provide enough information so that others can review your pull request. The three fields below are mandatory.

  Before submitting a pull request, please make sure the following is done:

  1. Fork [the repository](https://github.com/facebook/react) and create your branch from `master`.
  2. Run `yarn` in the repository root.
  3. If you've fixed a bug or added code that should be tested, add tests!
  4. Ensure the test suite passes (`yarn test`). Tip: `yarn test --watch TestName` is helpful in development.
  5. Run `yarn test --prod` to test in the production environment. It supports the same options as `yarn test`.
  6. If you need a debugger, run `yarn debug-test --watch TestName`, open `chrome://inspect`, and press "Inspect".
  7. Format your code with [prettier](https://github.com/prettier/prettier) (`yarn prettier`).
  8. Make sure your code lints (`yarn lint`). Tip: `yarn linc` to only check changed files.
  9. Run the [Flow](https://flowtype.org/) type checks (`yarn flow`).
  10. If you haven't already, complete the CLA.

  Learn more about contributing: https://reactjs.org/docs/how-to-contribute.html
-->

## Summary

<!-- Explain the **motivation** for making this change. What existing problem does the pull request solve? -->

I investigated the package scheduler and observed that the current implementation MinHeap reading beyond the length of the array. MinHeap is hot type code and I had decided to improve the current implementation

Result
```
❯ node -v
v14.15.5

❯ node bench.js
master branche - small number of elements x 17,740 ops/sec ±1.50% (85 runs sampled)
master branche - large number of elements x 1,430 ops/sec ±1.10% (71 runs sampled)

current branche - small number of elements x 441,482 ops/sec ±0.60% (95 runs sampled)
current branche - large number of elements x 14,038 ops/sec ±1.17% (91 runs sampled)
```

Proofs why it's work that

> reading array[42] when array.length === 5. In this case, the array index 42 is out of bounds, the property is not present on the array itself, and so the JavaScript engine has to perform expensive prototype chain lookups. Once a load has run into this situation, V8 remembers that “this load needs to deal with special cases”, and it will never be as fast again as it was before reading out-of-bounds.

url - [https://v8.dev/blog/elements-kinds#avoid-reading-beyond-the-length-of-the-array](https://v8.dev/blog/elements-kinds#avoid-reading-beyond-the-length-of-the-array)

## Test Plan

<!-- Demonstrate the code is solid. Example: The exact commands you ran and their output, screenshots / videos if the pull request changes the user interface. -->


Changed files:
filename: packages/scheduler/src/SchedulerMinHeap.js
patch: @@ -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;