From fa8470a8cd42a0ceff315232ec7e8a30ed1ff7d3 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Wed, 1 May 2019 18:02:14 +0000 Subject: runtime: make treap iteration more efficient This change introduces a treapIterFilter type which represents the power set of states described by a treapIterType. This change then adds a treapIterFilter field to each treap node indicating the types of spans that live in that subtree. The field is maintained via the same mechanism used to maintain maxPages. This allows pred, succ, start, and end to be judicious about which subtrees it will visit, ensuring that iteration avoids traversing irrelevant territory. Without this change, repeated scavenging attempts can end up being N^2 as the scavenger walks over what it already scavenged before finding new spans available for scavenging. Finally, this change also only scavenges a span once it is removed from the treap. There was always an invariant that spans owned by the treap may not be mutated in-place, but with this change violating that invariant can cause issues with scavenging. For #30333. Change-Id: I8040b997e21c94a8d3d9c8c6accfe23cebe0c3d3 Reviewed-on: https://go-review.googlesource.com/c/go/+/174878 Run-TryBot: Michael Knyszek TryBot-Result: Gobot Gobot Reviewed-by: Austin Clements --- src/runtime/export_test.go | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-) (limited to 'src/runtime/export_test.go') diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go index cbd210bd2e..e6b82bd728 100644 --- a/src/runtime/export_test.go +++ b/src/runtime/export_test.go @@ -546,15 +546,21 @@ func (s Span) Pages() uintptr { return s.mspan.npages } -type TreapIterType int +type TreapIterType treapIterType const ( TreapIterScav TreapIterType = TreapIterType(treapIterScav) TreapIterBits = treapIterBits ) +type TreapIterFilter treapIterFilter + +func TreapFilter(mask, match TreapIterType) TreapIterFilter { + return TreapIterFilter(treapFilter(treapIterType(mask), treapIterType(match))) +} + func (s Span) MatchesIter(mask, match TreapIterType) bool { - return s.mspan.matchesIter(treapIterType(mask), treapIterType(match)) + return treapFilter(treapIterType(mask), treapIterType(match)).matches(s.treapFilter()) } type TreapIter struct { @@ -639,5 +645,5 @@ func (t *Treap) Size() int { func (t *Treap) CheckInvariants() { t.mTreap.treap.walkTreap(checkTreapNode) - t.mTreap.treap.validateMaxPages() + t.mTreap.treap.validateInvariants() } -- cgit v1.3