Optimize DebugNode flatten_to

[mattsse]

Component

Forge

Describe the feature you would like

ref #7382

This currently does a bunch of expensive clones:

foundry/crates/debugger/src/tui/builder.rs

Lines 40 to 45 in b2f9346

	/// Extends the debug arena.
	#[inline]
	pub fn debug_arena(mut self, arena: &DebugArena) -> Self {
	arena.flatten_to(0, &mut self.debug_arena);
	self
	}

foundry/crates/evm/core/src/debug.rs

Lines 74 to 87 in b2f9346

	/// Recursively traverses the tree of debug nodes and flattens it into the given list.
	///
	/// See [`flatten`](Self::flatten) for more information.
	pub fn flatten_to(&self, entry: usize, out: &mut Vec<DebugNodeFlat>) {
	let node = &self.arena[entry];
	if !node.steps.is_empty() {
	out.push(node.flat());
	}
	for child in &node.children {
	self.flatten_to(*child, out);
	}
	}

since we're consuming the type, we can get rid of the clones by rewriting this with a stack approach

Additional context

[qiweiii]

May I know how do you generate the image under Additional context

[PanGan21]

Hi @mattsse .
I am interested to pick this up. Would a VecDeque be a good option for our use case?

[mattsse]

Hi @mattsse . I am interested to pick this up. Would a VecDeque be a good option for our use case?

yeah, I think it should be similar to

https://github.com/paradigmxyz/evm-inspectors/blob/d7317c7fbf38d5e5df2393beee0414c987ea440a/src/tracing/builder/geth.rs#L46

[mattsse]

May I know how do you generate the image under Additional context

this is https://github.com/mstange/samply

[PanGan21]

Hi @mattsse . I am interested to pick this up. Would a VecDeque be a good option for our use case?

this is https://github.com/mstange/samply

I will give it a try then!

[MuhtasimTanmoy]

Would like to give it a try as well.

Does this change looks ok?

pub fn flatten_to(&self, entry: usize, out: &mut Vec<DebugNodeFlat>) {

      let mut stack = VecDeque::new();
      stack.push_back(entry);

      while let Some(entry) = stack.pop_back() {
          let node = &self.arena[entry];

          if !node.steps.is_empty() {
              out.push(node.flat());
          }

          for child in node.children.iter().rev() {
              stack.push_back(*child);
          }
      }
 }

Also, what needs to be done to test it?

[PanGan21]

Sure, no problem. Let me know if I can still help with something

[MuhtasimTanmoy]

@mattsse What command should generate the profiler image from additional context? samply record ..... ?
How to measure improvement?

As suggested by @DaniPopes how should we work on this function and try to get rid this clone?

/// Flattens this node into a [`DebugNodeFlat`].
pub fn flat(&self) -> DebugNodeFlat {
    DebugNodeFlat { address: self.address, kind: self.kind, steps: self.steps.clone() }
}

[lakshya-sky]

IMO we can't get rid of clones since we are passing DebugArena by ref, but somebody can correct me on this.

[DaniPopes]

You're right, we have to pass by reference due to the nested data structure. I don't think this is worth it.