sort.Slice produce different result from golang v1.19 #327

gzliudan · 2023-10-07T08:05:04Z

gzliudan
Oct 7, 2023
Maintainer

If we use golang v1.19 or higher versions to compile XDPoSChain, then sync would fail, such as reported by #268 and #324. After troubleshooting I found that the function sort.Slice outputs differerent result from golang v1.19 when the stake values are equal.

Eg, for below codes when the block number is 516150:

		for i, m := range ms {
			log.Info("before-sort", "i", i, "address", m.Address.String(), "stake", m.Stake)
		}
		sort.Slice(ms, func(i, j int) bool {
			return ms[i].Stake.Cmp(ms[j].Stake) >= 0
		})
		log.Info("Ordered list of masternode candidates")
		for i, m := range ms {
			log.Info("after-sort", "i", i, "address", m.Address.String(), "stake", m.Stake)
		}
		// update masternodes

		log.Info("Updating new set of masternodes")
		// get block header
		header := bc.CurrentHeader()
		err = engine.UpdateMasternodes(bc, header, ms)
		if err != nil {
			return err
		}
		log.Info("Masternodes are ready for the next epoch")

Golang v1.14-v1.18

INFO [10-07|13:15:31] It's time to update new set of masternodes for the next epoch...
INFO [10-07|13:15:31] before-sort                              ms=19
INFO [10-07|13:15:31] before-sort                              i=0  address=xdc25c65b4b379ac37CF78357c4915f73677022eaFF stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=1  address=xdcC7d49d0a2CF198DeEBd6ce581aF465944ec8b2bB stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=2  address=xdccfCCDeA1006a5CfA7d9484B5b293B46964c265c0 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=3  address=xdc4398241671b3Dd484FE3213A4fB7511f30e7D7C0 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=4  address=xdc9a3787688fD210EC8F8D0224c6c50B8178d75Bc0 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=5  address=xdc7aA125338BE075260e77c6a66A56c90A5DeC4C58 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=6  address=xdc664c4a7B15d91B07c468162f535909114C038b91 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=7  address=xdca65010026b83368Ca05DF6E8B467985D6de3eAC5 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=8  address=xdc065551F0dcAC6f00CAe11192D462db709bE3758c stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=9  address=xdcc67c2DEc79da735d6587d8DB3c23271d557196ab stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=10 address=xdcA4F06BD6E4b217F1FfF9327BDE83da1d41193bE4 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=11 address=xdcFaa7A3c5b5a7f8c9A69f73347F9F28E2B9669d72 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=12 address=xdc595b8170eAF2e53e47cc20db47aD063a1e6e2C0f stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=13 address=xdcA0caeC455E7585d845BBF72420397774e52f3B74 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=14 address=xdc7923B7f78dFfacBb3e1b886e2410630975384C7F stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=15 address=xdced2cE9d056DB8DeF2B4d877c9a80b6f988ae202E stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=16 address=xdcDb2E141595d8Edf6B1CE40b10d57Ca5b83855ec5 stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=17 address=xdc0eaa5c2F0929C95ED0280e8840A2416C4EF16E9d stake=10000000000000000000000000
INFO [10-07|13:15:31] before-sort                              i=18 address=xdc72fb467Ef6dA285b6B0D8f7A25AbD6049385d5fD stake=10000000000000000000000000
INFO [10-07|13:15:31] Ordered list of masternode candidates
INFO [10-07|13:15:31] after-sort                               ms=19
INFO [10-07|13:15:31] after-sort                               i=0  address=xdc9a3787688fD210EC8F8D0224c6c50B8178d75Bc0 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=1  address=xdc4398241671b3Dd484FE3213A4fB7511f30e7D7C0 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=2  address=xdccfCCDeA1006a5CfA7d9484B5b293B46964c265c0 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=3  address=xdcC7d49d0a2CF198DeEBd6ce581aF465944ec8b2bB stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=4  address=xdcFaa7A3c5b5a7f8c9A69f73347F9F28E2B9669d72 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=5  address=xdc7aA125338BE075260e77c6a66A56c90A5DeC4C58 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=6  address=xdcA4F06BD6E4b217F1FfF9327BDE83da1d41193bE4 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=7  address=xdc72fb467Ef6dA285b6B0D8f7A25AbD6049385d5fD stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=8  address=xdcDb2E141595d8Edf6B1CE40b10d57Ca5b83855ec5 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=9  address=xdc7923B7f78dFfacBb3e1b886e2410630975384C7F stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=10 address=xdc595b8170eAF2e53e47cc20db47aD063a1e6e2C0f stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=11 address=xdcA0caeC455E7585d845BBF72420397774e52f3B74 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=12 address=xdc664c4a7B15d91B07c468162f535909114C038b91 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=13 address=xdced2cE9d056DB8DeF2B4d877c9a80b6f988ae202E stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=14 address=xdca65010026b83368Ca05DF6E8B467985D6de3eAC5 stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=15 address=xdc0eaa5c2F0929C95ED0280e8840A2416C4EF16E9d stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=16 address=xdc065551F0dcAC6f00CAe11192D462db709bE3758c stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=17 address=xdc25c65b4b379ac37CF78357c4915f73677022eaFF stake=10000000000000000000000000
INFO [10-07|13:15:31] after-sort                               i=18 address=xdcc67c2DEc79da735d6587d8DB3c23271d557196ab stake=10000000000000000000000000
INFO [10-07|13:15:31] Updating new set of masternodes
INFO [10-07|13:15:31] New set of masternodes has been updated to snapshot number=516150 hash=25a20f…bc50cd new masternodes="[xdc9a3787688fD210EC8F8D0224c6c50B8178d75Bc0 xdc4398241671b3Dd484FE3213A4fB7511f30e7D7C0 xdccfCCDeA1006a5CfA7d9484B5b293B46964c265c0 xdcC7d49d0a2CF198DeEBd6ce581aF465944ec8b2bB xdcFaa7A3c5b5a7f8c9A69f73347F9F28E2B9669d72 xdc7aA125338BE075260e77c6a66A56c90A5DeC4C58 xdcA4F06BD6E4b217F1FfF9327BDE83da1d41193bE4 xdc72fb467Ef6dA285b6B0D8f7A25AbD6049385d5fD xdcDb2E141595d8Edf6B1CE40b10d57Ca5b83855ec5 xdc7923B7f78dFfacBb3e1b886e2410630975384C7F xdc595b8170eAF2e53e47cc20db47aD063a1e6e2C0f xdcA0caeC455E7585d845BBF72420397774e52f3B74 xdc664c4a7B15d91B07c468162f535909114C038b91 xdced2cE9d056DB8DeF2B4d877c9a80b6f988ae202E xdca65010026b83368Ca05DF6E8B467985D6de3eAC5 xdc0eaa5c2F0929C95ED0280e8840A2416C4EF16E9d xdc065551F0dcAC6f00CAe11192D462db709bE3758c xdc25c65b4b379ac37CF78357c4915f73677022eaFF]"
INFO [10-07|13:15:31] Masternodes are ready for the next epoch

