3

我使用任意精度的整数来表示密集的位向量——大小从十几个到几千不等。

我的代码经常需要检查是否设置了某些位（或未设置），因此我做了一些微基准测试，以查看某些变化是否明显快于其他变化：

bench_1(0, _, _) :- !.
bench_1(N, V, P) :- V /\ (1 << P) =\= 0, N0 是 N-1, bench_1(N0, V, P)。

bench_2(0, _, _) :- !.
bench_2(N, V, P) :- (V >> P) /\ 1 =:= 1, N0 是 N-1, bench_2(N0, V, P)。

bench_3(0, _, _) :- !.
bench_3(N, V, P) :- (V >> P) /\ 1 =\= 0, N0 是 N-1, bench_3(N0, V, P)。

bench_4(0, _, _) :- !.
bench_4(N, V, P) :- (V >> P) /\ 1 > 0, N0 是 N-1, bench_4(N0, V, P)。

bench_5(0, _, _) :- !.
bench_5(N, V, P) :- 1 是 (V >> P) /\ 1，N0 是 N-1，bench_5(N0, V, P)。

对于 SWI 和 SICStus，上述变体都（几乎）同样快。

然后我偶然发现了 SWI-Prolog 手册中以下有趣的部分：

getbit(+IntExprV, +IntExprI)

计算为 的第 - 位的位值（0或1）。两个参数都必须计算为非负整数。结果等效于，但更有效，因为避免了移位值的具体化。IntExprIIntExprV(IntExprV >> IntExprI)/\1

未来的版本将优化(IntExprV >> IntExprI)/\1对 的调用getbit/2，同时提供可移植性和性能。

所以我检查了getbit/2：

bench_6(0, _, _) :- !.
bench_6(N, V, P) :- getbit(V,P) =:= 1, N0 是 N-1, bench_6(N0, V, P)。

我使用以下代码进行微基准测试：

call_indi_delta(G, What, Delta) :-
   statistics(What, [V0|_]),
   call(G),
   statistics(What, [V1|_]),
   Delta is V1 - V0.

run(Ind, Reps, Expr, Pos) :-
   Position is Pos,
   Value    is Expr,
   member(P_3, [bench_1,bench_2,bench_3,bench_4,bench_5,bench_6]),
   G =.. [P_3,Reps,Value,Position],
   call_indi_delta(G, Ind, T_ms), 
   write(P_3:Reps=T_ms), nl,
   false.

随着run(runtime, 10000000, 1<<1000-1, 200)我观察这些运行时：

        | SWI | SWI-O | SICStus | SICStus |
        | 7.3.23 | 7.3.23 | 4.3.2 | 4.3.3 |
--------+-----------------+--------------------|
长凳_1 | 4547毫秒| 3704 毫秒| 900 毫秒 |   780ms |
长凳_2 | 4562ms | 3619 毫秒 | 970 毫秒 | 850 毫秒 |
长凳_3 | 4541ms | 3603ms | 970 毫秒 | 870ms |
长凳_4 | 4541ms | 3633ms | 940 毫秒 | 890 毫秒 |
长凳_5 | 4502ms | 3632ms | 950 毫秒 | 840 毫秒 |
--------+-----------------+--------------------|
长凳_6 | 1424 毫秒 |  797ms | 呐 |    呐|

看起来：

  • getbit/2给 SWI-Prolog 500% 的加速。

  • 命令行选项-O为 SWI-Prolog 带来了显着的加速。

是否有更好的公式（arith. fun.等）来获得与 SICStus 类似的加速？

先感谢您！

4

1 回答 1

4

不，我认为没有比您尝试过的更快的配方。特别是，getbit/2SICStus 中没有任何东西（编译算术时甚至没有在内部使用）。

PS。walltime一般来说，我会使用来进行基准测试。当前的操作系统不提供非常可靠的runtime.

聚苯乙烯。我将添加一个使用测试代码序列的虚拟版本的基准测试，以确保测试代码实际上确实比基准测试工具花费更多。（我做到了，并且用什么都不做的调用替换了位测试dummy/3，使它更快。所以基准测试似乎还可以。）

于 2016-07-07T09:03:26.070 回答