cstree icon indicating copy to clipboard operation
cstree copied to clipboard

Feature-gate threadsafe syntax trees

Open domenicquirl opened this issue 5 years ago • 2 comments

Make Send and Sync impls for SyntaxXY a feature and see which parts of the implementation can be simplified for the single threaded case. From the top of my head, I would start with

  • the ref count,
  • NodeData's children, together with SyntaxNode::{read, write},
  • NodeData's data.

#2 should happen first before we start working on this.

domenicquirl avatar Jan 13 '21 10:01 domenicquirl

Would you be open to using archery for this? We can add it as the last generic type and default to ArcTK, and have it not be a breaking change.

https://lib.rs/rpds does this and it's neat

RGBCube avatar Jul 11 '25 21:07 RGBCube

So, we can definitely use something like this if it proves to be a useful abstraction, I don't have a strong opinion on whether this is better or worse than switching between Rc and Arc based on a feature flag (I believe rustc does something like this to support work on parallelizing the compiler, basically you do type SomeRc = /* depends on feature flag */. I think most users need one or the other, not both - but I could be wrong there), other than that we already have quite a lot of generics on everything and so if your suggested route involves adding more of them I'd want to provide type aliases to reduce the amount of having to specify which version you want.

With that said, I don't think it's quite as easy to support this as dropping in an abstraction over the refcounting pointer type:

  • They support triomphe's Arc, which is good, but we also use ThinArc to store the children in green nodes, which according to the README they don't currently support (this is minor since we mostly want to support this for syntax nodes, not green nodes).
  • We don't actually use any RC type for the syntax nodes currently, as they manage their own refcount as an AtomicU32 because SyntaxNode is already a handle / pointer type to the underlying NodeData. Using Rc or Arc instead would make every SyntaxNode bigger, which would be a big perf hit.
  • Probably the biggest win we could get from this idea would be if we can get rid of the locks currently required to access a node's children (this is the child_locks: Vec<RwLock<()>> in NodeData, and in the same way but less impactful the RwLock for data). Since these are locks, not smart pointers, archery won't help with that.

IMO tree building and traversal performance (and maybe memory usage) are the main motivation for this change, since other than that removing Send / Sync makes our types strictly less useful than they are now. A partial solution for only the pointer types likely won't buy us much here, especially if it increases the API surface (by adding yet another generic).

domenicquirl avatar Jul 12 '25 09:07 domenicquirl