The address xdcc67c2DEc79da735d6587d8DB3c23271d557196ab is cut off.

Golang v1.19-v1.21

INFO [10-07|14:43:42] It's time to update new set of masternodes for the next epoch...
INFO [10-07|14:43:42] before-sort                              ms=19
INFO [10-07|14:43:42] before-sort                              i=0  address=xdc25c65b4b379ac37CF78357c4915f73677022eaFF stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=1  address=xdcC7d49d0a2CF198DeEBd6ce581aF465944ec8b2bB stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=2  address=xdccfCCDeA1006a5CfA7d9484B5b293B46964c265c0 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=3  address=xdc4398241671b3Dd484FE3213A4fB7511f30e7D7C0 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=4  address=xdc9a3787688fD210EC8F8D0224c6c50B8178d75Bc0 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=5  address=xdc7aA125338BE075260e77c6a66A56c90A5DeC4C58 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=6  address=xdc664c4a7B15d91B07c468162f535909114C038b91 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=7  address=xdca65010026b83368Ca05DF6E8B467985D6de3eAC5 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=8  address=xdc065551F0dcAC6f00CAe11192D462db709bE3758c stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=9  address=xdcc67c2DEc79da735d6587d8DB3c23271d557196ab stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=10 address=xdcA4F06BD6E4b217F1FfF9327BDE83da1d41193bE4 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=11 address=xdcFaa7A3c5b5a7f8c9A69f73347F9F28E2B9669d72 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=12 address=xdc595b8170eAF2e53e47cc20db47aD063a1e6e2C0f stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=13 address=xdcA0caeC455E7585d845BBF72420397774e52f3B74 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=14 address=xdc7923B7f78dFfacBb3e1b886e2410630975384C7F stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=15 address=xdced2cE9d056DB8DeF2B4d877c9a80b6f988ae202E stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=16 address=xdcDb2E141595d8Edf6B1CE40b10d57Ca5b83855ec5 stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=17 address=xdc0eaa5c2F0929C95ED0280e8840A2416C4EF16E9d stake=10000000000000000000000000
INFO [10-07|14:43:42] before-sort                              i=18 address=xdc72fb467Ef6dA285b6B0D8f7A25AbD6049385d5fD stake=10000000000000000000000000
INFO [10-07|14:43:42] Ordered list of masternode candidates
INFO [10-07|14:43:42] after-sort                               ms=19
INFO [10-07|14:43:42] after-sort                               i=0  address=xdcFaa7A3c5b5a7f8c9A69f73347F9F28E2B9669d72 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=1  address=xdcc67c2DEc79da735d6587d8DB3c23271d557196ab stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=2  address=xdc664c4a7B15d91B07c468162f535909114C038b91 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=3  address=xdcC7d49d0a2CF198DeEBd6ce581aF465944ec8b2bB stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=4  address=xdc25c65b4b379ac37CF78357c4915f73677022eaFF stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=5  address=xdcA0caeC455E7585d845BBF72420397774e52f3B74 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=6  address=xdced2cE9d056DB8DeF2B4d877c9a80b6f988ae202E stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=7  address=xdc9a3787688fD210EC8F8D0224c6c50B8178d75Bc0 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=8  address=xdc72fb467Ef6dA285b6B0D8f7A25AbD6049385d5fD stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=9  address=xdcA4F06BD6E4b217F1FfF9327BDE83da1d41193bE4 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=10 address=xdcDb2E141595d8Edf6B1CE40b10d57Ca5b83855ec5 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=11 address=xdc595b8170eAF2e53e47cc20db47aD063a1e6e2C0f stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=12 address=xdc7923B7f78dFfacBb3e1b886e2410630975384C7F stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=13 address=xdccfCCDeA1006a5CfA7d9484B5b293B46964c265c0 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=14 address=xdc7aA125338BE075260e77c6a66A56c90A5DeC4C58 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=15 address=xdc4398241671b3Dd484FE3213A4fB7511f30e7D7C0 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=16 address=xdca65010026b83368Ca05DF6E8B467985D6de3eAC5 stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=17 address=xdc0eaa5c2F0929C95ED0280e8840A2416C4EF16E9d stake=10000000000000000000000000
INFO [10-07|14:43:42] after-sort                               i=18 address=xdc065551F0dcAC6f00CAe11192D462db709bE3758c stake=10000000000000000000000000
INFO [10-07|14:43:42] Updating new set of masternodes
INFO [10-07|14:43:42] New set of masternodes has been updated to snapshot number=516150 hash=25a20f…bc50cd new masternodes="[xdcFaa7A3c5b5a7f8c9A69f73347F9F28E2B9669d72 xdcc67c2DEc79da735d6587d8DB3c23271d557196ab xdc664c4a7B15d91B07c468162f535909114C038b91 xdcC7d49d0a2CF198DeEBd6ce581aF465944ec8b2bB xdc25c65b4b379ac37CF78357c4915f73677022eaFF xdcA0caeC455E7585d845BBF72420397774e52f3B74 xdced2cE9d056DB8DeF2B4d877c9a80b6f988ae202E xdc9a3787688fD210EC8F8D0224c6c50B8178d75Bc0 xdc72fb467Ef6dA285b6B0D8f7A25AbD6049385d5fD xdcA4F06BD6E4b217F1FfF9327BDE83da1d41193bE4 xdcDb2E141595d8Edf6B1CE40b10d57Ca5b83855ec5 xdc595b8170eAF2e53e47cc20db47aD063a1e6e2C0f xdc7923B7f78dFfacBb3e1b886e2410630975384C7F xdccfCCDeA1006a5CfA7d9484B5b293B46964c265c0 xdc7aA125338BE075260e77c6a66A56c90A5DeC4C58 xdc4398241671b3Dd484FE3213A4fB7511f30e7D7C0 xdca65010026b83368Ca05DF6E8B467985D6de3eAC5 xdc0eaa5c2F0929C95ED0280e8840A2416C4EF16E9d]"
INFO [10-07|14:43:42] Masternodes are ready for the next epoch

