Пролог: тестирование, если бит установлен

Question

Я использую целые числа произвольной точности для представления плотных битовых векторов - размером от десятка до нескольких тысяч.

Мой код часто должен проверять, установлены ли определенные биты (или нет), поэтому я сделал несколько микро-тестов, чтобы увидеть, были ли некоторые вариации значительно быстрее, чем другие:

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) из IntExprI -й бит IntExprV, Оба аргумента должны соответствовать неотрицательным целым числам. Результат эквивалентен (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 |
-------- + ----------------- + ------------------- |
bench_1 | 4547 мс | 3704мс |   900 мс | 780мс |
bench_2 | 4562мс | 3619мс |   970мс |   850мс |
bench_3 | 4541мс | 3603мс |   970мс |   870мс |
bench_4 | 4541мс | 3633мс |   940мс |   890мс |
bench_5 | 4502 мс | 3632мс |   950мс |   840мс |
--------+-----------------+-------------------|
bench_6 | 1424мс | 797мс | на | на |

Похоже, что:

• getbit/2 дал SWI-Prolog ускорение на 500%.

• Параметр командной строки -O дал SWI-Prolog замечательное ускорение.

Есть ли какая-нибудь лучшая формулировка (арифметическая. И т. Д.), Чтобы получить подобное ускорение с SICStus?

Заранее спасибо!

Answer 1

Нет, я не думаю, что есть более быстрые формулировки, чем те, которые вы пробовали. В частности, нет ничего подобного getbit/2 в SICStus (даже не используется внутренне при составлении арифметики).

PS. я хотел бы использовать walltimeВ общем, для бенчмаркинга. Текущие ОС не дают очень надежных runtime,

PPS. Я бы добавил бенчмарк, который использует фиктивную версию тестируемой последовательности кода, просто чтобы убедиться, что тестируемый код на самом деле стоит гораздо дороже, чем тестирование. (Я сделал, и заменить бит-тест с вызовом dummy/3 это ничего не делает, делает это намного быстрее. Так что эталонный тест кажется нормальным.)