Performance of `where` for small amounts of work is dominated by cloning the engine state

Related problem

Motivation

I have a script that parses the signature for all commands. One step is extracting all positional arguments for each command signature. That's a few houndred where calls on 2-6 items each. This is noticably not instant (takes about 300ms), which was quite surprising to me.

Cause

where seems to have a lot of overhead for starting up without any meaningful data.

> std bench { 1..1000 | each {|it| [] | where true } } --rounds 10 | get mean
2sec 84ms 554µs 362ns

That's pretty wild for doing nothing a thousand times.

Looking at a flamegraph, the time is dominated by cloning the vectors in EngineState (especially blocks and decls).

The same problem probably exists for every single command that clones EngineState (I've tested each, but this should apply to any other command that has to evaluate a block).

Describe the solution you'd like

One possible solution seems to be to (maybe partially) revert https://github.com/nushell/nushell/commit/60b58630588e7ec0085a8d6e4fffe56d98ba767a, reintroducing something that's cheaper to clone. I noticed in profiling that EngineState::blocks and EngineState::decls take almost all of the time to copy, so I applied a small diff that just makes those two things im::Vector.

--- a/crates/nu-protocol/Cargo.toml
+++ b/crates/nu-protocol/Cargo.toml
@@ -35,0 +36 @@ typetag = "0.2.5"
+im = "15.1.0"
diff --git a/crates/nu-protocol/src/engine/engine_state.rs b/crates/nu-protocol/src/engine/engine_state.rs
index e2cd1eba5..2ff6de4d8 100644
--- a/crates/nu-protocol/src/engine/engine_state.rs
+++ b/crates/nu-protocol/src/engine/engine_state.rs
@@ -106,2 +106,2 @@ pub struct EngineState {
-    decls: Vec<Box<dyn Command + 'static>>,
-    blocks: Vec<Block>,
+    decls: im::Vector<Box<dyn Command + 'static>>,
+    blocks: im::Vector<Block>,
@@ -154,2 +154,2 @@ impl EngineState {
-            decls: vec![],
-            blocks: vec![],
+            decls: im::Vector::new(),
+            blocks: im::Vector::new(),

A comparison shows that this is a lot faster:

> hyperfine './nu_with_im_vecs -c "1..1000 | each {|it| [] | where true }"' './nu_main -c "1..1000 | each {|it| [] | where true }"'

Benchmark 1: ./nu_with_im_vecs -c "1..1000 | each {|it| [] | where true }"
  Time (mean ± σ):      69.6 ms ±   1.6 ms    [User: 66.9 ms, System: 3.0 ms]
  Range (min … max):    67.1 ms …  72.9 ms    40 runs
 
Benchmark 2: ./nu_main -c "1..1000 | each {|it| [] | where true }"
  Time (mean ± σ):      1.764 s ±  0.064 s    [User: 1.757 s, System: 0.007 s]
  Range (min … max):    1.699 s …  1.924 s    10 runs
 
Summary
  './nu_with_im_vecs -c "1..1000 | each {|it| [] | where true }"' ran
   25.33 ± 1.10 times faster than './nu_main -c "1..1000 | each {|it| [] | where true }"'

It seems like those immutable datastructures were removed due to lack of benchmarks showing they make a difference. Here's one benchmark that suggests it can matter :)

Describe alternatives you've considered

Maybe there's a way to not clone the EngineState at all for these commands? I don't know if that's possible, though probably not as a stream could be evaluated later but should still have the old engine state. A naive attempt to avoid the clone leads to some borrow checker errors, since streams currently require 'static lifetime so they effectively can't be borrowed in iterators.

Otherwise, it would also be possible to the expensive bits of information outside EngineState, implementing some kind of copy-on-write (basically reimplement the immutable data structure 😏)

Additional context and details

No response

Start in crates/nu-protocol/src/engine/engine_state.rs and inspect how EngineState is cloned during block evaluation, especially its blocks and decls fields. Reproduce the issue with the provided std bench or hyperfine commands; done means the small-work where/each benchmark is substantially faster without breaking the required engine-state behavior.