From: Bram Cohen <bram@bittorrent•com>
To: "G. Andrew Stone" <g.andrew.stone@gmail•com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Better MMR Definition
Date: Tue, 28 Feb 2017 15:10:16 -0800 [thread overview]
Message-ID: <CA+KqGkrNDEUB8yzkX+ya1ikb46zmKA6Bt4-skqUgLzo=nnNtUw@mail.gmail.com> (raw)
In-Reply-To: <CAHUwRvtseXUx_ShfHd9r9LW1_8cJYcofQ4s1vEpkpKJEniDTzA@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 1310 bytes --]
On Tue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone <g.andrew.stone@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.
[-- Attachment #2: Type: text/html, Size: 1730 bytes --]
next prev parent reply other threads:[~2017-02-28 23:10 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-02-23 1:15 Peter Todd
2017-02-23 3:07 ` Bram Cohen
2017-02-23 7:41 ` Peter Todd
2017-02-23 17:53 ` Chris Priest
2017-02-23 18:19 ` Peter Todd
2017-02-23 18:28 ` G. Andrew Stone
2017-02-23 18:31 ` Peter Todd
2017-02-23 23:13 ` Bram Cohen
2017-02-23 23:51 ` Peter Todd
2017-02-24 0:49 ` Bram Cohen
2017-02-24 1:09 ` Peter Todd
2017-02-24 2:50 ` Bram Cohen
2017-02-24 2:58 ` Peter Todd
2017-02-24 3:02 ` Bram Cohen
2017-02-24 3:15 ` Peter Todd
2017-02-24 3:32 ` Bram Cohen
2017-02-24 4:36 ` Peter Todd
2017-02-24 22:20 ` Bram Cohen
2017-02-25 4:12 ` Peter Todd
2017-02-25 6:23 ` Bram Cohen
2017-02-28 16:43 ` G. Andrew Stone
2017-02-28 23:10 ` Bram Cohen [this message]
2017-02-28 23:24 ` Pieter Wuille
2017-03-01 1:47 ` Bram Cohen
2017-03-01 1:56 ` Peter Todd
2017-03-01 22:31 ` Peter Todd
2017-03-31 20:38 ` Bram Cohen
2017-04-01 10:18 ` praxeology_guy
2017-04-01 19:46 ` praxeology_guy
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CA+KqGkrNDEUB8yzkX+ya1ikb46zmKA6Bt4-skqUgLzo=nnNtUw@mail.gmail.com' \
--to=bram@bittorrent$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=g.andrew.stone@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox