See attached

github_golang_issue_32424_test.go.txt

Please rename the file to .go, and run as below:

mv github_golang_issue_32424_test.go.txt github_golang_issue_32424_test.go
go test -tags "32424" -run Nothing -bench 'Map(Range|ReflectIter|ReflectIndex)' -benchmem  -cpuprofile cpu.out -memprofile mem.out -memprofilerate 1

Got results:

BenchmarkMapRange-8          	   89374	     12812 ns/op	       0 B/op	       0 allocs/op
BenchmarkMapReflectIter-8    	     660	   1805001 ns/op	   16546 B/op	    1026 allocs/op
BenchmarkMapReflectIndex-8   	     576	   2146006 ns/op	   41088 B/op	    1026 allocs/op

For an operation that shouldn't have any allocations, we have a lot.

$ go tool pprof mem.out 
(pprof) top 2
Showing nodes accounting for 38.34MB, 93.02% of 41.21MB total
Dropped 163 nodes (cum <= 0.21MB)
Showing top 2 nodes out of 20
      flat  flat%   sum%        cum   cum%
   22.47MB 54.52% 54.52%    22.47MB 54.52%  reflect.copyVal
   15.87MB 38.50% 93.02%    26.51MB 64.32%  reflect.Value.MapKeys

The allocation is mostly from copyVal (which I traced as being called for each time we convert a map key or value into a reflect.Value, where we call unsafe_New because interfaceIndir(t) returns true.

For Reflect using MapIndex, the call to MapKeys allocates a slice with same length as the map, which is a reason for why MapIter is better. But that (MapIter) still has allocation because of the copyVal function call.

As you see above, with normal range, there is no allocation. And the allocation is completely because the copyVal code does a seemingly unnecessary allocation for composing a reflect.Value from the map key or value.

From my understanding, the reason for this is that reflection works off interface{}, and so we MUST create a pointer for each non-pointer that is wrapped in an interface.

I am hoping there is a way to create an API that works around this. For example, we could pass in a reflect.Value to each call to MapIter.Key() or Value(), and that would be used to pass on Set the value on each iteration?

From my understanding, the reason for this is that reflection works off interface{}, and so we MUST create a pointer for each non-pointer that is wrapped in an interface.

Correct.

I am hoping there is a way to create an API that works around this. For example, we could pass in a reflect.Value to each call to MapIter.Key() or Value(), and that would be used to pass on Set the value on each iteration?

That's a possibility. That would be a pretty ugly API though.

In general there are lots of places (not just map iteration) where reflect is slow because we're putting non-pointers in interfaces. We've historically come down on the side of cleaner API even though there might be faster ways with an uglier API.

For single byte things, we could use runtime.staticbytes. For non-large zero-valued things we could use runtime.zeroval. I don’t know how common those cases are.

@randall77

I am hoping there is a way to create an API that works around this. For example, we could pass in a reflect.Value to each call to MapIter.Key() or Value(), and that would be used to pass on Set the value on each iteration?

That's a possibility. That would be a pretty ugly API though.

In general there are lots of places (not just map iteration) where reflect is slow because we're putting non-pointers in interfaces. We've historically come down on the side of cleaner API even though there might be faster ways with an uglier API.

It's just that I can make a workaround for all other types because I control their location in memory i.e. for a (u)int(|8|16|32|64), float(32|64), bool, string, I can put these in a struct, slice or array or standalone variable, and make an addressable reference. For slices/array (pointers), all elements are already addressable (in general).

However, for maps, because the "slot" can be reused and reclaimed under the hood, we do not expose the allocated space and MUST always re-allocate to expose the entries as an interface{}.

It is thus the case that only map iteration has no workaround.

This is why the option of passing a reference is the only workaround specifically for maps.

I am currently looking to mimic such an interface, leveraging unsafe and cull'ing from the reflection codebase, for API below:

//- look up key, and set val (expecting settable)
//- if return false, then no entry for that key
mapIndex(mapp reflect.Value, key reflect.Value, val reflect.Value) bool
//- creates an iterator, using key and val (expecting both settable) to set the next entries on each iteration
// - if any of key or val is invalid, treat as if a _ was passed to "for ... range"
// 
//- if Next() returns true, then key and val have been set to the next iteration key/value pair
//- if Next() returns false, no more entries
mapIter(key, val reflect.Value) *mapIter
(*mapIter).Next()

IMO, it is not an inelegant API. If retrofited to the current reflection API, it would look like:

// Look up key, and set its mapping into val, returning true if mapping exists
Value.MapIndexUsing(key, val reflect.Value) bool
// Create an iterator, using key and val for each key/value mapping
// Treat as _ if invalid (zero value) allowing us simulate for k, _ = range; _, v = range; k, v = range
Value.MapRangeUsing(key, val reflect.Value) *MapIter

Again, I personally do not see this as an inelegant or unweildly API.

My usecase is the go-codec encoding library: https://github.com/ugorji/go. This is the one place where code-generation is far and away more performant than reflection-based.

Others "encoders" in the space e.g. json-iterator went the way of completely re-writing the reflection package, which I think is extremely fraught with peril: see https://github.com/json-iterator/go https://github.com/modern-go/reflect2 . But they have gotten a lot of mileage doing this, gaining performance equivalent to static codebases.

We could add methods to *reflect.MapIter:

// SetKey does dst.Set(it.Key()).
func (it *MapIter) SetKey(dst Value) { ... }

(and the same for values)

I think that would provide an allocation-free path.

It seems strange to me that we'd provide this optimized path for map iteration, and not for other things that construct a Value. Just scanning value.go, you could make a case for *Recv, Select, Convert, MapIndex, Zero, and Append.

Nice - the methods on *reflect.MapIter work nicely!

I would love to have for MapIndex also, as that is a common use-case. That is the Value.MapIndexUsing(key, dst reflect.Value) reflect.Value above.

Specifically regarding Zero, I always assumed that it would be allocation-free. I thought it would be sufficient to return a readonly non-addressable and non-settable static value as the zero value. That way, every caller gets the same one, but they cannot do much with it except set something else with it or use it readonly.

Regarding Append, there is a somewhat allocation free path with AppendSlice (as you can pass a slice of non-pointers). You can also pass Value which are addressable elements of a slice. So - there is not much of a gap here.

The remaining gaps will be the chan ones (Recv, Select) and Convert. Those are seemingly less common in typical usage (in my limited experience - YMMV). I also do not have a common use for them and do not have any good ideas of how to present it on the API.

I personally would love this, map iteration is a major allocation pain-point where it is being used, and is significantly slower compared to either type-specific cases, or code-gen. Personally I am seeing a ~3x increase in encoding removing special cases for common maps(map[string]interface{}, map[interface{}]interface{} and map[string]string). I was benchmarking those types (map[interface{}]interface{} specifically) but those are the most common map types.

I don't thinks a generic send/recv for channels is very common, so I personally wouldn't see the value if its any difficulty implementing. But if those are trivial to do then I would do so for the sake of keeping the same API.

Zero is being handled in #33136 .

I agree that the channel ones are probably not worth worrying about, performance-wise.

Convert I'm not sure.

But Slice (and the ones that call Slice, like Append and AppendSlice) would be even more important than the map ones, I suspect. @ugorji I didn't understand how you think Append could be made allocation free - could you explain?

I came by the reflect.Append case allocating a new SliceHeader in value.Slice (called by the grow function unconditionally) in an append loop in the last weeks and optimized it by using reflect.MakeSlice and reflectSliceValue.Index(i).Set(...).

If we can reuse the existing pointed to SliceHeader in the reflect.Value and just set the underlying len to the new length we may be able to avoid an allocation per Append call. Seems like this would need a new API e.g. reflect.AppendInplace(s Value, x ...Value) (no return value) since it would be a behaviour change.

@randall77 Sorry, I missed this earlier.

Zero is being handled in #33136 .

I agree that the channel ones are probably not worth worrying about, performance-wise.

Convert I'm not sure.

But Slice (and the ones that call Slice, like Append and AppendSlice) would be even more important than the map ones, I suspect. @ugorji I didn't understand how you think Append could be made allocation free - could you explain?

As @Martish alluded to, a new API like AppendInPlace(s Value, x ...Value) will be needed.

In the same vein, AppendSlice() can elide the allocation caused by the call to s.Slice, by doing something akin to:

Copy(s.Slice(i0, i1), t)

to

p := (*unsafeheader.Slice)(s.ptr)
p0 := *p
p.Data = arrayAt(p0.Data, i0, typ.elem.Size(), "i < cap")
p.Len = i1 - i0
Copy(s, t)
*p = p0

Change https://golang.org/cl/320929 mentions this issue: reflect: add MapIter.SetKey and MapIter.SetValue