rules/sdk: flag methods inside sort comparators to avoid quadratic worst case time & memory consumption: instead recommend O(n) computations and memoization of results

[odeke-em]

Summary

If we look at this cosmos-sdk issue cosmos/cosmos-sdk#7766 we can see that it was fixed by cosmos/cosmos-sdk#8719 and one of the root causes was this code

        sort.Slice(balances, func(i, j int) bool {
		addr1, _ := sdk.AccAddressFromBech32(balances[i].Address)
		addr2, _ := sdk.AccAddressFromBech32(balances[j].Address)
		return bytes.Compare(addr1.Bytes(), addr2.Bytes()) < 0
	})

of which sdk.AccAddressFromBech32 is an expensive function that discards prior work inside the quicksort routine which in the worst case is O(n^2) and if we have 100K accounts, that could be (100K * 100K) = 10 million times and if for example each call takes a couple of milliseconds that code can take ages to run and that was the root cause

Recommendation

Our recommendation for that is to recommend that they create a slice whose elements are a struct with the memoized value for the comparator inside an O(n) slice along with the original value, then a sort and then in-place copying thus

        type addrToBalance struct {
		// We use a pointer here to avoid averse effects of value copying
		// wasting RAM all around.
		balance *Balance
		accAddr []byte
	}
	adL := make([]*addrToBalance, 0, len(balances))
	for _, balance := range balances {
		balance.Coins = balance.Coins.Sort()
		balance := balance
		addr, _ := sdk.AccAddressFromBech32(balance.Address)
		adL = append(adL, &addrToBalance{
			balance: &balance,
			accAddr: []byte(addr),
		})
	}

	// 2. Sort with the cheap mapping, using the mapper's
	// already accAddr bytes values which is a cheaper operation.
	sort.Slice(adL, func(i, j int) bool {
		ai, aj := adL[i], adL[j]
		return bytes.Compare(ai.accAddr, aj.accAddr) < 0
	})

	// 3. To complete the sorting, we have to now just insert
	// back the balances in the order returned by the sort.
	for i, ad := range adL {
		balances[i] = *ad.balance
	}
	return balances