Performance of id_tree

[dalance]

I investigated the performance of id_tree.
In the flamegraph, many time is consumed by PartialEq of ProcessUniqueId.

The ProcessUniqueId which is provided by https://github.com/Stebalien/snowflake is 128bit.
So I thought another snowflake implementation which provides 64bit id may get performance gain.

I got about 20% performance gain with the custom id_tree which uses https://github.com/BobAnkh/idgenerator.

https://github.com/dalance/id-tree/tree/use_idgenerator

throughput/parse        time:   [22.283 ms 22.315 ms 22.372 ms]
                        thrpt:  [679.05 KiB/s 680.77 KiB/s 681.75 KiB/s]
                 change:
                        time:   [-18.014% -17.837% -17.606%] (p = 0.00 < 0.05)
                        thrpt:  [+21.369% +21.710% +21.973%]
                        Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
  5 (5.00%) high mild
  3 (3.00%) high severe

[jsinger67]

@dalance,

again thank you for sharing your performance analyses.

id_tree is actually already for a long time on my list.

I even created an issue there for another problem that included a suggestion for a possible solution - and nothing happened.
So, I think that id_tree is dead.

The id type that id_tree uses is actually overdone for the use-case in parol because I don't need to prevent myself from referencing nodes via their ids in the wrong tree, because I have only one - the current parse tree.

So using snowflake's ProcessUniqueId is not necessary at all. A usize or an i64 (as you did in your fork of id_tree) will do the job completely.

Since I can't reference github repositories in crates that are not released on crates.io I actually can't use your fork in parol.

I have only two options

• Find a suitable substitution for id_treeout there
• Write my own tree implementation that fits exactly my needs and does only those things necessary

I have played a bit with a "SimpleTree" implementation that uses parts from @iwburns' id_tree long ago and I think it should be feasible.
The license this crate uses is MIT and I have to evaluate such a step, of course before doing this.

[jsinger67]

Currently I'm evaluating syntree created by @udoprog. Thanks a lot for this create!

It really looks promising and seems to be much better suitable for parol's use cases than id_tree has ever been.

I would like to keep the possibility of creating visualized trees as I did with id_tree_layout intact. This could mean that I have to provide an adequate implementation for syntree too.

Maybe, I'm doing this first to get a better feeling on how to work with syntree 😊

[udoprog]

I don't see an immediate reason why that shouldn't be possible.

A major difference I've done in 0.14.* which I just recently released though was the ability to have differently sized span indexes and pointer sizes (default being u32 and usize like before). This makes the API a bit harder to use if you're referencing identifiers which it seems like id_tree_layout will want to do.

Instead of this:

let id: syntree::Id = tree.first().ok_or("missing")?.id();

You'll have to do this (if you're using usize pointers):

use syntree::pointer::Width;

let id: <usize as Width>::Pointer = tree.first().ok_or("missing")?.id();

Of course the intent is that usize could be generic which would make it W::Pointer but that's up to you.

Good luck!

[jsinger67]

@udoprog
Thanks a lot for your explanation!
I hope I can start with this soon 😃

[jsinger67]

@udoprog
I have one question.
Is it possible to not include skipped tokens into the tree, i.e., to have a non-contiguous span information?
As far as I understand the API, it is not.

The API for token insertion (Builder::token) simply accepts a length information which is internally expanded to a span.

I think it is not necessary for parol's use cases, I only need a working tree implementation. The nodes I insert contain the information whether they are tokens or non-terminals.
So, there's no need for action here.

But if I wanted to use print_with_source this won't work out of the box.

I could imagine that having non-contiguous span information in the tree's leaves is a possible use case for other users.
Maybe a method where besides the length of the token a gap size (length of skipped text) can be provided.

As I said before there is no need from my side here. I just stumbled about that.

By the way, syntree_layout crate is on its way. 👍

[udoprog]

Hm, yeah. It's intended as a non-destructive representation of a syntax tree, which implies a contiguous set of spans from something being processed.

Additional information can be carried in the tree though, as is the case with the synthetic strings example, but you'd have to implement that in your own print_with_source implementation.

[jsinger67]

Ok, fine. I can live with that. 😉
It's no restriction for me.
Thanks a lot for your answer.

[jsinger67]

The first step has been taken:
syntree_layout
😎

[jsinger67]

@dalance
I have a working version on branch syntree.
I would appreciate if you could do some performance evaluations there.
Thanks in advance!

Edit:
In my scenario I achieved a performance gain factor of nearly eight (7.7) which is really amazing 💪
I parsed a 25 MiB JSON file in 1256 milliseconds.
The id_tree version took 9686 milliseconds.

[jsinger67]

In my scenario I counted 5.695.873 elements in this parse tree

[dalance]

I tried syntree branch.
I got 2.3x performance gain. It's awesome!!!

throughput/parse        time:   [11.867 ms 11.875 ms 11.885 ms]
                        thrpt:  [1.2612 MiB/s 1.2623 MiB/s 1.2632 MiB/s]
                 change:
                        time:   [-56.856% -56.801% -56.754%] (p = 0.00 < 0.05)
                        thrpt:  [+131.24% +131.49% +131.78%]
                        Performance has improved.
Found 20 outliers among 100 measurements (20.00%)
  9 (9.00%) low mild
  3 (3.00%) high mild
  8 (8.00%) high severe

[jsinger67]

Great, thanks!! 👍

[jsinger67]

As of version parol 0.19.0 and parol_runtime 0.15.0 we have switched to syntree crate as parse tree implemenation.
It was a huge amount of changes. Regarding this all went relatively smooth.
Thanks to all contributors!! 🥇

[udoprog]

Very cool!

Also, if you don't want to store spans in the tree (which might save you some memory since you're not using them), consider using Empty instead of u32.

[jsinger67]

Ok, good hint. I wasn't sure if I will ever need any span information. But as it turned out I won't.
So, I will probably use Empty in the next version.