Comment made by: adrianm
Appendo and membero are particularly slow.
(dotimes (link: i ie5) (run* (link: q) (== q true))) takes around ~4500ms, which is about 10x slower than the JVM.
After profiling, I've discovered the problem - pretty standard recursion optimizations are necessary, it's re-walking (by reunifying) lvars recursively as the code is executed. E.g.,
for appendo, (run 5 (link: q) (fresh (link: x y) (appendo x y q))) will expand into something like..
((_0) (_0 . _1) (_0 _1 . _2) ... ))
and it's slow because every new list is actually re-walking every previously unified lvar again.
I'll have more time to investigate this over the weekend, but I think it might be as simple as not generating unique lvars by default, since then the identical? for unification check should catch any attempted walk.