1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 474F4486
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Feb 2017 23:10:18 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f52.google.com (mail-it0-f52.google.com
[209.85.214.52])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C641A131
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Feb 2017 23:10:17 +0000 (UTC)
Received: by mail-it0-f52.google.com with SMTP id y135so19974472itc.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 28 Feb 2017 15:10:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=bittorrent-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=zCNAfhX9qGo/v2ystgTx0O6M8mSwBhvTNREHmvO4U7M=;
b=WfsZng7zc3sY1mQ4RpPPS0I8GBW/sdVsnZ3Mg/XRMncPwEVj2TYz/nCADojNPJAzIb
lhV80a0yBFcyP4EuwRtA/f/czvHt3Uh1sgoNiTMa4bLdOwUwU3N5AXd9FK+xpavxzu2G
WxRVH+Ow/dZAUsj7EbJZR8dlUHdKE12Cto5O+dS+j3XOz01rB1rbQxZdQPcjxCs6JUfg
LTd33cOEjPQ3WkxSoD1vcfX+u5+sjTgRuv8mjcCZoO4mfVNw3sfWQmlm+Lt7Ftg+HDhw
vedN3CYDeAKtbe0pf4JkLN8/Rlt1in1yheqwyimh8B4bcBYkIsHXyoeepHU+QJCllpee
pfmA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=zCNAfhX9qGo/v2ystgTx0O6M8mSwBhvTNREHmvO4U7M=;
b=Un+gQ+Hl9eu4SHNOb/0Z4v9gm+N+WqLjcniOjUCzGUnzhVxFLWTCTrxOVKt3omA8hZ
JvvO08Dgxgwxx6o0TmQ2LVmMbjybauKfDo2xxVp3oxl7qyo52TSFNaA7Tue9QerVK2mf
mMs97239N79E66cUFtl37aRpOh29Q+KQ5hACDP1WJAQblmSxiC0YnKiqtKPxFeQhr3hL
kwzYBwPACws1iOo31uNLndvi/ojnac0xHa5HVAcRXgtCGHjrEp6YFFIxJ9wW84oy5lGa
bf0Oo0jH4LhJyxInPiCubfGnLBtHk4vdEqZvp5q5tA8fFmPZERUfTRYIkyz3kNV7REV3
hJLQ==
X-Gm-Message-State: AMke39kri1DbiDR/gUQIiFCpwFPS3P8a4Jb1SBOlt3tENCvqjcDfvH2NcurGEdBNMNbObwcLeLg2JJEkt2XYoXOw
X-Received: by 10.36.14.77 with SMTP id 74mr1251383ite.115.1488323417216; Tue,
28 Feb 2017 15:10:17 -0800 (PST)
MIME-Version: 1.0
Received: by 10.36.73.150 with HTTP; Tue, 28 Feb 2017 15:10:16 -0800 (PST)
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
X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Better MMR Definition
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 28 Feb 2017 23:10:18 -0000
--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"><<a href=
=3D"mailto:g.andrew.stone@gmail.com" target=3D"_blank">g.andrew.stone@gmail=
.com</a>></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' 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'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--
|
