Proof of concept: trailing objects for GreenNode

[CAD97]

This is "theoretically unsound" as of current as it requires creating a fat pointer from a thin pointer gotten from alloc. However, it should have enough paranoia checking to kill performance of GreenNode::new and ensure that it doesn't cause UB due to implementation details changing.

The "llvm::trailing_objects trick" requires that the "trailing_objects carrier" always be behind a pointer (as it is ?Sized). For simplicity of the PoC, I just put an Arc inside GreenNode, so it's essentially C++ ptr::shared<GreenNodeInner>. Because of this we aren't even saving allocations, just moving the syntax kind and text length of the GreenNode inside the Arc.

This doesn't even give us space savings, as GreenElement remains 5 usize large, as GreenToken is still 4 usize large and there is no way to niche GreenNode and GreenToken together. This does reduce the size of GreenNode from 3 usize to 2 usize, but that benefit just can't proliferate to GreenElement.

Because of this I recommend removing the llvm::trailing_objects mention or otherwise clarifying how it might benefit the tree.

[CAD97]

Unsound fat pointer creation has been eliminated courtesy of @myrrlyn. We still have a laundry list of assumptions for the manual allocation, however.

[CAD97]

Having walked the implementation a bit more, I understand where the benefit could come in: what was previously called TreeArc and is now just SyntaxNode. I'm playing with properly making GreenNode ?Sized now, just to see where that goes.

[matklad]

Don’t have time to review right now, but yeah, this might not be as beneficial as the swift’s case, because we are storing tokens inline.

On Saturday, 26 October 2019, Christopher Durham notifications@github.com wrote:

Having walked the implementation a bit more, I understand where the benefit could come in: what was previously called TreeArc and is now just SyntaxNode. I'm playing with properly making GreenNode ?Sized now, just to see where that goes.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/rust-analyzer/rowan/pull/31?email_source=notifications&email_token=AANB3M7X6J3VNQ3IBKC2VLLQQSOORA5CNFSM4JFJMIX2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOECKPXUY#issuecomment-546634707, or unsubscribe https://github.com/notifications/unsubscribe-auth/AANB3M7YMJVNMKHGPXCOME3QQSOORANCNFSM4JFJMIXQ .

[CAD97]

Closing in favor of #32.