cheeriojs / cheerio
100%
main: 100%

LAST BUILD BRANCH: chore/eslint-config-0.5
DEFAULT BRANCH: main
Repo Added
Files 16
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst

LAST BUILD ON BRANCH perf/closest-map-linear
branch: perf/closest-map-linear
CHANGE BRANCH
x

coverage: 99.562% (+0.004%) from 99.558%
30450340954

Pull #5380

github

fb55 
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.
Pull Request #5380: perf(traversing): keep closest() dedup and map() accumulation linear

265 of 265 branches covered (100.0%)

Branch coverage included in aggregate %.

10 of 0 new or added lines in 0 files covered. (NaN%)

872 of 877 relevant lines covered (99.43%)

378.8 hits per line

Relevant lines Covered
877 RELEVANT LINES 872 COVERED LINES
378.8 HITS PER LINE
Source Files on perf/closest-map-linear

Recent builds

Builds Branch Commit Type Ran Committer Via Coverage
30450340954 perf/closest-map-linear 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 ea... Pull #5380 fb55 github
99.56
30450342029 perf/closest-map-linear Merge 208682b50 into a8e5b000e Pull #5380 web-flow github
99.56
30449700084 perf/closest-map-linear Apply suggestions from code review Co-authored-by: Copilot Autofix powered by AI <175728472+Copilot@users.noreply.github.com> Pull #5380 web-flow github
99.56
30449305621 perf/closest-map-linear Merge 6f6191b7b into 71fa54581 Pull #5380 web-flow github
99.56
30449269865 perf/closest-map-linear 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 ea... push fb55 github
99.56
See All Builds (5436)