reflect: add MapIter.Reset #46293

josharian · 2021-05-20T17:20:25Z

Currently, iterating over a map requires two allocations: A reflect.MapIter and a runtime.hiter. By embedding a runtime.hiter (or rather, a type with the same shape and size) in a reflect.MapIter, it is possible to eliminate the second allocation. If we could re-use a reflect.MapIter to iterate over multiple maps, then we could eliminate the first allocation as well.

I propose that we add:

// Reset changes iter to iterate over v.
// It panics if v's Kind is not Map and v is not the zero Value.
func (iter *MapIter) Reset(v Value)

Allowing v to be the zero Value enables the caller to avoid pinning whatever map iter was previously iterating over.

Note that these two would be equivalent:

iter := new(reflect.MapIter)
iter.Reset(mapVal)

iter := mapVal.MapRange()

cc @bradfitz @randall77

This reduces the number of allocations per reflect map iteration from two to one. For golang#46293 Change-Id: Ibcff5f42fc512e637b6e460bad4518e7ac83d4c3

it := new(reflect.MapIter) it.Next() This generates a nil pointer dereference panic from reflect.Value.pointer. Generate a clearer panic. For golang#46293 Change-Id: I32a22c797e1ba3a7b4e70b38ceb4dedb44d264fa

This allows callers to do (amortized) allocation-free iteration over many maps. Fixes golang#46293 Change-Id: I3aa6134dd00da35b508bd1e3b487332a871a3673

gopherbot · 2021-05-21T17:46:26Z

Change https://golang.org/cl/321891 mentions this issue: reflect: add MapIter.Reset

gopherbot · 2021-05-21T17:46:26Z

Change https://golang.org/cl/321890 mentions this issue: reflect: improve panic when MapIter has no associated map Value

gopherbot · 2021-05-21T17:46:27Z

Change https://golang.org/cl/321889 mentions this issue: reflect: allocate hiter as part of MapIter

name old time/op new time/op delta Hash-8 12.4µs ± 0% 12.4µs ± 0% -0.33% (p=0.002 n=10+9) HashMapAcyclic-8 21.2µs ± 0% 21.3µs ± 0% +0.45% (p=0.000 n=8+8) name old alloc/op new alloc/op delta Hash-8 793B ± 0% 408B ± 0% -48.55% (p=0.000 n=10+10) HashMapAcyclic-8 128B ± 0% 0B -100.00% (p=0.000 n=10+10) name old allocs/op new allocs/op delta Hash-8 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10) HashMapAcyclic-8 1.00 ± 0% 0.00 -100.00% (p=0.000 n=10+10) Depends on golang/go#46293. Signed-off-by: Josh Bleecher Snyder <josh@tailscale.com>

This reduces the number of allocations per reflect map iteration from two to one. For golang#46293 (cherry picked from golang.org/cl/321889) Change-Id: Ibcff5f42fc512e637b6e460bad4518e7ac83d4c3

… map Value it := new(reflect.MapIter) it.Next() This generates a nil pointer dereference panic from reflect.Value.pointer. Generate a clearer panic. For golang#46293 (cherry picked from golang.org/cl/321890) Change-Id: I32a22c797e1ba3a7b4e70b38ceb4dedb44d264fa

This allows callers to do (amortized) allocation-free iteration over many maps. Fixes golang#46293 (cherry picked from golang.org/cl/321891) Change-Id: I3aa6134dd00da35b508bd1e3b487332a871a3673

name old time/op new time/op delta Hash-8 12.4µs ± 0% 12.4µs ± 0% -0.33% (p=0.002 n=10+9) HashMapAcyclic-8 21.2µs ± 0% 21.3µs ± 0% +0.45% (p=0.000 n=8+8) name old alloc/op new alloc/op delta Hash-8 793B ± 0% 408B ± 0% -48.55% (p=0.000 n=10+10) HashMapAcyclic-8 128B ± 0% 0B -100.00% (p=0.000 n=10+10) name old allocs/op new allocs/op delta Hash-8 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10) HashMapAcyclic-8 1.00 ± 0% 0.00 -100.00% (p=0.000 n=10+10) Depends on golang/go#46293. Signed-off-by: Josh Bleecher Snyder <josh@tailscale.com>

name old time/op new time/op delta Hash-8 12.4µs ± 0% 12.4µs ± 0% -0.33% (p=0.002 n=10+9) HashMapAcyclic-8 21.2µs ± 0% 21.3µs ± 0% +0.45% (p=0.000 n=8+8) name old alloc/op new alloc/op delta Hash-8 793B ± 0% 408B ± 0% -48.55% (p=0.000 n=10+10) HashMapAcyclic-8 128B ± 0% 0B -100.00% (p=0.000 n=10+10) name old allocs/op new allocs/op delta Hash-8 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10) HashMapAcyclic-8 1.00 ± 0% 0.00 -100.00% (p=0.000 n=10+10) Depends on golang/go#46293. Signed-off-by: Josh Bleecher Snyder <josh@tailscale.com> Signed-off-by: Simeng He <simeng@tailscale.com>

rsc · 2021-06-02T18:00:49Z

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

rsc · 2021-06-09T17:07:40Z

Does anyone object to this proposal?

randall77 · 2021-06-09T17:54:39Z

Seems ok to me.

I think there is a small issue with calling Reset for a map of different type. It constrains somewhat how we represent an hiter inside the compiler. We don't do any such thing currently, but we could for example embed the key by value instead of by pointer. Then on a reset with a different type we'd need to reallocate the hiter which is what you're trying to avoid. But this is all hypothetical and even in the worst case means reflect map iteration would at most become slow/allocatey again.

rsc · 2021-06-16T17:55:22Z

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

rsc · 2021-07-14T18:01:24Z

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group