From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 474F4486 for ; 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 ; Tue, 28 Feb 2017 23:10:17 +0000 (UTC) Received: by mail-it0-f52.google.com with SMTP id y135so19974472itc.1 for ; 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: References: <20170223235105.GA28497@savin.petertodd.org> <20170224010943.GA29218@savin.petertodd.org> <20170224025811.GA31911@savin.petertodd.org> <20170224031531.GA32118@savin.petertodd.org> <20170224043613.GA32502@savin.petertodd.org> <20170225041202.GA11152@savin.petertodd.org> From: Bram Cohen Date: Tue, 28 Feb 2017 15:10:16 -0800 Message-ID: To: "G. Andrew Stone" 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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
On T= ue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone <g.andrew.stone@gmail= .com> wrote:

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?

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.

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

--001a1143d75698484405499f4c9b--