Repository: vercel/next.js
Pull request: Turbopack: shrink amortized

### What?

Use amortized shrinking.

Capacity should always be a power of 2.
We shrink when len is capacity / 3.
Assuming the capacity was `2^x` we shrink to `2^(x-1)` which is `capacity / 2`.
Therefore capacity is still larger than len, which avoids direct reallocation when items are added again.

Changed files:
filename: turbopack/crates/turbo-tasks-auto-hash-map/src/map.rs
patch: @@ -271,7 +271,9 @@ impl<K: Eq + Hash, V, H: BuildHasher + Default, const I: usize> AutoMap<K, V, H,
         match self {
             AutoMap::List(list) => {
                 if list.capacity() > list.len() * 3 {
-                    list.shrink_to_fit();
+                    // You need to call "grow" to shrink a SmallVec to a specific capacity
+                    // There is no Vec::shrink_to() equivalent for SmallVec
+                    list.grow(list.len().next_power_of_two());
                 }
             }
             AutoMap::Map(map) => {
@@ -280,6 +282,7 @@ impl<K: Eq + Hash, V, H: BuildHasher + Default, const I: usize> AutoMap<K, V, H,
                     list.extend(map.drain());
                     *self = AutoMap::List(list);
                 } else if map.capacity() > map.len() * 3 {
+                    // HashMaps will always have a capacity that is a power of two
                     map.shrink_to_fit();
                 }
             }

filename: turbopack/crates/turbo-tasks-backend/src/backend/mod.rs
patch: @@ -2580,6 +2580,10 @@ impl<B: BackingStorage> TurboTasksBackendInner<B> {
         task.shrink_to_fit(CachedDataItemType::CellDependency);
         task.shrink_to_fit(CachedDataItemType::OutputDependency);
         task.shrink_to_fit(CachedDataItemType::CollectiblesDependency);
+        task.shrink_to_fit(CachedDataItemType::OutdatedOutputDependency);
+        task.shrink_to_fit(CachedDataItemType::OutdatedCellDependency);
+        task.shrink_to_fit(CachedDataItemType::OutdatedCollectiblesDependency);
+        task.shrink_to_fit(CachedDataItemType::OutdatedCollectible);
 
         drop(task);
     }

filename: turbopack/crates/turbo-tasks/src/priority_runner.rs
patch: @@ -176,9 +176,7 @@ impl<
     ) -> Option<(E::Future, Option<Sender<()>>)> {
         let mut queue = self.queue.lock();
         if let Some(heap_item) = queue.pop() {
-            if queue.len() * 2 + 16 < queue.capacity() {
-                queue.shrink_to_fit();
-            }
+            shrink_amortized(&mut queue);
             drop(queue);
             let tx = heap_item.tx;
             Some((
@@ -198,9 +196,7 @@ impl<
     ) -> bool {
         let mut queue = self.queue.lock();
         if let Some(heap_item) = queue.pop() {
-            if queue.len() * 2 + 16 < queue.capacity() {
-                queue.shrink_to_fit();
-            }
+            shrink_amortized(&mut queue);
             drop(queue);
             let tx = heap_item.tx;
             let new_future =
@@ -218,6 +214,15 @@ impl<
     }
 }
 
+fn shrink_amortized<P, T>(queue: &mut BinaryHeap<HeapItem<P, T>>) {
+    // Amortized shrinking of the queue, but with a lower threshold to avoid
+    // frequent reallocations when the queue is small.
+    if queue.capacity() > queue.len() * 3 && queue.capacity() > 128 {
+        let new_capacity = queue.len().next_power_of_two().max(128);
+        queue.shrink_to(new_capacity);
+    }
+}
+
 #[derive(Debug)]
 enum WorkerState {
     UnfinishedFuture,