refactor(tvix/eval): add name-based index over compiler's locals r/5454

Instead of finding locals by doing 2x O(n) walks over the compiler's
locals list, use a secondary name-based index for resolving locals by
name.

Previously, almost 60% (!!) of eval time on some expressions over
nixpkgs was spent in `Local::has_name`. This function doesn't even
exist anymore now, and eval speed about doubles as a result.

Note that this doesn't exactly make the locals code easier to read,
but I'm also not sure what we can simplify in there in general.

This fixes b/227.

Change-Id: I29ce5eb9452b02d3b358c673e1f5cf8082e2fef9
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7560
Reviewed-by: grfn <grfn@gws.fyi>
Tested-by: BuildkiteCI

1 files changed, 7 insertions, 6 deletions

diff --git a/tvix/eval/src/compiler/mod.rs b/tvix/eval/src/compiler/mod.rs
index 87383c0ca967..b8d8fb11a247 100644
--- a/tvix/eval/src/compiler/mod.rs
+++ b/tvix/eval/src/compiler/mod.rs
@@ -1120,16 +1120,17 @@ impl Compiler<'_> {
             self.scope_mut().poison(global_ident, depth);
         }
 
-        for other in self.scope().locals.iter().rev() {
-            if other.has_name(&name) && other.depth == depth {
-                self.emit_error(node, ErrorKind::VariableAlreadyDefined(other.span));
+        let span = self.span_for(node);
+        let (idx, shadowed) = self.scope_mut().declare_local(name, span);
 
-                break;
+        if let Some(shadow_idx) = shadowed {
+            let other = &self.scope()[shadow_idx];
+            if other.depth == depth {
+                self.emit_error(node, ErrorKind::VariableAlreadyDefined(other.span));
             }
         }
 
-        let span = self.span_for(node);
-        self.scope_mut().declare_local(name, span)
+        idx
     }
 
     /// Determine whether the current lambda context has any ancestors