Prolog：测试是否设置了位

Question

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

我的代码经常需要检查某些位是否已设置（或未设置），所以我做了一些微基准测试，看看是否有一些变体比其他变体快得多：

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

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

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

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

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

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

然后我偶然发现了以下 interesting part of the SWI-Prolog manual:

getbit(+IntExprV, +IntExprI)

Evaluates to the bit value (0 or 1) of the IntExprI-th bit of IntExprV. Both arguments must evaluate to non-negative integers. The result is equivalent to (IntExprV >> IntExprI)/, but more efficient because materialization of the shifted value is avoided.

Future versions will optimise (IntExprV >> IntExprI)/ to a call to getbit/2, providing both portability and performance.

所以我查看了 getbit/2:

bench_6(0, _, _) :- !.
bench_6(N, V, P) :- getbit(V,P) =:= 1, N0 is 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 |
--------+-----------------+-------------------|
bench_1 | 4547ms | 3704ms |   900ms |   780ms |
bench_2 | 4562ms | 3619ms |   970ms |   850ms |
bench_3 | 4541ms | 3603ms |   970ms |   870ms |
bench_4 | 4541ms | 3633ms |   940ms |   890ms |
bench_5 | 4502ms | 3632ms |   950ms |   840ms |
--------+-----------------+-------------------|
bench_6 | 1424ms |  797ms |    n.a. |    n.a. |

看来：

getbit/2 为 SWI-Prolog 提供了 500% 的加速。
command-line option -O 使 SWI-Prolog 有了显着的加速。

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

提前致谢！

Answer 1

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

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

PPS。我会添加一个使用测试代码序列的虚拟版本的基准测试，只是为了确保测试代码实际上确实比基准测试工具花费更多。（我做到了，并用对 dummy/3 的调用替换了位测试，它什么都不做，使其更快。所以基准测试似乎没问题。）

Prolog：测试是否设置了位

Prolog: testing if bit is set

prolog

benchmarking

microbenchmark

sicstus-prolog