Bram Cohen [ARCHIVE] on Nostr: 📅 Original date posted:2017-02-28 📝 Original message:On Tue, Feb 28, 2017 at ...
📅 Original date posted:2017-02-28
📝 Original message:On Tue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone <g.andrew.stone at gmail.com>
wrote:
>
> But since transactions' prevouts are not specified by [block height, tx
> index, output index] or by TXO index, I don't understand how an insertion
> ordered TXO tree can result in efficient lookups. Can you help me
> understand this?
>
You have to have a lookup table going from prevouts to txo index. Lookups
on that are relatively fast because looking up things in a hashtable is a
single cache miss, while looking up things in a tree is logarithmic cache
misses.
The purported benefit of using txout is that because recent things are
spent much more than old things, there's a lot of clustering of updates. If
you update two things near each other they share the top branches of
updates in the tree, resulting in less hashing and cache misses. But since
everything is log scale I suspect such benefits are small. My guess is
transaction ordering has much larger potential from compression because you
cram information about lots of things into a single leaf node because they
have very small diffs from each other. That said, those benefits are also
smaller than and accretive to the simple implementation tricks I already
implemented which cause things near each other in the tree to be near each
other in memory.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170228/aa032a07/attachment-0001.html>;
📝 Original message:On Tue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone <g.andrew.stone at gmail.com>
wrote:
>
> But since transactions' prevouts are not specified by [block height, tx
> index, output index] or by TXO index, I don't understand how an insertion
> ordered TXO tree can result in efficient lookups. Can you help me
> understand this?
>
You have to have a lookup table going from prevouts to txo index. Lookups
on that are relatively fast because looking up things in a hashtable is a
single cache miss, while looking up things in a tree is logarithmic cache
misses.
The purported benefit of using txout is that because recent things are
spent much more than old things, there's a lot of clustering of updates. If
you update two things near each other they share the top branches of
updates in the tree, resulting in less hashing and cache misses. But since
everything is log scale I suspect such benefits are small. My guess is
transaction ordering has much larger potential from compression because you
cram information about lots of things into a single leaf node because they
have very small diffs from each other. That said, those benefits are also
smaller than and accretive to the simple implementation tricks I already
implemented which cause things near each other in the tree to be near each
other in memory.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170228/aa032a07/attachment-0001.html>;