SICStus Prolog中maplist/2比递归实现慢10倍的原因探究

为什么maplist/2会用到元调用？ #

maplist/2是Prolog里的高阶通用谓词，核心是适配任意处理列表元素的谓词。正因为要支持这种通用性，它没法在编译阶段提前知道你要传入的具体谓词（比如你写的f/1），所以必须靠**元调用（meta-call）**机制，在运行时动态调用你指定的目标。

拿SICStus Prolog里maplist/2的核心逻辑举例（实际实现更复杂，但本质一致）：

maplist(_, []).
maplist(Pred, [H|T]) :-
    call(Pred, H),  % 这里就是元调用，动态执行传入的Pred谓词
    maplist(Pred, T).

这里的call(Pred, H)就是元调用——它得在运行时解析Pred参数对应的谓词定义，再执行；而你手写的递归fs/1是直接硬编码调用f/1，完全不需要这一步动态解析。

为什么元调用会造成10倍性能差？ #

元调用的额外开销主要来自这几个方面：

• 动态谓词解析：每次执行call/2时，Prolog都要查找Pred对应的谓词，而手写递归的fs([H|T]) :- f(H), fs(T)是编译为对f/1的直接调用，没有解析成本。
• 栈帧与上下文开销：元调用需要额外的栈帧来处理动态调用的上下文，手写递归的调用链则更紧凑，栈开销更小。
• 编译优化受限：Prolog编译器能对手写递归做很多优化（比如尾递归优化、内联调用），但对元调用的动态目标，大部分静态优化都没法生效——因为编译器提前不知道要调用的具体谓词，没法做针对性优化。

你的测试场景是1000元素列表重复100000次，单次调用的微小差距被放大了1亿次，最终就出现了10倍的耗时差。

额外提示 #

如果想兼顾代码简洁和接近手写递归的性能，SICStus Prolog支持部分编译期展开手段（比如expand_term/2或特定编译选项），也可以用宏生成类似手写递归的代码，但这会牺牲一点通用性。

内容的提问来源于stack exchange，提问作者repeat