Comment by thramp
1 month ago
We (the rust-analyzer team) have been aware of the slowness in Rowan for a while, but other things always took priority. Beyond allocation, Rowan is structured internally as a doubly-linked list to support mutating trees, but: 1. Mutation isn’t really worth it; the API isn’t user-friendly. 2. In most cases, it’s straight up faster to create a new parse tree and replace the existing one. Cache effects of a linked list vs. an arena!
In fairness, I don’t think we predicted just how large L1/L2 caches would get over the coming years.
Is a rewrite of Rowan on the horizon?
One of the rust-analyzer co-maintainers (Chayim Friedman) already rewrote it, but we can’t integrate it yet, as about 40 assists (the little lightbulbs?) still rely on mutation. If you want something Rowan-like, I think syntree and Biome’s rowan fork are good options to look into.
How about cstree? https://crates.io/crates/cstree Recently I found that traversal in rowan tree can cost much time. No sure if there's a cheaper way to achieve that. Or, integrate rowan with bump allocator (bumpalo or oxc_allocator)?