Skip to content

Commit a1653e7

Browse files
arnetheduckarnetheduck
authored
Switch VertexRef to inheritance (#3197)
The current VertexRef is a composition of two case object types - this layout is inefficient in that each VertexRef instance takes up as much memory as its largest member. Adding to the insult are the two case fields which each take up space. Here, we use inhertance instead to create optimally sized verticies for each node kind - in particular, the Brach kind kan drop the prefix and reduce its memory usage to a fraction of what it was using before. The memory savings are instead invested in a larger key cache - when processing blocks for live syncing, key lookups are the source of a significant majority (95%) of database reads - when importing, the key cache is simply allotted to verticies instead.
1 parent 4ef2a28 commit a1653e7

26 files changed

+580
-529
lines changed

‎execution_chain/db/aristo/aristo_blobify.nim‎

Lines changed: 98 additions & 90 deletions
Original file line numberDiff line numberDiff line change
@@ -125,40 +125,39 @@ proc load256(data: openArray[byte]; start: var int, len: int): Result[UInt256,Ar
125125
# Public functions
126126
# ------------------------------------------------------------------------------
127127

128-
proc blobifyTo*(pyl: LeafPayload, data: var seq[byte]) =
129-
case pyl.pType
130-
of AccountData:
131-
# `lens` holds `len-1` since `mask` filters out the zero-length case (which
132-
# allows saving 1 bit per length)
133-
var lens: uint16
134-
var mask: byte
135-
if 0 < pyl.account.nonce:
136-
mask = mask or 0x01
137-
let tmp = pyl.account.nonce.blobify()
138-
lens += tmp.len - 1 # 3 bits
139-
data &= tmp.data()
140-
141-
if 0 < pyl.account.balance:
142-
mask = mask or 0x02
143-
let tmp = pyl.account.balance.blobify()
144-
lens += uint16(tmp.len - 1) shl 3 # 5 bits
145-
data &= tmp.data()
146-
147-
if pyl.stoID.isValid:
148-
mask = mask or 0x04
149-
let tmp = pyl.stoID.vid.blobify()
150-
lens += uint16(tmp.len - 1) shl 8 # 3 bits
151-
data &= tmp.data()
152-
153-
if pyl.account.codeHash != EMPTY_CODE_HASH:
154-
mask = mask or 0x08
155-
data &= pyl.account.codeHash.data
156-
157-
data &= lens.toBytesBE()
158-
data &= [mask]
159-
of StoData:
160-
data &= pyl.stoData.blobify().data
161-
data &= [0x20.byte]
128+
proc blobifyTo*(pyl: AccLeafRef, data: var seq[byte]) =
129+
# `lens` holds `len-1` since `mask` filters out the zero-length case (which
130+
# allows saving 1 bit per length)
131+
var lens: uint16
132+
var mask: byte
133+
if 0 < pyl.account.nonce:
134+
mask = mask or 0x01
135+
let tmp = pyl.account.nonce.blobify()
136+
lens += tmp.len - 1 # 3 bits
137+
data &= tmp.data()
138+
139+
if 0 < pyl.account.balance:
140+
mask = mask or 0x02
141+
let tmp = pyl.account.balance.blobify()
142+
lens += uint16(tmp.len - 1) shl 3 # 5 bits
143+
data &= tmp.data()
144+
145+
if pyl.stoID.isValid:
146+
mask = mask or 0x04
147+
let tmp = pyl.stoID.vid.blobify()
148+
lens += uint16(tmp.len - 1) shl 8 # 3 bits
149+
data &= tmp.data()
150+
151+
if pyl.account.codeHash != EMPTY_CODE_HASH:
152+
mask = mask or 0x08
153+
data &= pyl.account.codeHash.data
154+
155+
data &= lens.toBytesBE()
156+
data &= [mask]
157+
158+
proc blobifyTo*(pyl: StoLeafRef, data: var seq[byte]) =
159+
data &= pyl.stoData.blobify().data
160+
data &= [0x20.byte]
162161

163162
proc blobifyTo*(vtx: VertexRef, key: HashKey, data: var seq[byte]) =
164163
## This function serialises the vertex argument to a database record.
@@ -167,51 +166,56 @@ proc blobifyTo*(vtx: VertexRef, key: HashKey, data: var seq[byte]) =
167166
## ::
168167
## Branch:
169168
## <HashKey> -- optional hash key
170-
## [VertexID, ..] -- list of up to 16 child vertices lookup keys
169+
## startVid -- vid of first child vertex
170+
## used -- bitmap of which children are included
171171
## seq[byte] -- hex encoded partial path (non-empty for extension nodes)
172-
## uint64 -- lengths of each child vertex, each taking 4 bits
173-
## 0x80 + xx -- marker(0/2) + pathSegmentLen(6)
172+
## 0xtt + xx -- bits + pathSegmentLen(6)
174173
##
175174
## Leaf:
176175
## seq[byte] -- opaque leaf data payload (might be zero length)
177176
## seq[byte] -- hex encoded partial path (at least one byte)
178-
## 0xc0 + yy -- marker(3) + partialPathLen(6)
179-
##
180-
## For a branch record, the bytes of the `access` array indicate the position
181-
## of the Patricia Trie vertex reference. So the `vertexID` with index `n` has
182-
## ::
183-
## 8 * n * ((access shr (n * 4)) and 15)
177+
## 0xtt + yy -- bits + partialPathLen(6)
184178
##
179+
185180
doAssert vtx.isValid
186181

187-
let
188-
bits =
189-
case vtx.vType
190-
of Branch:
191-
let bits =
182+
template writePfx(vtx, bits: untyped): untyped =
183+
if vtx.pfx.len >= 0:
184+
let pSegm = vtx.pfx.toHexPrefix(isleaf = vtx.vType in Leaves)
185+
data &= pSegm.data()
186+
(bits shl 6) or pSegm.len.byte
187+
else:
188+
(bits shl 6)
189+
190+
let bits =
191+
case vtx.vType
192+
of Branches:
193+
let
194+
vtx = BranchRef(vtx)
195+
bits =
192196
if key.isValid and key.len == 32:
193197
# Shorter keys can be loaded from the vertex directly
194198
data.add key.data()
195199
0b10'u8
196200
else:
197201
0b00'u8
198202

199-
data.add vtx.startVid.blobify().data()
200-
data.add toBytesBE(vtx.used)
201-
bits
202-
of Leaf:
203-
vtx.lData.blobifyTo(data)
204-
0b01'u8
205-
206-
pSegm =
207-
if vtx.pfx.len > 0:
208-
vtx.pfx.toHexPrefix(isleaf = vtx.vType == Leaf)
203+
data.add vtx.startVid.blobify().data()
204+
data.add toBytesBE(vtx.used)
205+
if vtx.vType == ExtBranch:
206+
writePfx(ExtBranchRef(vtx), bits)
209207
else:
210-
default(HexPrefixBuf)
211-
psLen = pSegm.len.byte
212-
213-
data &= pSegm.data()
214-
data &= [(bits shl 6) or psLen]
208+
bits shl 6
209+
of AccLeaf:
210+
let vtx = AccLeafRef(vtx)
211+
vtx.blobifyTo(data)
212+
writePfx(vtx, 0b01'u8)
213+
of StoLeaf:
214+
let vtx = StoLeafRef(vtx)
215+
vtx.blobifyTo(data)
216+
writePfx(vtx, 0b01'u8)
217+
218+
data &= [bits]
215219

216220
proc blobify*(vtx: VertexRef, key: HashKey): seq[byte] =
217221
## Variant of `blobify()`
@@ -230,46 +234,45 @@ proc blobify*(lSst: SavedState): seq[byte] =
230234
lSst.blobifyTo data
231235
data
232236

233-
# -------------
234-
proc deblobify(
237+
proc deblobifyLeaf(
235238
data: openArray[byte];
236-
pyl: var LeafPayload;
237-
): Result[void,AristoError] =
239+
pfx: NibblesBuf;
240+
): Result[VertexRef,AristoError] =
238241
if data.len == 0:
239242
return err(DeblobVtxTooShort)
240243

241244
let mask = data[^1]
242245
if (mask and 0x20) > 0: # Slot storage data
243-
pyl = LeafPayload(
244-
pType: StoData,
245-
stoData: ?deblobify(data.toOpenArray(0, data.len - 2), UInt256))
246-
ok()
246+
ok StoLeafRef.init(
247+
pfx,
248+
?deblobify(data.toOpenArray(0, data.len - 2), UInt256),
249+
)
247250
elif (mask and 0xf0) == 0: # Only account fields set
248-
pyl = LeafPayload(pType: AccountData)
251+
let vtx = AccLeafRef(vType: AccLeaf, pfx: pfx)
249252
var
250253
start = 0
251254
lens = uint16.fromBytesBE(data.toOpenArray(data.len - 3, data.len - 2))
252255

253256
if (mask and 0x01) > 0:
254257
let len = lens and 0b111
255-
pyl.account.nonce = ? load64(data, start, int(len + 1))
258+
vtx.account.nonce = ?load64(data, start, int(len + 1))
256259

257260
if (mask and 0x02) > 0:
258261
let len = (lens shr 3) and 0b11111
259-
pyl.account.balance = ? load256(data, start, int(len + 1))
262+
vtx.account.balance = ?load256(data, start, int(len + 1))
260263

261264
if (mask and 0x04) > 0:
262265
let len = (lens shr 8) and 0b111
263-
pyl.stoID = (true, VertexID(? load64(data, start, int(len + 1))))
266+
vtx.stoID = (true, VertexID(?load64(data, start, int(len + 1))))
264267

265268
if (mask and 0x08) > 0:
266269
if data.len() < start + 32:
267270
return err(DeblobCodeLenUnsupported)
268-
discard pyl.account.codeHash.data.copyFrom(data.toOpenArray(start, start + 31))
271+
discard vtx.account.codeHash.data.copyFrom(data.toOpenArray(start, start + 31))
269272
else:
270-
pyl.account.codeHash = EMPTY_CODE_HASH
273+
vtx.account.codeHash = EMPTY_CODE_HASH
271274

272-
ok()
275+
ok(vtx)
273276
else:
274277
err(DeblobUnknown)
275278

@@ -278,10 +281,15 @@ proc deblobifyType*(record: openArray[byte]; T: type VertexRef):
278281
if record.len < 3: # minimum `Leaf` record
279282
return err(DeblobVtxTooShort)
280283

281-
ok if ((record[^1] shr 6) and 0b01'u8) > 0:
282-
Leaf
284+
let
285+
isLeaf = ((record[^1] shr 6) and 0b01'u8) > 0
286+
psLen = int(record[^1] and 0b00111111)
287+
psPos = record.len - psLen - 1
288+
ok if isLeaf:
289+
let mask = record[psPos - 1]
290+
if (mask and 0x20) > 0: StoLeaf else: AccLeaf
283291
else:
284-
Branch
292+
if psLen > 0: ExtBranch else: Branch
285293

286294
proc deblobify*(
287295
record: openArray[byte];
@@ -294,7 +302,7 @@ proc deblobify*(
294302

295303
let
296304
bits = record[^1] shr 6
297-
vType = if (bits and 0b01'u8) > 0: Leaf else: Branch
305+
isLeaf = (bits and 0b01'u8) > 0
298306
hasKey = (bits and 0b10'u8) > 0
299307
psLen = int(record[^1] and 0b00111111)
300308
start = if hasKey: 32 else: 0
@@ -307,8 +315,8 @@ proc deblobify*(
307315
(_, pathSegment) =
308316
NibblesBuf.fromHexPrefix record.toOpenArray(psPos, record.len - 2)
309317

310-
ok case vType
311-
of Branch:
318+
ok case isLeaf
319+
of false:
312320
var pos = start
313321
let
314322
svLen = psPos - pos - 2
@@ -317,12 +325,12 @@ proc deblobify*(
317325

318326
pos += 2
319327

320-
VertexRef(vType: Branch, pfx: pathSegment, startVid: startVid, used: used)
321-
of Leaf:
322-
let vtx = VertexRef(vType: Leaf, pfx: pathSegment)
323-
324-
?record.toOpenArray(start, psPos - 1).deblobify(vtx.lData)
325-
vtx
328+
if pathSegment.len > 0:
329+
ExtBranchRef.init(pathSegment, startVid, used)
330+
else:
331+
BranchRef.init(startVid, used)
332+
of true:
333+
?record.toOpenArray(start, psPos - 1).deblobifyLeaf(pathSegment)
326334

327335
proc deblobify*(record: openArray[byte], T: type HashKey): Opt[HashKey] =
328336
if record.len > 33 and (((record[^1] shr 6) and 0b10'u8) > 0):

‎execution_chain/db/aristo/aristo_check/check_top.nim‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -87,17 +87,17 @@ proc checkTopCommon*(
8787
if topVid < rvid.vid:
8888
topVid = rvid.vid
8989
case vtx.vType:
90-
of Leaf:
91-
if vtx.lData.pType == AccountData:
92-
let stoID = vtx.lData.stoID
90+
of AccLeaf:
91+
let stoID = AccLeafRef(vtx).stoID
9392
if stoID.isValid:
9493
let stoVid = stoID.vid
9594
if stoVid in stoRoots:
9695
return err((stoVid,CheckAnyVidSharedStorageRoot))
9796
if vTop < stoVid:
9897
return err((stoVid,CheckAnyVidDeadStorageRoot))
9998
stoRoots.incl stoVid
100-
of Branch:
99+
of StoLeaf: discard
100+
of Branches:
101101
block check42Links:
102102
var seen = false
103103
for _, _ in vtx.pairs():

0 commit comments

Comments
 (0)