reflect: StructOf with very large arrays is slow

[lmb]

What version of Go are you using (go version)?

% go version
go version go1.18.1 darwin/arm64

Does this issue reproduce with the latest release?

Yes.

What did you do?

func TestLargeArray(t *testing.T) {
	elem := reflect.TypeOf(uint32(0))
	arr := reflect.ArrayOf(100_000_000_000, elem)

	fields := []reflect.StructField{
		{Name: "A", Type: arr},
		// This will trigger a lot of time spent in addTypeBits.
		{Name: "B", Type: reflect.TypeOf("")},
	}

	typ := reflect.StructOf(fields)
	for i := 0; i < typ.NumField(); i++ {
		field := typ.Field(i)
		t.Logf("field %d: offset %d", i, field.Offset)
	}
}

What did you expect to see?

I expected creating the type to be fast, though I can see why that is a naive assumption.

What did you see instead?

=== RUN   TestLargeArray
    foo_test.go:103: field 0: offset 0
    foo_test.go:103: field 1: offset 400000000000
--- PASS: TestLargeArray (6.08s)

Running the test takes 6s, most of the time is spent in addTypeBits followed by (*bitVector).append:

(pprof) top3
Showing nodes accounting for 6.57s, 96.76% of 6.79s total
Dropped 5 nodes (cum <= 0.03s)
Showing top 3 nodes out of 25
      flat  flat%   sum%        cum   cum%
     2.71s 39.91% 39.91%      2.88s 42.42%  reflect.(*bitVector).append
     2.36s 34.76% 74.67%      5.24s 77.17%  reflect.addTypeBits
     1.50s 22.09% 96.76%      1.50s 22.09%  runtime.usleep
(pprof) list addTypeBits
Total: 6.79s
ROUTINE ======================== reflect.addTypeBits in /usr/local/go/src/reflect/type.go
     2.36s     10.48s (flat, cum) 154.34% of Total
         .          .   3140:	}
         .          .   3141:
         .          .   3142:	switch Kind(t.kind & kindMask) {
         .          .   3143:	case Chan, Func, Map, Pointer, Slice, String, UnsafePointer:
         .          .   3144:		// 1 pointer at start of representation
     2.07s      2.07s   3145:		for bv.n < uint32(offset/uintptr(goarch.PtrSize)) {
     290ms      3.17s   3146:			bv.append(0)
         .          .   3147:		}
         .          .   3148:		bv.append(1)
         .          .   3149:
         .          .   3150:	case Interface:
         .          .   3151:		// 2 pointers
         .          .   3152:		for bv.n < uint32(offset/uintptr(goarch.PtrSize)) {
         .          .   3153:			bv.append(0)
         .          .   3154:		}
         .          .   3155:		bv.append(1)
         .          .   3156:		bv.append(1)
         .          .   3157:
         .          .   3158:	case Array:
         .          .   3159:		// repeat inner type
         .          .   3160:		tt := (*arrayType)(unsafe.Pointer(t))
         .          .   3161:		for i := 0; i < int(tt.len); i++ {
         .          .   3162:			addTypeBits(bv, offset+uintptr(i)*tt.elem.size, tt.elem)
         .          .   3163:		}
         .          .   3164:
         .          .   3165:	case Struct:
         .          .   3166:		// apply fields
         .          .   3167:		tt := (*structType)(unsafe.Pointer(t))
         .          .   3168:		for i := range tt.fields {
         .          .   3169:			f := &tt.fields[i]
         .      5.24s   3170:			addTypeBits(bv, offset+f.offset(), f.typ)
         .          .   3171:		}
         .          .   3172:	}
         .          .   3173:}

For very large arrays it takes a long time to extend the bitvector one byte at a time, with lots of copying going on etc.

[dr2chase]

@golang/runtime PTAL, seems like has-no-pointers is one of those special cases we could optimize.

[randall77]

Not clear to me that this is worth optimizing. I'd like to understand what the point of such a beast might be.
In any case, the code looks broken for objects >2^35 in size. We only keep 32 bits of bitmap length.

[lmb]

I'm using an RNG to create reflect.Type on the fly to fuzz a package that does type traversal using reflect. Incidentally that also ends up fuzzing reflect itself. There is no specific reason why this type needs to exist, it just leads to the fuzzer bailing out since constructing the type takes so long. I've worked around this by just setting an upper limit on "fake array" sizes.