为什么当第三个参数是未绑定变量时 arg/3 更快？

Question

谓词

ksort/3

和

fksort/3

对

Key-Value

对列表进行排序，其中

Key

是介于

1

和小整数

MaxKey

之间的值。

% first version

ksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    scatter(List, Buckets),
    gather(Buckets, Sorted).

scatter([], _).
scatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Head-[Key-Val|Tail]),
    setarg(Key, Buckets, Head-Tail),
    scatter(Pairs, Buckets).

% second version

fksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    fscatter(List, Buckets),
    gather(Buckets, Sorted).

fscatter([], _).
fscatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Bucket),        % <= third argument is an unbound variable
    setarg(Key, Buckets, Head-Tail),
    Bucket = Head-[Key-Val|Tail],
    fscatter(Pairs, Buckets).

% predicates used in both versions

create(MaxKey, Buckets) :-
    findall(L-L, between(1, MaxKey, _), Dlists),
    Buckets =.. [buckets|Dlists].

gather(Buckets, Sorted) :-
    Buckets =.. [buckets|Dlists],
    join(Dlists, Sorted).

join([], []).
join([Head-Tail|Dlists], Head) :-
    join(Dlists, Tail).

comparison :-
    K = 100,
    format('size keysort ksort fksort\n'),
    forall( between(15, 22, I),
            (   garbage_collect,
                N is 2^I,
                randpairs(N, K, L),
                timeit(10, keysort,   L, S1, T1),
                timeit(10, ksort(K),  L, S2, T2),
                timeit(10, fksort(K), L, S3, T3),
                S1 = S2,
                S2 = S3,
                format('2^~w    ~2f  ~2f   ~2f\n', [I, T1, T2, T3]) ) ).

randpairs(N, K, Pairs) :-
    findall(Key-Val,
            ( between(1, N, _),
              random_between(1, K, Key),
              random(Val) ),
            Pairs).

timeit(R, P, L, S, T) :-
    garbage_collect,
    Start is cputime,
    forall(between(1, R, _), call(P, L, S)),
    T is (cputime - Start)/R.

在此特定场景中，两个谓词的运行速度都比 ISO 内置谓词更快

keysort/2

。

?- comparison.
size keysort ksort fksort
2^15    0.01  0.01   0.00
2^16    0.02  0.02   0.01
2^17    0.05  0.03   0.02
2^18    0.12  0.06   0.03
2^19    0.30  0.12   0.06
2^20    0.69  0.23   0.13
2^21    1.56  0.42   0.26
2^22    3.56  0.93   0.52
true.

ksort/3

和

fksort/3

之间的唯一区别是它们如何调用谓词

arg/3

。我的问题是：为什么

fksort/3

比

ksort/3

快？

Answer 1

在

scatter/2

谓词中，

arg/3

调用中的第三个参数

Head-[Key-Val|Tail]

需要遍历复合项来访问四个子项，这比

 调用中的变量参数的计算成本更高fscatter/3

谓词。

fscatter/3

将参数统一从

arg/3

移动到显式统一

Bucket = Head-[Key-Val|Tail]

，这似乎具有性能优势。