The address xdc065551F0dcAC6f00CAe11192D462db709bE3758c is cut off.

Reason

The release node of golang v1.19 said:

[sort](https://go.dev/pkg/sort/)

The sorting algorithm has been rewritten to use [pattern-defeating quicksort](https://arxiv.org/pdf/2106.05123.pdf), which is faster for several common scenarios.

Solution

We can make the sorting results completely determined by the data, such as:

		sort.Slice(ms, func(i, j int) bool {
			return ms[i].Stake.Cmp(ms[j].Stake) > 0
		})

Or:

        sort.Slice(ms, func(i, j int) bool {
            c := ms[i].Stake.Cmp(ms[j].Stake)
            return c > 0 || (c == 0 && bytes.Compare(ms[i].Address[:], ms[j].Address[:]) > 0)
        })

gzliudan · 2024-04-24T09:35:58Z

gzliudan
Apr 24, 2024
Maintainer Author

This problem is solved by PR #338.

0 replies

Navigation Menu

Uh oh!

sort.Slice produce different result from golang v1.19 #327

Uh oh!

{{title}}

Uh oh!

Uh oh!

{{editor}}'s edit

{{editor}}'s edit

Uh oh!

Replies: 1 comment

Uh oh!

{{title}}

Uh oh!

Select a reply

Uh oh!

Uh oh!

sort.Slice produce different result from golang v1.19 #327

Uh oh!

Uh oh!

gzliudan Oct 7, 2023 Maintainer

Replies: 1 comment

Uh oh!

gzliudan Apr 24, 2024 Maintainer Author

gzliudan
Oct 7, 2023
Maintainer

gzliudan
Apr 24, 2024
Maintainer Author