aboutsummaryrefslogtreecommitdiffstats
path: root/trie/node.go
diff options
context:
space:
mode:
authorFelix Lange <fjl@twurst.com>2016-10-15 00:04:33 +0800
committerPéter Szilágyi <peterke@gmail.com>2016-10-15 00:04:33 +0800
commit40cdcf1183df235e4b32cfdbf6182a00a0e49f24 (patch)
tree571daa75d1590a47dfe98b67ab1a3350e46ea527 /trie/node.go
parentc2ddfb343a22958324c0c26dae789d3937eece4f (diff)
downloaddexon-40cdcf1183df235e4b32cfdbf6182a00a0e49f24.tar
dexon-40cdcf1183df235e4b32cfdbf6182a00a0e49f24.tar.gz
dexon-40cdcf1183df235e4b32cfdbf6182a00a0e49f24.tar.bz2
dexon-40cdcf1183df235e4b32cfdbf6182a00a0e49f24.tar.lz
dexon-40cdcf1183df235e4b32cfdbf6182a00a0e49f24.tar.xz
dexon-40cdcf1183df235e4b32cfdbf6182a00a0e49f24.tar.zst
dexon-40cdcf1183df235e4b32cfdbf6182a00a0e49f24.zip
trie, core/state: improve memory usage and performance (#3135)
* trie: store nodes as pointers This avoids memory copies when unwrapping node interface values. name old time/op new time/op delta Get 388ns ± 8% 215ns ± 2% -44.56% (p=0.000 n=15+15) GetDB 363ns ± 3% 202ns ± 2% -44.21% (p=0.000 n=15+15) UpdateBE 1.57µs ± 2% 1.29µs ± 3% -17.80% (p=0.000 n=13+15) UpdateLE 1.92µs ± 2% 1.61µs ± 2% -16.25% (p=0.000 n=14+14) HashBE 2.16µs ± 6% 2.18µs ± 6% ~ (p=0.436 n=15+15) HashLE 7.43µs ± 3% 7.21µs ± 3% -2.96% (p=0.000 n=15+13) * trie: close temporary databases in GetDB benchmark * trie: don't keep []byte from DB load around Nodes decoded from a DB load kept hashes and values as sub-slices of the DB value. This can be a problem because loading from leveldb often returns []byte with a cap that's larger than necessary, increasing memory usage. * trie: unload old cached nodes * trie, core/state: use cache unloading for account trie * trie: use explicit private flags (fixes Go 1.5 reflection issue). * trie: fixup cachegen overflow at request of nick * core/state: rename journal size constant
Diffstat (limited to 'trie/node.go')
-rw-r--r--trie/node.go63
1 files changed, 41 insertions, 22 deletions
diff --git a/trie/node.go b/trie/node.go
index b97d370be..de9752c93 100644
--- a/trie/node.go
+++ b/trie/node.go
@@ -30,42 +30,60 @@ var indices = []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b
type node interface {
fstring(string) string
cache() (hashNode, bool)
+ canUnload(cachegen, cachelimit uint16) bool
}
type (
fullNode struct {
Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
- hash hashNode // Cached hash of the node to prevent rehashing (may be nil)
- dirty bool // Cached flag whether the node's new or already stored
+ flags nodeFlag
}
shortNode struct {
Key []byte
Val node
- hash hashNode // Cached hash of the node to prevent rehashing (may be nil)
- dirty bool // Cached flag whether the node's new or already stored
+ flags nodeFlag
}
hashNode []byte
valueNode []byte
)
// EncodeRLP encodes a full node into the consensus RLP format.
-func (n fullNode) EncodeRLP(w io.Writer) error {
+func (n *fullNode) EncodeRLP(w io.Writer) error {
return rlp.Encode(w, n.Children)
}
-// Cache accessors to retrieve precalculated values (avoid lengthy type switches).
-func (n fullNode) cache() (hashNode, bool) { return n.hash, n.dirty }
-func (n shortNode) cache() (hashNode, bool) { return n.hash, n.dirty }
-func (n hashNode) cache() (hashNode, bool) { return nil, true }
-func (n valueNode) cache() (hashNode, bool) { return nil, true }
+func (n *fullNode) copy() *fullNode { copy := *n; return &copy }
+func (n *shortNode) copy() *shortNode { copy := *n; return &copy }
+
+// nodeFlag contains caching-related metadata about a node.
+type nodeFlag struct {
+ hash hashNode // cached hash of the node (may be nil)
+ gen uint16 // cache generation counter
+ dirty bool // whether the node has changes that must be written to the database
+}
+
+// canUnload tells whether a node can be unloaded.
+func (n *nodeFlag) canUnload(cachegen, cachelimit uint16) bool {
+ return !n.dirty && cachegen-n.gen >= cachelimit
+}
+
+func (n *fullNode) canUnload(gen, limit uint16) bool { return n.flags.canUnload(gen, limit) }
+func (n *shortNode) canUnload(gen, limit uint16) bool { return n.flags.canUnload(gen, limit) }
+func (n hashNode) canUnload(uint16, uint16) bool { return false }
+func (n valueNode) canUnload(uint16, uint16) bool { return false }
+
+func (n *fullNode) cache() (hashNode, bool) { return n.flags.hash, n.flags.dirty }
+func (n *shortNode) cache() (hashNode, bool) { return n.flags.hash, n.flags.dirty }
+func (n hashNode) cache() (hashNode, bool) { return nil, true }
+func (n valueNode) cache() (hashNode, bool) { return nil, true }
// Pretty printing.
-func (n fullNode) String() string { return n.fstring("") }
-func (n shortNode) String() string { return n.fstring("") }
-func (n hashNode) String() string { return n.fstring("") }
-func (n valueNode) String() string { return n.fstring("") }
+func (n *fullNode) String() string { return n.fstring("") }
+func (n *shortNode) String() string { return n.fstring("") }
+func (n hashNode) String() string { return n.fstring("") }
+func (n valueNode) String() string { return n.fstring("") }
-func (n fullNode) fstring(ind string) string {
+func (n *fullNode) fstring(ind string) string {
resp := fmt.Sprintf("[\n%s ", ind)
for i, node := range n.Children {
if node == nil {
@@ -76,7 +94,7 @@ func (n fullNode) fstring(ind string) string {
}
return resp + fmt.Sprintf("\n%s] ", ind)
}
-func (n shortNode) fstring(ind string) string {
+func (n *shortNode) fstring(ind string) string {
return fmt.Sprintf("{%x: %v} ", n.Key, n.Val.fstring(ind+" "))
}
func (n hashNode) fstring(ind string) string {
@@ -120,6 +138,7 @@ func decodeShort(hash, buf, elems []byte) (node, error) {
if err != nil {
return nil, err
}
+ flag := nodeFlag{hash: hash}
key := compactDecode(kbuf)
if key[len(key)-1] == 16 {
// value node
@@ -127,17 +146,17 @@ func decodeShort(hash, buf, elems []byte) (node, error) {
if err != nil {
return nil, fmt.Errorf("invalid value node: %v", err)
}
- return shortNode{key, valueNode(val), hash, false}, nil
+ return &shortNode{key, append(valueNode{}, val...), flag}, nil
}
r, _, err := decodeRef(rest)
if err != nil {
return nil, wrapError(err, "val")
}
- return shortNode{key, r, hash, false}, nil
+ return &shortNode{key, r, flag}, nil
}
-func decodeFull(hash, buf, elems []byte) (fullNode, error) {
- n := fullNode{hash: hash}
+func decodeFull(hash, buf, elems []byte) (*fullNode, error) {
+ n := &fullNode{flags: nodeFlag{hash: hash}}
for i := 0; i < 16; i++ {
cld, rest, err := decodeRef(elems)
if err != nil {
@@ -150,7 +169,7 @@ func decodeFull(hash, buf, elems []byte) (fullNode, error) {
return n, err
}
if len(val) > 0 {
- n.Children[16] = valueNode(val)
+ n.Children[16] = append(valueNode{}, val...)
}
return n, nil
}
@@ -176,7 +195,7 @@ func decodeRef(buf []byte) (node, []byte, error) {
// empty node
return nil, rest, nil
case kind == rlp.String && len(val) == 32:
- return hashNode(val), rest, nil
+ return append(hashNode{}, val...), rest, nil
default:
return nil, nil, fmt.Errorf("invalid RLP string size %d (want 0 or 32)", len(val))
}