cheeriojs / cheerio / 30450340954

100%

main: 100%

Pull #5380

github

perf(traversing): keep closest() dedup and map() accumulation linear

Two quadratic accumulation paths, found while auditing for asymmetric
cost.

`closest()` guarded against duplicates with `set.includes(elem)`, a scan
of a growing array. When each element resolves to a distinct ancestor the
result set grows to n and the scan work is n(n-1)/2. Keep the array scan
for the small result sets `closest` normally yields and switch to a Set
once the set passes 100 entries, so ordering and dedup semantics are
unchanged while the pathological case stays linear. A Set from the start
was measured 4-7% slower on ordinary collections, since the allocation
and hashing are paid on every call regardless of result size.

`map()` accumulated with `elems = elems.concat(val)`, rebuilding the
whole array each iteration. Push instead, spreading array return values
with a loop to keep `concat`'s one-level flatten, including its treatment
of `null`/`undefined` members.

closest() over 64k distinct matches: 467ms -> 13.6ms. map() over 40k
elements: 2971ms -> 0.94ms. Ordinary 50-element calls: closest +0.2%
(noise), map ~12x faster. Both regression tests assert operation counts
rather than timings.

265 of 265 branches covered (100.0%)

Branch coverage included in aggregate %.

872 of 877 relevant lines covered (99.43%)

378.8 hits per line