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
Move the "stop at first match" optimization out of HasMatcher and into
singleMatcher, where it can be reused elsewhere.
singleMatcher now implements MatchFirst, which calls the underlying
Matcher's MatchFirst if it provides one (cascadia-compiled matchers all
do), otherwise falls back to MatchAll and returns its first element.
singleMatcher.MatchAll wraps MatchFirst's result in a single-item slice
to respect the Matcher interface, so external SingleMatcher() users get
the slice signature while internal callers can avoid that allocation.
HasMatcher now constructs a singleMatcher directly to call MatchFirst
without a type assertion, removing the duplicated probe branch.
HasMatcher only needs to know whether a child subtree contains a match,
but it tested len(m.MatchAll(c)) > 0 after wrapping the matcher with
SingleMatcher. SingleMatcher.MatchAll computes MatchFirst internally and
then wraps the result in a throwaway []*html.Node{node}, allocating a
one-element slice per matching child subtree just to check a boolean.
When the matcher exposes MatchFirst, probe it directly and test the returned
node against nil, avoiding the allocation entirely. This is the same trick
already used in SingleMatcher.MatchAll, just applied at the HasMatcher call
site so the intermediate slice is never built in the first place. The
SingleMatcher path is kept as a fallback for matchers that don't implement
MatchFirst.
benchstat (count=10):
| before | after |
| sec/op | sec/op vs base|
Has-8 | 2.675µ ± 17% | 2.208µ ± 17% -17.47%|
| before | after |
| B/op | B/op vs base |
Has-8 | 360.0 ± 0% | 240.0 ± 0% -33.33% |
| before | after |
|allocs/op | allocs/op vs base |
Has-8 | 20.00 ± 0% | 6.000 ± 0% -70.00% |
Has(selector) and HasMatcher(m) used to call
s.document.Find(selector)/FindMatcher(m), materializing every matching
descendant in the entire document, then iterate s.Nodes x matchedNodes x
treeDepth via nodeContains to keep the elements that contain one.
This commit probes each selection node's subtree directly with SingleMatcher, which
short-circuits on the first descendant match.
BenchmarkHas (DocW().Find("h2").Has(".editsection")), -count=10:
sec/op B/op
before 61.97µs 744 B
after 3.33µs 360 B
-94.6% -51.6%
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.
HasNodes routed through FilterFunction -> winnowFunction -> grep, which
allocated a single-node Selection and a closure capture per source element,
just to call sel.Contains(n) which is itself a one-iteration sliceContains over
the wrapped node. This commit inlines a direct double loop over s.Nodes x nodes
calling nodeContains, and push the result via pushStack.
name old allocs/op new allocs/op delta
Has-8 55.00 ± 0% 24.00 ± 0% -56.36% (p=0.000)
HasNodes-8 752.00 ± 0% 4.00 ± 0% -99.47% (p=0.000)
HasSelection-8 752.00 ± 0% 3.00 ± 0% -99.60% (p=0.000)
In the same spirit as #545, replaces costly grep() with a loop.
While escape analysis managed to stack-allocate the per-node
Selection through grep's inlining, the closure capture itself (nodes and keep)
was still heap-allocated. Local benchmarks are showing a 30% allocs/op
reduction, and a ~10-20% reduction in sec/op.
The winnow() "Not" path routed through grep(), which called
newSingleSelection() for every node, allocating a Selection and
a 1-element []*html.Node slice on the heap per node, only to
immediately unwrap it via s.Get(0) for m.Match().
This commit call m.Match(n) directly and pre-allocate the result slice.
It also adds BenchmarkNotMatcher to isolate the winnow path from
compileMatcher overhead.
Here are my local benchmark results, for BenchmarkNotMatcher with 373 <li>
nodes, and a pre-compiled matcher:
old ns/op new ns/op delta
22750 19350 ~-15%
old B/op new B/op delta
9384 3120 -66.7%
old allocs new allocs delta
11 2 -81.8%
jvoisin