Question regarding performance hacks

[DaddyWesker]

There was an inner conversation regarding my suggestion on how to improve performance of some functions. This issue is the result of this conversation. I'm wrapping it here since it could be useful for those who starts to learn Metta.

So, let's start with a code. Here is a two possible ways to implement factorial:

(= (fac $x) (if (== $x 0 ) 1 ( * (fac (- $x 1)) $x  )))  

(= (fac2 0)
    1)
(= (fac2 $x)
    (if (> $x 0)
        (* (fac2 (- $x 1)) $x)
        (empty)))

And, similarly, two ways to implement Fibonacci number generator:

(= (fib $n)
    (if (== $n 0)
        0
        (if (== $n 1)
            1
            (+ (fib (- $n 1)) (fib (- $n 2))))))

(= (fib2 0)
    0)
(= (fib2 1)
    1)
(= (fib2 $x)
    (if (> $x 1)
        (+ (fib2 (- $x 1)) (fib2 (- $x 2)))
        (empty)))

In each example, second implementation is faster than first one. For example, (fib 100) vs (fib2 100) is 48.808s vs 19.594s . And bigger the input number - bigger the difference in performance. Difference for factorial is not so impressive. At least for 100 as input. 10.303s vs 9.703s .

Anyway, @Necr0x0Der said that these hacks is not appropriate since they can be applied only to current state of metta interpreter and further interpreter optimizations could make these hacks obsolete. So better way to implement fib will be one of those:

; Recursive
(= (fib $n)
    (if (< $n 2)
        $n
        (+ (fib (- $n 1)) (fib (- $n 2)))))

!(assertEqual
    (fib 7)
    13)

; Iterative
(= (ifib $n)
    (fib-iter 1 0 $n))

(= (fib-iter $a $b $count)
    (if (== $count 0)
        $b
        (fib-iter (+ $a $b) $a (- $count 1))))

!(assertEqual
    (ifib 7)
    13)

Iterative variant should be quicker, but in current metta interpreter's state it is quite opposite due to interpreter cashes all calls during evaluation (@Necr0x0Der will probably explain this better). In minimal-metta this behavior could be different.

[vsbogd]

Iterative variant should be quicker, but in current metta interpreter's state it is quite opposite due to interpreter cashes all calls during evaluation

To me the second variant is quicker. In both minimal MeTTa and Rust interpreter.

[Necr0x0Der]

Apparently, nested ifs may add some overhead. However, the code in these examples should be pretty straightforwardly compilable, which we may have in the near future. At the same time, the code like this

(= (fac2 0) 1)
(= (fac2 $x)
    (if (> $x 0)
        (* (fac2 (- $x 1)) $x)
        (empty)))

uses non-determinism for a deterministic function, which is definitely not an idiomatic way to implement it, and involves (empty), which requires additional explanations. Even if it is faster, it's not a good idea for a tutorial to show such code. There are other ways to implement fact of fib, and to avoid nested ifs for mutually exclusive branches (instead of using non-determinism which is for non-exclusive branches), e.g. with the use of case:

(= (fac3 $x)
   (case $x
    ((0 1)
     ($_ (* (fac3 (- $x 1)) $x)))))

Whether to use case or not may depend on how the tutorial is organized. Maybe, transforming this code

(= (fib $n)
    (if (== $n 0)
        0
        (if (== $n 1)
            1
            (+ (fib (- $n 1)) (fib (- $n 2))))))

to this

(= (fib3 $n)
   (case $n
      ((0 0)
       (1 1)
       ($_ (+ (fib3 (- $n 1)) (fib3 (- $n 2)))))))

is exactly the place where case can be introduced. Although case differs from nested if in MeTTa in a deeper way than in other languages, so it should also be described carefully

[DaddyWesker]

Iterative variant should be quicker, but in current metta interpreter's state it is quite opposite due to interpreter cashes all calls during evaluation

To me the second variant is quicker. In both minimal MeTTa and Rust interpreter.

It is weird, but you're right. It was quite opposite on the previous metta versions for me. I haven't tested time difference between these two variants after updating metta.

[DaddyWesker]

@Necr0x0Der Thank you for explanations. One question regarding case - what $_ symbol means? In case of this function:

(= (fib3 $n)
   (case $n
      ((0 0)
       (1 1)
       ($_ (+ (fib3 (- $n 1)) (fib3 (- $n 2)))))))

as I understand for (== $n 0) result will be 0, for (== $n 1) result will be 1, for $ (everything else?) result will be sum of recursions. Is this symbol `$applicable only in case ofcase`? Or it has some other use cases?

[vsbogd]

what $_ symbol means?

In MeTTa it is just a normal variable. Name _ is chosen to be familiar to users of other languages where _ means match anything. Keep in mind that if you want to use couple of such variables in same context you need to name it differently: $_ and $__ or $_1.

[DaddyWesker]

what $_ symbol means?

In MeTTa it is just a normal variable. Name _ is chosen to be familiar to users of other languages where _ means match anything. Keep in mind that if you want to use couple of such variables in same context you need to name it differently: $_ and $__ or $_1.

Thanks, Vitaly.