Description
Is your feature request related to a problem? Please describe.
For docstring support we need to access the parent of an Expr. (workarounds not feasible - @hsjobeki and I have tried)
We expect the memory overhead of an extra Expr field to be on the order of 5%, so this loss would be prevented. (measurement tbd)
Furthermore memory allocation overhead can be bypassed (both cpu, sync and memory)
Describe the solution you'd like
By allocating Exprs together in an area of memory, we can instead determine the root virtually for free, and find the parent by doing an O(log n) binary search.
This also speeds up parsing, because we can use an allocator that performs no synchronization.
We can also take advantage of the fact that individual Exprs aren't freed, so we don't need to track object sizes, reducing memory overhead.
I couldn't find an off the shelf allocator. Possible data model:
constexpr size_t region_size;
pool<Allocator> allocators;
struct Region {
void * start;
void * end;
}
struct Allocator {
void * currentRegionStart;
void * cursor;
}
map<Region, Expr *> roots;
When starting to parse, request an allocator and use it for all Expr allocations in the parser.
These are single threaded, so Allocator access will be efficient.
When the next cursor position doesn't fit in the allocator's region anymore, or when parsing is done, add the used region to the roots map.
To find the root of an Expr, use its pointer to find it in the roots map. To find a parent, also perform a binary search using pos info.
Describe alternatives you've considered
Go through pos and the parse cache. This would not support
- scopedImport
- comments in alternate sources such as the repl
This has its own complexity and does not speed up Expr allocation, and does not reduce allocator memory overhead to a bare minimum.
Additional context
Priorities
Add 👍 to issues you find important.