Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

reflect: StructOf with very large arrays is slow #52741

Open
lmb opened this issue May 6, 2022 · 3 comments
Open

reflect: StructOf with very large arrays is slow #52741

lmb opened this issue May 6, 2022 · 3 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Unplanned

Comments

@lmb
Copy link
Contributor

lmb commented May 6, 2022

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 dr2chase added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels May 6, 2022
@dr2chase
Copy link
Contributor

dr2chase commented May 6, 2022

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

@randall77
Copy link
Contributor

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
Copy link
Contributor Author

lmb commented May 6, 2022

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.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 7, 2022
@seankhliao seankhliao added this to the Unplanned milestone Aug 20, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
Go Compiler / Runtime
Status: Triage Backlog
Milestone
Unplanned
Development

No branches or pull requests
5 participants
@lmb @dr2chase @randall77 @gopherbot @seankhliao