This is a pretty hot operation, but it is linear. So, for example, when we are
- collecting lang items
- and looking at attributes of items
- and looking at sources of items
in a big file, we get O(N^2) behavior.
Originally I wanted to fix this with using binary search for finding the relevant child. This, however, requires changes to rowan -- specifically, we'd need to remember start offsets of children in green nodes to make binary search work.
This is not a bad solution, however, I'd like to test something even better in theory -- using paths and not text ranges to represnt SyntaxPtr. I think if we use var-length encoding for paths, this might fly without too much extra allocations.
This is a pretty hot operation, but it is linear. So, for example, when we are
in a big file, we get O(N^2) behavior.
Originally I wanted to fix this with using binary search for finding the relevant child. This, however, requires changes to rowan -- specifically, we'd need to remember start offsets of children in green nodes to make binary search work.
This is not a bad solution, however, I'd like to test something even better in theory -- using paths and not text ranges to represnt SyntaxPtr. I think if we use var-length encoding for paths, this might fly without too much extra allocations.