CBlockIndex stores a pointer to previous block..
Is there any specific reason why it does not store a vector of "next" blocks for forward iteration?
If you think, a typical tree (as data structure) has "parent" (pprev) and a list of "children".
Add a comment
|
1 Answer
Memory usage. Adding a vector to each of the (now over 600000) CBlockIndex entries would be a significant memory usage increase (at least 48 bytes per entry, to be precise, on stdc++ 64-bit platforms).
For most operations it's also unnecessary. Instead, CChain stores a pointer to all CBlockIndex entries in the main chain, allowing O(1) access to any of those. Also, using the skiplist mechanism (see pskip) in CBlockIndex it's possible to efficiently find the height N ancestor of any given block (in O(log n) or O((log n)^2), IIRC).
answered Apr 29, 2020 at 18:23
-
Why is it 48 bytes per entry? Shouldn't it be 8 byte per entry? (sizeof(void*)) Commented Apr 29, 2020 at 18:28
-
1A vector has an overhead of 3 pointers (begin of memory block, end of memory block, end of used portion of memory block). The memory block itself is dynamically allocated, which has malloc() overhead (16 to 31 bytes on x86_64 Linux, depending on rounding). Commented Apr 29, 2020 at 18:30