>>250
Prologは最も速いコンパイラ言語の100倍以上遅いでしょう。
その理由の過半がユニフィケーションと変数の繰り返し出現検査に
あると思います。指摘されたように配列がないこともある場合には
原因となります。それに比べればトレイルスタック等の追加的処理は
大きなコストになっていないはずです。

明らかに遅くて使えないのはビットマップの処理ですね。繰り返し
数百万のビットに対して演算する場合です。RPGも無理でしょう。

Prologはオンメモリデータベースですから、そこそこ速いのですが、
Prologが再起するためには、あなたが指摘したとおり、インデックス
などによる最適化によって、定義アトムを検索する能力を高める
必要があると思います。現在のレベルでは、数百万節の検索を
掛ける気になりません。