MIME-Version: 1.0
In-Reply-To: <CAHUwRvtseXUx_ShfHd9r9LW1_8cJYcofQ4s1vEpkpKJEniDTzA@mail.gmail.com>
References: <20170223235105.GA28497@savin.petertodd.org>
	<CA+KqGkowxEZeAFYa2JJchBDtRkg1p3YZNocivzu3fAtgRLDRBQ@mail.gmail.com>
	<20170224010943.GA29218@savin.petertodd.org>
	<CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com>
	<20170224025811.GA31911@savin.petertodd.org>
	<CA+KqGkq7gavAnAk-tcA+gxL2sWpv3ENhEmHrQHaPdyAsKrLjGg@mail.gmail.com>
	<20170224031531.GA32118@savin.petertodd.org>
	<CA+KqGkrfhg3GnbWwvKXHQ2NWuCnfzYyTPUxRhzYMuDBiNQR4eA@mail.gmail.com>
	<20170224043613.GA32502@savin.petertodd.org>
	<CA+KqGkpi4GvgU-K6vt-U5ZN4AkpjZ0rruzddoJS4-V0TcnyqUQ@mail.gmail.com>
	<20170225041202.GA11152@savin.petertodd.org>
	<CA+KqGkqs8F1hK6y-JnLFRpqhQ5i8i+MXVmtGUQBYmE5d1OCAAg@mail.gmail.com>
	<CAHUwRvtseXUx_ShfHd9r9LW1_8cJYcofQ4s1vEpkpKJEniDTzA@mail.gmail.com>
From: Bram Cohen <bram@bittorrent.com>
Date: Tue, 28 Feb 2017 15:10:16 -0800
Message-ID: <CA+KqGkrNDEUB8yzkX+ya1ikb46zmKA6Bt4-skqUgLzo=nnNtUw@mail.gmail.com>
To: "G. Andrew Stone" <g.andrew.stone@gmail.com>
Content-Type: multipart/alternative; boundary=001a1143d75698484405499f4c9b
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Better MMR Definition
Precedence: list

--001a1143d75698484405499f4c9b
Content-Type: text/plain; charset=UTF-8

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.

--001a1143d75698484405499f4c9b
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On T=
ue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone <span dir=3D"ltr">&lt;<a href=
=3D"mailto:g.andrew.stone@gmail.com" target=3D"_blank">g.andrew.stone@gmail=
.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"lt=
r"><div><div><div><br></div>But since transactions&#39; prevouts are not sp=
ecified by [block height, tx index, output index] or by TXO index, I don=
9;t understand how an insertion ordered TXO tree can result in efficient lo=
okups.=C2=A0 Can you help me understand this?<br></div></div></div></blockq=
uote><div><br></div><div>You have to have a lookup table going from prevout=
s to txo index. Lookups on that are relatively fast because looking up thin=
gs in a hashtable is a single cache miss, while looking up things in a tree=
 is logarithmic cache misses.</div><div><br></div><div>The purported benefi=
t of using txout is that because recent things are spent much more than old=
 things, there&#39;s a lot of clustering of updates. If you update two thin=
gs near each other they share the top branches of updates in the tree, resu=
lting 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 e=
ach 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.=C2=A0</div><di=
v><br></div></div></div></div>

--001a1143d75698484405499f4c9b--