cdr-atom in minimal metta is very slow

[ngeiswei]

What is your problem?

In minimal MeTTa cdr-atom is very slow.

How to reproduce your problem?

1. Compile MeTTa with "minimal" feature.

2. Run the following program

;; Define arity
(: arity (-> $a Number))
(= (arity $tuple) (if (== $tuple ())
                      0
                      (let* (($head (car-atom $tuple))
                             ($tail (cdr-atom $tuple)))
                        (+ 1 (arity $tail)))))

;; Generate tuple of arithmetic series
(: gen-tuple (-> Number Number Number $a))
(= (gen-tuple $i $s $n) (if (== $n 0)
                            ()
                            (let $r (gen-tuple (+ $i $s) $s (- $n 1))
                              (cons-atom $i $r))))

;; Test arity
!(arity (gen-tuple 0 1 10))

What would you normally expect?

[10]

instantly.

What do you get instead?

[10]

in 38s on my Ryzen 7 2700X.

What else do you have to say?

I suspect the problem comes from cdr-atom, so I wrote an equivalent program that does not rely on cdr-atom, see below

;; Define List
(: List (-> $a Type))
(: Nil (List $a))
(: Cons (-> $a (List $a) (List $a)))

;; Define length
(: length (-> (List $a) Number))
(= (length Nil) 0)
(= (length (Cons $head $tail)) (+ 1 (length $tail)))

;; Generate list of arithmetic series
(: gen-list (-> Number Number Number (List Number)))
(= (gen-list $i $s $n) (if (== $n 0)
                           Nil
                           (Cons $i (gen-list (+ $i $s) $s (- $n 1)))))

;; Test length
!(length (gen-list 0 1 10))

it takes 4s.

Also, I compared gen-list and gen-tuple only and they are about as fast, consolidating the idea that cdr-atom is the culprit.

In non-minimal MeTTa it takes 1s for tuple and 0.5s for list, which is obviously much better, though still slow.

[vsbogd]

@ngeiswei , one strange thing I see is that Python in this case 6x times slower than Rust REPL. For instance running example through the Rust Repl gives:

time cargo run --release --features minimal,no_python /tmp/638.metta
[10]

real    0m8.188s
user    0m8.145s
sys 0m0.040s

It is the first issue I would like to investigate.

[vsbogd]

I would recommend using Rust REPL if it is possible in your case.