diff options
| author | Michael Pratt <mpratt@google.com> | 2024-10-18 16:17:12 -0400 |
|---|---|---|
| committer | Gopher Robot <gobot@golang.org> | 2024-10-30 15:35:37 +0000 |
| commit | 7b3ac0ca5d168afda5d5c244eeb79aae021ecbe2 (patch) | |
| tree | 1022d088ef8f0b45efa1d61f32d08653630cdee0 /src/internal | |
| parent | d51f92e73751fd8fb7455927ecabd85becd13f06 (diff) | |
| download | go-7b3ac0ca5d168afda5d5c244eeb79aae021ecbe2.tar.xz | |
internal/runtime/maps: avoid table lookup on most Iter.Next calls
Speeds up iteration by about 3%.
For #54766.
Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap
Change-Id: I3406376fb8db87306d52e665fcee1f33cf610f24
Reviewed-on: https://go-review.googlesource.com/c/go/+/621115
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
Diffstat (limited to 'src/internal')
| -rw-r--r-- | src/internal/runtime/maps/table.go | 18 |
1 files changed, 9 insertions, 9 deletions
diff --git a/src/internal/runtime/maps/table.go b/src/internal/runtime/maps/table.go index 59d84761c6..bda74ea41b 100644 --- a/src/internal/runtime/maps/table.go +++ b/src/internal/runtime/maps/table.go @@ -54,6 +54,9 @@ type table struct { // Index of this table in the Map directory. This is the index of the // _first_ location in the directory. The table may occur in multiple // sequential indicies. + // + // index is -1 if the table is stale (no longer installed in the + // directory). index int // groups is an array of slot groups. Each group holds abi.SwissMapGroupSlots @@ -710,15 +713,10 @@ func (it *Iter) Next() { // Continue iteration until we find a full slot. for it.dirIdx < it.m.dirLen { - // TODO(prattmic): We currently look up the latest table on - // every call, even if it.tab is set because the inner loop - // checks if it.tab has grown by checking it.tab != newTab. - // - // We could avoid most of these lookups if we left a flag - // behind on the old table to denote that it is stale. - dirIdx := int((uint64(it.dirIdx) + it.dirOffset) & uint64(it.m.dirLen-1)) - newTab := it.m.directoryAt(uintptr(dirIdx)) + // Find next table. if it.tab == nil { + dirIdx := int((uint64(it.dirIdx) + it.dirOffset) & uint64(it.m.dirLen-1)) + newTab := it.m.directoryAt(uintptr(dirIdx)) if newTab.index != dirIdx { // Normally we skip past all duplicates of the // same entry in the table (see updates to @@ -781,7 +779,7 @@ func (it *Iter) Next() { // We still use our old table to decide which // keys to lookup in order to avoid returning // the same key twice. - grown := it.tab != newTab + grown := it.tab.index == -1 var elem unsafe.Pointer if grown { var ok bool @@ -956,6 +954,7 @@ func (t *table) split(typ *abi.SwissMapType, m *Map) { } m.installTableSplit(t, left, right) + t.index = -1 } // grow the capacity of the table by allocating a new table with a bigger array @@ -999,6 +998,7 @@ func (t *table) grow(typ *abi.SwissMapType, m *Map, newCapacity uint16) { newTable.checkInvariants(typ, m) m.replaceTable(newTable) + t.index = -1 } // probeSeq maintains the state for a probe sequence that iterates through the |