How Lodash pullAllBy Optimizes Array Removal

Lodash's _.pullAllBy method provides a high-performance way to mutate an array by removing elements that match values in a secondary array based on a shared iteratee. Rather than relying on naive, deeply nested loops or multiple expensive array resizes, Lodash applies algorithmic shortcuts, internal caching strategies, and in-place memory management. This article examines the specific optimizations _.pullAllBy uses under the hood to handle large collections of objects efficiently.

Hash-Based Lookup Caching

The most significant performance bottleneck when comparing two arrays is nested iteration (\(O(n \times m)\) complexity). A naive implementation checks every item in the source array against every item in the target values array.

_.pullAllBy resolves this by transforming the target values into an internal cache before scanning the main collection. When the values array exceeds a minimal size threshold, Lodash passes the target values through the iteratee and stores the results in an internal structure called SetCache (which leverages native Set or MapCache depending on the environment). This reduces the lookup cost for each candidate element from linear time (\(O(m)\)) to constant average time (\(O(1)\)), lowering overall complexity to \(O(n + m)\).

Minimizing Iteratee Invocation

Computing iteratee results—such as accessing nested properties via string paths or executing custom transformation functions—incurs execution overhead. Lodash optimizes this by:

Pre-computing target criteria: The iteratee is run across the values list exactly once during cache creation.
On-the-fly source checking: As Lodash steps through the source array, it runs the iteratee once per item and performs an instant membership check against the pre-computed cache.

By ensuring that elements in the values array are not repeatedly re-evaluated against the iteratee during comparisons, CPU cycles are significantly reduced.

In-Place Array Mutation Without Multiple Splices

Standard JavaScript methods like Array.prototype.splice shift every subsequent element in memory whenever an element is removed. Calling splice sequentially inside a loop yields \(O(n^2)\) write operations.

_.pullAllBy mutates the input array directly without repetitive index shifting. Internally, Lodash tracks matching indexes and utilizes an optimized sweep:

It iterates through the original array and writes elements that should be kept forward to their new destination indexes in a single pass.
Once the scan completes, it truncates the array length in a single operation.

This eliminates redundant memory allocations and prevents the garbage collector from having to discard intermediate array copies, making _.pullAllBy vastly more memory-efficient than combinations of Array.prototype.filter and re-assignment.