Merged
Conversation
Contributor
Author
|
TODO:
|
Contributor
Author
|
Looking at Sourcegraph makes me think nobody calls |
dylandreimerink
previously requested changes
Mar 27, 2024
Member
dylandreimerink
left a comment
dylandreimerink
left a comment
There was a problem hiding this comment.
Looks good overall, just the one doc comment
BTF encodes C language constructs such as const, restrict, etc. as
separate types. In most cases we don't care about these when traversing
a type graph. Users can strip these qualifiers by invoking Copy() with a
"transformer" aka UnderlyingType(). Unfortunately, copying is quite
expensive.
For this reason we changed CO-RE relocations to use an unexported as()
function that can be used to "unwrap" a type instead of copying it.
Think of it as a generic version of UnderlyingType. This is much faster
than copying and turns out to be quite ergonomic as well, since we often
have to assert a type anyways.
Export As() so that external users can benefit from it. Usage is like so:
foo, ok := As[*Int](typ)
if !ok {
panic("not an Int")
}
Remove the Transformer type and the extra argument from Copy, since As
is the better way to deal with qualifiers and typedefs. This allows
further simplifying Copy in a follow up commit.
Signed-off-by: Lorenz Bauer <[email protected]>
children is a much better name than walkType, so let's use that. Signed-off-by: Lorenz Bauer <[email protected]>
Rewrite Copy() to use recursion instead of a manually mantained stack. Signed-off-by: Lorenz Bauer <[email protected]>
Throw out the painstakingly hand optimized postorder iterator in favour of
a simple recursive function. Turns out this can be a lot faster for larger
types, probably because the visited map can be allocated on the stack.
There is a small hit to very simple types, but it doesn't seem to affect
overall benchmarks too much.
core: 1
goos: linux
goarch: amd64
pkg: github.com/cilium/ebpf/btf
cpu: 12th Gen Intel(R) Core(TM) i7-1260P
│ base-po.txt │ recursive.txt │
│ sec/op │ sec/op vs base │
PostorderTraversal/single_type 32.22n ± 0% 39.69n ± 0% +23.18% (p=0.002 n=6)
PostorderTraversal/cycle(1) 576.3n ± 3% 112.3n ± 0% -80.51% (p=0.002 n=6)
PostorderTraversal/cycle(10) 2.807µ ± 1% 1.578µ ± 1% -43.80% (p=0.002 n=6)
PostorderTraversal/gov_update_cpu_data 2.039m ± 1% 1.795m ± 1% -11.97% (p=0.002 n=6)
geomean 3.211µ 1.885µ -41.30%
│ base-po.txt │ recursive.txt │
│ B/op │ B/op vs base │
PostorderTraversal/single_type 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=6) ¹
PostorderTraversal/cycle(1) 264.0 ± 0% 0.0 ± 0% -100.00% (p=0.002 n=6)
PostorderTraversal/cycle(10) 716.5 ± 0% 326.0 ± 0% -54.50% (p=0.002 n=6)
PostorderTraversal/gov_update_cpu_data 345.1Ki ± 0% 334.8Ki ± 0% -2.98% (p=0.002 n=6)
geomean ² ? ² ³
¹ all samples are equal
² summaries must be >0 to compute geomean
³ ratios must be >0 to compute geomean
│ base-po.txt │ recursive.txt │
│ allocs/op │ allocs/op vs base │
PostorderTraversal/single_type 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=6) ¹
PostorderTraversal/cycle(1) 4.000 ± 0% 0.000 ± 0% -100.00% (p=0.002 n=6)
PostorderTraversal/cycle(10) 7.000 ± 0% 1.000 ± 0% -85.71% (p=0.002 n=6)
PostorderTraversal/gov_update_cpu_data 132.0 ± 1% 115.0 ± 1% -12.88% (p=0.002 n=6)
geomean ² ? ² ³
¹ all samples are equal
² summaries must be >0 to compute geomean
³ ratios must be >0 to compute geomean
Signed-off-by: Lorenz Bauer <[email protected]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Reduce iterator complexity in the btf package by using recursion. If you have played with the rangefunc proposal you will realise that
visitPostorder,etc. can be turned into aniter.Seqwith a few lines of code. The reason to make this change now (rather than waiting) is that the recursive implementation is easier to reason about and about as fast:Commit messages below.
btf: export As and remove Transformer
btf: rename walkType to children
btf: replace modifyGraphPreorder with recursion
btf: replace postorderIterator with recursion