Recursive method with access to large data object, How to?

Developers Getting Started
1

I would like to implement a recursive function with Motoko. This method needs to access a very large data object. What is the best way to implement it?

A first option is a class with a class method to implement the recursive functionality and a class attribute to hold the large data object used in each iteration of the recursive method.
A second option is just a canister function with one argument where we pass the large data object every time

I suspect that the second option could be problematic (maybe filling the heap after few iterations) when the number of iterations/recursions is large and/or the data object is also very large.

Could you advice me on the pros and cons of every option or whether there are better ways?

@claudio @matthewhammer

1 Like
2

Is the large object always the same? In that case your recursive function can just reference the object from its code without passing it as an additional argument.

In Motoko, large objects a heap-allocated and passed by reference (just passing a small pointer to the object, not copying the entire object) so the size of the object should not really matter.

Maybe it would help if you should show the code you are trying to write.

2 Likes
3

Just to illustrate, consider this code, that sum the elements of a large array o:


import Array "mo:base/Array";

actor {

  let o = Array.tabulate<Nat>(1000_000, func i { i });

  func sum(i : Nat, acc : Nat) : Nat {
    if (i < o.size()) {
      sum(i + 1, acc + o[i]);
    } else acc;
  };

  func tot(a : [Nat], i : Nat, acc : Nat) : Nat {
    if (i < a.size()) {
      tot(a, i + 1, acc + a[i]);
    } else acc;
  };

  class Summer(a : [Nat]) {
    public func sum(i : Nat, acc : Nat) : Nat {
      if (i < a.size()) {
        sum(i + 1, acc + a[i]);
      } else acc;
    };
  };

  public func doSum() : async Nat {
    return sum(0, 0);
  };

  public func doTot() : async Nat {
    return tot(o, 0, 0);
  };

  public func doSummer() : async Nat {
    return Summer(o).sum(0, 0);
  };

};

Function ‘sum’ just references ‘o’ directly and won’t create a copy.
The call ‘tot(o, 0, 0)’ just passed a 4-byte reference to o for the parameter a, even for the recursive calls.
The call ‘Summer(o).sum(0,0)’ does the same, and the method .sum(0,0) just references ‘o’ via the parameter ‘a’ - the only things that get copied is the short, 4-byte address of ‘o’, not the large contents of ‘o’.

Hope that helps.

1 Like