[MLS] Performance measurement of full tree PR

[Richard Barnes <[e-mail]>]

Hi all,

As promised on yesterday's call, I ran some performance metrics on the
"Always use a full tree" PR (#645).  I took a prototype I had of the
tree-hash-based parent hash and extended it to use a full tree.  Note that
I did *not* implement the suppression of redundant nodes, so these trees
have the redundant nodes in them.  The only real bias that that would
introduce here is to do log(n) extra parent hash verifications in the
full-tree case; in other words, the full-tree case should be slightly
better in reality than it is here.

The testing methodology is basically the same as [1]: Make a tree with N
members and see how long it takes the Nth joiner to import the tree.  The
main difference is that since [1] I got a new laptop, so I can go to N=512
instead of just N=256 :)

PDF with plots of full results at [2].  Summary:

* Time to compute tree hash is up to 30% worse, never better
* Time to verify parent hashes is up to 40% better, never worse
* Overall time to ingest a tree (sum of the above) varies between 30% worse
and 20% better

The absolute total ingest time on the high end (512 participants) is on the
order of 60ms, so we’re talking about variations of around plus or minus
15ms.  This is on a current-year M1 MacBook Pro.

The primary driver for whether the full tree does better is how filled-in
the tree is, in the sense of parent nodes being populated.  If even 1/4 of
the tree is filled, then you’re basically always better off with a full
tree, even with 3/4 of leaves unmerged.

Overall, these numbers don’t seem intimidating to me, so I’m inclined to
merge the PR

—Richard

[1] https://mailarchive.ietf.org/arch/msg/mls/QrxmpAzKxoAGKTuzOM3M1UcKFAA/
[2]
https://drive.google.com/file/d/1yQWkmDTKnS1zpkjYb5gn7vmgcjLX0BKt/view?usp=sharing