From: Bram Cohen <bram@bittorrent•com>
To: Peter Todd <pete@petertodd•org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Better MMR Definition
Date: Fri, 24 Feb 2017 22:23:20 -0800 [thread overview]
Message-ID: <CA+KqGkqs8F1hK6y-JnLFRpqhQ5i8i+MXVmtGUQBYmE5d1OCAAg@mail.gmail.com> (raw)
In-Reply-To: <20170225041202.GA11152@savin.petertodd.org>
[-- Attachment #1: Type: text/plain, Size: 3731 bytes --]
On Fri, Feb 24, 2017 at 8:12 PM, Peter Todd <pete@petertodd•org> wrote:
>
> So to be clear, what you're proposing there is to use the insertion order
> as
> the index - once you go that far you've almost entirely re-invented my
> proposal!
>
I'm not 'proposing' this, I'm saying it could be done simply but I'm
skeptical of the utility. Probably the most compelling argument for it is
that the insertion indexed values are much smaller so they can be compacted
down a lot resulting in using less memory and more locality and fewer
hashes, but your implementation doesn't take advantage of that.
> Your merkle-set implementation is 1500 lines of densely written Python
The reference implementation which is included in those 1500 lines is less
than 300 lines and fairly straightforward. The non-reference implementation
always behaves semantically identically to the reference implementation, it
just does so faster and using less memory.
> with
> almost no comments,
The comments at the top explain both the proof format and the in-memory
data structures very precisely. The whole codebase was reviewed by a
coworker of mine and comments were added explaining the subtleties which
tripped him up.
> and less than a 100 lines of (also uncommented) tests.
Those tests get 98% code coverage and extensively hit not only the lines of
code but the semantic edge cases as well. The lines which aren't hit are
convenience functions and error conditions of the parsing code for when
it's passed bad data.
> By
> comparison, my Python MMR implementation is 300 lines of very readable
> Python
> with lots of comments, a 200 line explanation at the top, and 200 lines of
> (commented) tests. Yet no-one is taking the (still considerable) effort to
> understand and comment on my implementation. :)
>
Given that maaku's Merkle prefix trees were shelved because of performance
problems despite being written in C and operating in basically the same way
as your code and my reference code, it's clear that non-optimized Python
won't be touching the bitcoin codebase any time soon.
>
> Fact is, what you've written is really daunting to review, and given it's
> not
> in the final language anyway, it's unclear what basis to review it on
> anyway.
It should reviewed based on semantic correctness and performance.
Performance can only be accurately and convincingly determined by porting
to C and optimizing it, which mostly involves experimenting with different
values for the two passed in magic numbers.
> I
> suspect you'd get more feedback if the codebase was better commented, in a
> production language, and you have actual real-world benchmarks and
> performance
> figures.
>
Porting to C should be straightforward. Several people have already
expressed interest in doing so, and it's written in intentionally C-ish
Python, resulting in some rather odd idioms which is a bit part of why you
think it looks 'dense'. A lot of that weird offset math should be much more
readable in C because it's all structs and x.y notation can be used instead
of adding offsets.
> In particular, while at the top of merkle_set.py you have a list of
> advantages,
> and a bunch of TODO's, you don't explain *why* the code has any of these
> advantages. To figure that out, I'd have to read and understand 1500 lines
> of
> densely written Python. Without a human-readable pitch, not many people are
> going to do that, myself included.
>
It's all about cache coherence. When doing operations it pulls in a bunch
of things which are near each other in memory instead of jumping all over
the place. The improvements it gets should be much greater than the ones
gained from insertion ordering, although the two could be accretive.
[-- Attachment #2: Type: text/html, Size: 5256 bytes --]
next prev parent reply other threads:[~2017-02-25 6:23 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 [this message]
2017-02-28 16:43 ` G. Andrew Stone
2017-02-28 23:10 ` Bram Cohen
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+KqGkqs8F1hK6y-JnLFRpqhQ5i8i+MXVmtGUQBYmE5d1OCAAg@mail.gmail.com \
--to=bram@bittorrent$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=pete@petertodd$(echo .)org \
/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