How to fast get reference to an element among the tree? when reference and enum involved

tiye · May 31, 2022, 8:00am

I have a tree, and 2 functions, one using recursive functions:

calcit-lang/ternary-tree.rs/blob/0.0.10/src/tree.rs#L223-L252


      
          pub fn ref_get(&self, idx: usize) -> &T {
            // println!("get: {} {}", self.format_inline(), idx);
            // if idx >= self.len() {
            //   println!("get from out of bound: {} {}", idx, self.len());
            //   return None;
            // }
            match self {
              Branch3 { left, middle, right, .. } => {
                let base = left.len();
                if idx < base {
                  return left.ref_get(idx);
                }
                let idx_in_middle = idx - base;
                if idx_in_middle < middle.len() {
                  middle.ref_get(idx_in_middle)
                } else {
                  right.ref_get(idx_in_middle - middle.len())
                }
              }
              Branch2 { left, middle, .. } => {

This file has been truncated. show original

one maintaining a Cell and using a loop:

github.com

calcit-lang/ternary-tree.rs/blob/0.0.10/src/tree.rs#L256-L289


      
          pub fn loop_get(&'a self, original_idx: usize) -> &'a T {
            let tree_parent = Cell::new(self);
            let mut idx = original_idx;
            loop {
              match tree_parent.get() {
                Leaf(value) => {
                  return &*value;
                }
                Branch2 { left, middle, .. } => {
                  if idx < left.len() {
                    tree_parent.set(left);
                  } else {
                    tree_parent.set(middle);
                    idx -= left.len();
                  }
                }
                Branch3 { left, middle, right, .. } => {
                  if idx < left.len() {
                    tree_parent.set(left);
                    continue;

This file has been truncated. show original

I made a simple bench function, the as the result, it's faster to use loop,

loop_get                time:   [20.444 us 20.667 us 20.886 us]
                        change: [-3.2910% -1.7348% -0.2509%] (p = 0.04 < 0.05)
                        Change within noise threshold.
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

ref_get                 time:   [30.671 us 30.842 us 31.007 us]
                        change: [-10.065% -9.5309% -8.9736%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

however, the story does not end here. I use this library in my project, which uses a large enum(see below), it's significantly slower(results from running script on Mac and Ubuntu):

github.com

calcit-lang/calcit/blob/0.5.44/src/primes.rs#L120


      
          /// and it is still different from quoted data which was intentionally turned in to data.
          Thunk(Arc<Calcit>, Option<Arc<Calcit>>), // code, value
          /// atom, holding a path to its state, data inside remains during hot code swapping
          Ref(Arc<str>),
          /// more tagged union type, more like an internal structure
          Tuple(Arc<Calcit>, Arc<Calcit>),
          /// binary data, to be used by FFIs
          Buffer(Vec<u8>),
          /// not for data, but for recursion
          Recur(CalcitItems),
          List(CalcitItems),
          Set(rpds::HashTrieSetSync<Calcit>),
          Map(rpds::HashTrieMapSync<Calcit, Calcit>),
          /// with only static and limited keys, for performance and checking
          /// size of keys are values should be kept consistent
          Record(EdnKwd, Arc<Vec<EdnKwd>>, Arc<Vec<Calcit>>),
          /// native functions that providing feature from Rust
          Proc(Arc<str>),
          Macro {
            name: Arc<str>,
            /// where it was defined

I don't have full benchmark for that, only some perf and flamegraph(sorry I don't have accurate and stable results except for the perf on Ubuntu... I can't analyze ASM by myself as well).

Is there any reason or tricks why the function fast using usize turned slow using on references large enum?

system · August 29, 2022, 8:00am

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.

Topic		Replies	Views
Returning reference to tree node value help	4	189	February 29, 2024
Return a reference from the function	7	988	January 20, 2022
Lifetime of RefCell borrows help	5	412	February 6, 2024
<Rc<RefCell<TreeNode>>> on Leetcode	11	1895	July 4, 2021
Borrow checker woes help	4	520	January 12, 2023

How to fast get reference to an element among the tree? when reference and enum involved

Related Topics