diff options
author | Péter Szilágyi <peterke@gmail.com> | 2016-01-22 18:05:17 +0800 |
---|---|---|
committer | Péter Szilágyi <peterke@gmail.com> | 2016-01-22 18:33:34 +0800 |
commit | a2dc074b1ddffaf4e35758835bafe14cca5f0ea7 (patch) | |
tree | b9aa5c904aea0962eb7c103896b6a4ef4c32971c /core/types/transaction.go | |
parent | 78f196409552466ff878a030e4069495a923c73e (diff) | |
download | dexon-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.tar dexon-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.tar.gz dexon-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.tar.bz2 dexon-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.tar.lz dexon-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.tar.xz dexon-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.tar.zst dexon-a2dc074b1ddffaf4e35758835bafe14cca5f0ea7.zip |
core, core/types, miner: fix transaction nonce-price combo sort
Diffstat (limited to 'core/types/transaction.go')
-rw-r--r-- | core/types/transaction.go | 85 |
1 files changed, 69 insertions, 16 deletions
diff --git a/core/types/transaction.go b/core/types/transaction.go index 7a6c5e088..4049ae888 100644 --- a/core/types/transaction.go +++ b/core/types/transaction.go @@ -17,11 +17,13 @@ package types import ( + "container/heap" "crypto/ecdsa" "errors" "fmt" "io" "math/big" + "sort" "sync/atomic" "github.com/ethereum/go-ethereum/common" @@ -302,27 +304,78 @@ func TxDifference(a, b Transactions) (keep Transactions) { return keep } -type TxByNonce struct{ Transactions } +// TxByNonce implements the sort interface to allow sorting a list of transactions +// by their nonces. This is usually only useful for sorting transactions from a +// single account, otherwise a nonce comparison doesn't make much sense. +type TxByNonce Transactions -func (s TxByNonce) Less(i, j int) bool { - return s.Transactions[i].data.AccountNonce < s.Transactions[j].data.AccountNonce -} +func (s TxByNonce) Len() int { return len(s) } +func (s TxByNonce) Less(i, j int) bool { return s[i].data.AccountNonce < s[j].data.AccountNonce } +func (s TxByNonce) Swap(i, j int) { s[i], s[j] = s[j], s[i] } + +// TxByPrice implements both the sort and the heap interface, making it useful +// for all at once sorting as well as individually adding and removing elements. +type TxByPrice Transactions -type TxByPrice struct{ Transactions } +func (s TxByPrice) Len() int { return len(s) } +func (s TxByPrice) Less(i, j int) bool { return s[i].data.Price.Cmp(s[j].data.Price) > 0 } +func (s TxByPrice) Swap(i, j int) { s[i], s[j] = s[j], s[i] } -func (s TxByPrice) Less(i, j int) bool { - return s.Transactions[i].data.Price.Cmp(s.Transactions[j].data.Price) > 0 +func (s *TxByPrice) Push(x interface{}) { + *s = append(*s, x.(*Transaction)) } -type TxByPriceAndNonce struct{ Transactions } +func (s *TxByPrice) Pop() interface{} { + old := *s + n := len(old) + x := old[n-1] + *s = old[0 : n-1] + return x +} -func (s TxByPriceAndNonce) Less(i, j int) bool { - // we can ignore the error here. Sorting shouldn't care about validness - ifrom, _ := s.Transactions[i].From() - jfrom, _ := s.Transactions[j].From() - // favour nonce if they are from the same recipient - if ifrom == jfrom { - return s.Transactions[i].data.AccountNonce < s.Transactions[j].data.AccountNonce +// SortByPriceAndNonce sorts the transactions by price in such a way that the +// nonce orderings within a single account are maintained. +// +// Note, this is not as trivial as it seems from the first look as there are three +// different criteria that need to be taken into account (price, nonce, account +// match), which cannot be done with any plain sorting method, as certain items +// cannot be compared without context. +// +// This method first sorts the separates the list of transactions into individual +// sender accounts and sorts them by nonce. After the account nonce ordering is +// satisfied, the results are merged back together by price, always comparing only +// the head transaction from each account. This is done via a heap to keep it fast. +func SortByPriceAndNonce(txs []*Transaction) { + // Separate the transactions by account and sort by nonce + byNonce := make(map[common.Address][]*Transaction) + for _, tx := range txs { + acc, _ := tx.From() // we only sort valid txs so this cannot fail + byNonce[acc] = append(byNonce[acc], tx) + } + for _, accTxs := range byNonce { + sort.Sort(TxByNonce(accTxs)) + } + // Initialize a price based heap with the head transactions + byPrice := make(TxByPrice, 0, len(byNonce)) + for acc, accTxs := range byNonce { + byPrice = append(byPrice, accTxs[0]) + byNonce[acc] = accTxs[1:] + } + heap.Init(&byPrice) + + // Merge by replacing the best with the next from the same account + txs = txs[:0] + for len(byPrice) > 0 { + // Retrieve the next best transaction by price + best := heap.Pop(&byPrice).(*Transaction) + + // Push in its place the next transaction from the same account + acc, _ := best.From() // we only sort valid txs so this cannot fail + if accTxs, ok := byNonce[acc]; ok && len(accTxs) > 0 { + heap.Push(&byPrice, accTxs[0]) + byNonce[acc] = accTxs[1:] + } + // Accumulate the best priced transaction + txs = append(txs, best) } - return s.Transactions[i].data.Price.Cmp(s.Transactions[j].data.Price) > 0 } |