Производительность встроенного предиката Пролог (есть)/2

Обновление: 11.6.2016

Расхождение производительности, которое я наблюдал с SICStus Prolog 4.3.2, полностью исчезло с недавно выпущенным SICStus Prolog 4.3.3. Престижность!

Я обновил таблицу "runtimes" ниже, чтобы включить SICStus Prolog 4.3.3. Основные моменты включают в себя:

  • (is)/2 до 10 раз быстрее, чем раньше.
  • val_of/2 тоже значительно ускорился, почти в 2 раза!

MEGO;-)

Отвечая на вопрос " Процедура определения размера на языке Thanos Tintinidis предложил весьма простой способ 1 познакомить новичков с производными length/2:

[...] Также обратите внимание, что E должен быть создан только потому, что собирается оценить выражение. Вы могли бы написать что-то вроде этого:

 размер ([], 0).
размер ([_|Xs], 1+E):- размер (Xs, E).

и если вы называете это:

? - размер ([_,_], E).
Е = 1+(1+0).

Веселье, не правда ли? Вы можете оценить последний E т.е. звонить ?- size([1,2], E), N is E, [...]

Веселье? Большое веселье! Впереди целый ряд интересных экспериментов:

  • Левые и правые деревья

    list_siz L ([], 0). % l наклона кверху list_sizL ([_ | Es], N + 1): - list_sizL (Es, N). list_siz R ([], 0). % r наклоняющийся list_sizR([_|Es], 1+N):- list_sizR(Es,N).

  • встроенный (is)/2 против val_of/2

    val_of(V, E):- ( E = E1+E2 -> val_of(V1, E1), val_of(V2, E2), V - V1+V2; число (E) -> V = E).

Чтобы измерить время выполнения я побежал go(2000000) используя разные процессоры Prolog 2:

идти (L):- 
   длина (Xs, L),
   член (B_2, [list_sizL,list_sizR]),
   вызов (B_2, Xs, E),
   член (P_2, [is, val_of]), 
   call_time (вызов (P_2,N,E), T),
   ( L = N -> writeq(B_2+P_2=T), nl; throw(вверх)).

На Intel Core i7-4700MQ я наблюдал следующие среды выполнения с SICStus и SWI:

                          | SWI | SICStus | SICStus |
                          | 7.3.20 | 4.3.2 | 4.3 .3 |
       ------------------- + -------- + --------- + --------- |
       list_sizL + (есть)   | 208 мс |  650 мс | 60 мс | 3.4x
       list_sizL + val_of | 381 мс |  100 мс |   60 мс | 6.3x
       -------------------+--------+---------+---------|
       list_sizR + (есть)   |  88 мс |  660 мс | 70 мс | 1.2x
       list_sizR + val_of | 346 мс |  100 мс |   60 мс | 5.7x
       -------------------+--------+---------+---------|

Я озадачен этими (воспроизводимыми) результатами... Может кто-нибудь сказать мне, что происходит?

Сноска 1: Для краткости и читабельности имена переменных были немного адаптированы.
Сноска 2: Запуск SWI-Prolog 7.3.20 с подходящими аргументами командной строки swipl -G2G -L2G -O ,

Источник

3 ответа

Решение

Я могу подтвердить удивительный факт, что в SICStus Prolog, val_of/2 намного быстрее чем is/2 когда выражение является большим составным термином, т.е. когда is/2 интерпретирует выражение.

В текущей реализации SICStus скомпилировано is/2 необходимо экранировать код Пролога, когда аргумент арифметического оператора не является числом. При интерпретации глубоких выражений это экранирование происходит для всех аргументов рекурсивно, что намного медленнее, чем val_of/2 делает, то есть простой Пролог к ​​Прологу звонит.

Я сделал проверку концепции для основной проблемы, он сделал is/2 случай в программе выше примерно с той же скоростью, что и val_of/2, Это изменение было включено в текущую версию SICStus Prolog (4.3.3).

Источник

Вы сравниваете две очень разные реализации (is)/2, SWI обнаруживает ошибки экземпляров и циклические выражения до фактической оценки. SICStus не делает. Попробуйте это с:

?- E=(1/0)+_, X is E.
?- E=(1/0)+E, X is E.

SWI создает ошибку инстанцирования и ошибку типа (из-за бесконечного дерева), тогда как SICStus всегда оценивает 1/0 и выдает ошибку оценки в обоих случаях. И (по крайней мере, для этого самого примера) оба соответствуют.

Разница в скорости между оценками двух древовидных структур обусловлена ​​оптимизацией хвостовой рекурсии в ground/1 а также acyclic_term/1 в SWI. Текущий алгоритм использует стек и обращается к аргументам слева направо. Таким образом, дерево, вложенное справа, требует постоянного вспомогательного пространства и, следовательно, намного быстрее.

SICStus использует Deutsch-Schorr-Waite для acyclic_term/1 а также ground/1и, следовательно, не имеет явного стека и, следовательно, не TRO. По крайней мере, оба имеют примерно одинаковую скорость для левого и правого.

Источник

Проще говоря, я думаю, что SWI-Prolog уделяет больше внимания арифметике, в то время как SICStus имеет лучшую генерацию кода для общего потока управления.

Возможно, лучшую производительность можно было бы получить из SWI-Prolog с помощью частичной оценки, которая очень хорошо представлена ​​Перейрой-Шибер в главе 6 Пролога и анализа естественного языка.

Вам также следует дать шанс YAP: он считается самым быстрым Прологом на основе WAM. Я помню, как Ян Уилмейкер отмечал в списке SWI-Prolog, что большая часть скорости YAP была получена путем массивного переписывания - скажем, встраивания. Что-то, на мой взгляд, основано (конечно, хорошо) на частичной оценке.

Источник
Другие вопросы по тегам