winnow only ever reads sel.Nodes; the *Selection parameter was
incidental. Change its signature to winnow(nodes []*html.Node, ...)
and update its three callers (FilterMatcher, NotMatcher,
filterAndPush). filterAndPush no longer needs to fabricate a
throwaway Selection to satisfy the call.
While this change has o measurable runtime effect, it simplifies the code a bit,
by making winnow's signature clearer, and removes a now-useless line and its
associated comment in filterAndPush
getParentNodes ran through mapNodes with a callback that allocated a
throwaway one-element []*html.Node{n.Parent} for every source node. Since
sibling nodes share the same parent, almost all of those slices were
immediately discarded as duplicates.
This commit collects the parents directly in a single loop, deduplicating via a
set as we go, so no per-node slice is allocated.
benchstat (count=10, all p=0.000):
| before | after |
| sec/op | sec/op vs base |
Parent-8 | 38.54µ ± 21%| 17.49µ ± 14% -54.63% |
ParentFiltered-8 | 46.57µ ± 13%| 20.91µ ± 24% -55.09% |
| before | after |
| B/op | B/op vs base |
Parent-8 | 13.24Ki ± 0%| 10.28Ki ± 0% -22.36% |
ParentFiltered-8 | 13.49Ki ± 0%| 10.58Ki ± 0% -21.60% |
| before | after |
| allocs/op | allocs/op vs base |
Parent-8 | 384.0 ± 0% | 10.00 ± 0% -97.40% |
ParentFiltered-8 | 392.0 ± 0% | 19.00 ± 0% -95.15% |
For the sibling types that collect every match (siblingAll,
siblingAllIncludingNonElements, siblingPrevAll, siblingNextAll), do a
cheap first-pass pointer walk to count the matches, then make the result
slice with that exact capacity. This removes the repeated append-driven
slice growth that dominated allocations on these hot traversal paths.
The Until cases are left untouched because counting would require running
the user predicate twice, and the single-result Next/Prev cases have
nothing to presize.
This drives Children/Contents/Siblings/Next*/Prev* through fewer
allocations:
allocs/op vs base B/op vs base
Siblings -57.23% -9.23%
SiblingsFiltered -54.49% -8.94%
NextAll -59.82% -10.04%
NextAllFiltered -55.83% -9.65%
PrevAll -55.32% -10.66%
PrevAllFiltered -52.53% -10.40%
ChildrenFiltered -15.38% -6.45%
Contents -7.69% -1.73%
geomean -25.07% -3.88%
The Until and single Next/Prev benchmarks are unchanged (bit-identical
allocs/op), confirming the count pre-pass only touches the collect-all
paths.
The quite verbose comment on top of the change is there so that future
generations won't waste time wondering why this weird loop is here.
Three internal helpers build a map[*html.Node]bool from a known set of
nodes (or use one as a dedup accumulator over a known number of input
nodes) but allocate the map without a size hint. They then incur
grow-and-double rehashing as entries are inserted.
Pass len(nodes) as the size hint at make time:
- traversal.go mapNodes: dedup map shared by appendWithoutDuplicates
across every per-node result. mapNodes is the engine behind most
traversal helpers (Parents, Children, Next/Prev, Siblings, Find*,
Contents, ...), so the impact is broad.
- traversal.go ClosestNodes: target-node set built from nodes...
- filter.go winnowNodes: large-N path's lookup set built from nodes...
Double-digit performance gains across ~all benchmarks.
mapNodes always allocated a map[*html.Node]bool for deduplication, even
when called with a single source node where duplicates cannot arise.
Short-circuit to return the callback result directly when len(nodes)==1.
Also add a special case for when there are zero nodes.
This benefits all traversal methods (Find, Children, Parent, Next, Prev,
etc.) when operating on a single-node selection, which is the common
case after First(), Eq(), or directly on a Document.
name old ns/op new ns/op delta
Find-8 23200 14200 -38.8%
name old B/op new B/op delta
Find-8 4632 1496 -67.7%
name old allocs new allocs delta
Find-8 27 13 -51.9%
jvoisin