perf(semantic): indextree

[Boshen]

We are currently constructing a parent pointing tree using the indextree crate, but this is probably an overkill both cpu and memory wise.

The only functionality we need are:

• find a node's parent node
• iterate through a node's ancestor nodes

For performance, I wonder if using bumpalo will be better than a Vec by using the same allocator for the AST.

[Boshen]

cc @YoniFeng, since you are really good at this kind of low level stuff, and I'm learning a lot from you.

[Boshen]

Relevant CPU profile:

[YoniFeng]

I need to get a setup for profiling native applications(on Windows..), been lazy so far.
Most of my profiling analysis experience is from a previous job where the profiling was already instrumented on production machines, and the data was served on a silver platter (and it was mostly non-native).

From reading indextree's doc and skimming the code, I'm skeptical that hand-rolling this tree on bumpallo will see significant gains.
However, I did notice that the append we use in create_ast_node isn't specialized for a new node.

pub fn checked_append<T>(
        self,
        new_child: NodeId,
        arena: &mut Arena<T>,
    ) -> Result<(), NodeError> {
        if new_child == self {
            return Err(NodeError::AppendSelf);
        }
        if arena[self].is_removed() || arena[new_child].is_removed() {
            return Err(NodeError::Removed);
        }
        if self.ancestors(arena).any(|ancestor| new_child == ancestor) {
            return Err(NodeError::AppendAncestor);
        }
        new_child.detach(arena);
        insert_with_neighbors(arena, new_child, Some(self), arena[self].last_child, None)
            .expect("Should never fail: `new_child` is not `self` and they are not removed");

        Ok(())
    }

In our case, everything above insert_with_neighbors() is redundant work for us.
Even within insert_with_neighbors(), there's a detach_from_siblings() call which is redundant when we know the inserted node is new (and even beyond the "new node" use case - it's redundant because it was just performed in detach).

In your profiling screenshot detach_from_siblings is 50ms which would get shaved off.
Probably worth checking out some sort of an append_new_node fast path, where it's the user's responsibility to uphold assumptions.

TL;DR I think making trying to make changes in indextree makes more sense, at least for a first approach.
You can assign this issue to me.

[Boshen]

Done in #122.