Repository: go
Issue: reflect: StructOf with very large arrays is slow 
Labels: Performance,NeedsInvestigation,compiler/runtime

### What version of Go are you using (`go version`)?

<pre>
% go version
go version go1.18.1 darwin/arm64
</pre>

### 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.