From 2ea4b81bfc6a041be08fa477321c513249c86bd6 Mon Sep 17 00:00:00 2001 From: Tim King Date: Thu, 15 Dec 2022 20:59:08 -0800 Subject: go/ast/inspector: skip ranges that do not contain a node type Skips inspecting a range of nodes that do not contain any nodes of a given type. Computes a bitmask of type nodes between push and pop events. Skips forward to pop if nodes in between cannot match the type mask. Benchmarking against previous implementation on "net": - Preorder filtered by *ast.FuncDecl and *ast.FuncLit traversal is faster by 11x. - Preorder filtered by *ast.CallExpr is faster by 10%. - Unfiltered traveral is 5% slower. - Constructing events 3% slower. - Break even for additional computation is 5 *CallExpr filtered traversals or 1 *Func{Decl,Lit} filtered traversal. Change-Id: If4cb566474b84186ff42fb80ed7e1ebb0f692cc2 Reviewed-on: https://go-review.googlesource.com/c/tools/+/458075 TryBot-Result: Gopher Robot Run-TryBot: Tim King Reviewed-by: Alan Donovan --- go/ast/inspector/inspector_test.go | 44 +++++++++++++++++++++++++++++++++++--- 1 file changed, 41 insertions(+), 3 deletions(-) (limited to 'go/ast/inspector/inspector_test.go') diff --git a/go/ast/inspector/inspector_test.go b/go/ast/inspector/inspector_test.go index 9e5391896..e88d584b5 100644 --- a/go/ast/inspector/inspector_test.go +++ b/go/ast/inspector/inspector_test.go @@ -244,9 +244,11 @@ func typeOf(n ast.Node) string { // but a break-even point (NewInspector/(ASTInspect-Inspect)) of about 5 // traversals. // -// BenchmarkNewInspector 4.5 ms -// BenchmarkNewInspect 0.33ms -// BenchmarkASTInspect 1.2 ms +// BenchmarkASTInspect 1.0 ms +// BenchmarkNewInspector 2.2 ms +// BenchmarkInspect 0.39ms +// BenchmarkInspectFilter 0.01ms +// BenchmarkInspectCalls 0.14ms func BenchmarkNewInspector(b *testing.B) { // Measure one-time construction overhead. @@ -274,6 +276,42 @@ func BenchmarkInspect(b *testing.B) { } } +func BenchmarkInspectFilter(b *testing.B) { + b.StopTimer() + inspect := inspector.New(netFiles) + b.StartTimer() + + // Measure marginal cost of traversal. + nodeFilter := []ast.Node{(*ast.FuncDecl)(nil), (*ast.FuncLit)(nil)} + var ndecls, nlits int + for i := 0; i < b.N; i++ { + inspect.Preorder(nodeFilter, func(n ast.Node) { + switch n.(type) { + case *ast.FuncDecl: + ndecls++ + case *ast.FuncLit: + nlits++ + } + }) + } +} + +func BenchmarkInspectCalls(b *testing.B) { + b.StopTimer() + inspect := inspector.New(netFiles) + b.StartTimer() + + // Measure marginal cost of traversal. + nodeFilter := []ast.Node{(*ast.CallExpr)(nil)} + var ncalls int + for i := 0; i < b.N; i++ { + inspect.Preorder(nodeFilter, func(n ast.Node) { + _ = n.(*ast.CallExpr) + ncalls++ + }) + } +} + func BenchmarkASTInspect(b *testing.B) { var ndecls, nlits int for i := 0; i < b.N; i++ { -- cgit v1.2.3