rpc: O(N**2) batch response matching

[bennetyee]

go-ethereum/rpc/client.go

Lines 367 to 392 in fc1c1cb

	for n := 0; n < len(b) && err == nil; n++ {
	var resp *jsonrpcMessage
	resp, err = op.wait(ctx, c)
	if err != nil {
	break
	}
	// Find the element corresponding to this response.
	// The element is guaranteed to be present because dispatch
	// only sends valid IDs to our channel.
	var elem *BatchElem
	for i := range msgs {
	if bytes.Equal(msgs[i].ID, resp.ID) {
	elem = &b[i]
	break
	}
	}
	if resp.Error != nil {
	elem.Error = resp.Error
	continue
	}
	if len(resp.Result) == 0 {
	elem.Error = ErrNoResult
	continue
	}
	elem.Error = json.Unmarshal(resp.Result, elem.Result)
	}

We scan the N=len(b) responses and for each we scan through msgs to look for the one with an ID that matches. For large batches, if the response ID order is in reverse of the batch order, we can get O(N**2) runtime in the matching.

It may be okay to just add a comment to say do not use large batches in the interface, but ideally this shsould be fixed.

[fjl]

I will fix it.

[muddlebee]

Hey @fjl 👋 !!
did you get a chance to look at this?

[fjl]

No, not yet. I consider this low priority because batch requests are not used much. Even if used, I would consider it rare to use hundreds of requests in one batch. That said, I will fix it as soon as I get to it.