performance haskell prolog alias

performance - ¿Prolog tiene un "operador" de alias como Haskell?



(1)

TL; DR: ¡ Buena idea 1 ! La aceleración parece estar limitada a ~ 20% (para la mayoría de los tamaños de lista).

En esta respuesta, comparamos tres predicados diferentes que difieren con respecto @ la reutilización de datos de tipo @ :

list_tails([], [[]]). % (1) like `tails/2` given by the OP ... list_tails([E|Es], [[E|Es]|Ess]) :- % ....... but with a better name :-) list_tails(Es, Ess). list_sfxs1(Es, [Es|Ess]) :- % (2) "re-use, mutual recursion" aux_list_sfxs1(Es, Ess). % "sfxs" is short for "suffixes" aux_list_sfxs1([], []). aux_list_sfxs1([_|Es], Ess) :- list_sfxs1(Es, Ess). list_sfxs2([], [[]]). % (3) "re-use, direct recursion" list_sfxs2(Es0, [Es0|Ess]) :- Es0 = [_|Es], list_sfxs2(Es, Ess).

Para medir el tiempo de ejecución, utilizamos el siguiente código:

:-( dif(D,sicstus), current_prolog_flag(dialect,D) ; use_module(library(between)) ). run_benchs(P_2s, P_2, L, N, T_ms) :- between(1, 6, I), L is 10^I, N is 10^(8-I), length(Xs, L), member(P_2, P_2s), garbage_collect, call_walltime(run_bench_core(P_2,Xs,N), T_ms). run_bench_core(P_2, Xs, N) :- between(1, N, _), call(P_2, Xs, _), false. run_bench_core(_, _, _).

Para medir wall-time 2 , utilizamos call_ walltime /2 -una variación de call_time/2 :

call_walltime(G, T_ms) :- statistics(walltime, [T0|_]), G, statistics(walltime, [T1|_]), T_ms is T1 - T0.

Pongamos las variaciones de código anteriores a prueba ...

  • ... usando diferentes longitudes de lista L ...
  • ... y ejecutar cada prueba varias veces N (para una mejor precisión).

Primero, usamos swi-prolog versión 7.3.14 (64-bit):

?- run_benchs([list_sfxs1,list_sfxs2,list_tails], P_2, L, N, T_ms). P_2 = list_sfxs1, L*N = 10*10000000, T_ms = 7925 ; P_2 = list_sfxs2, L*N = 10*10000000, T_ms = 7524 ; P_2 = list_tails, L*N = 10*10000000, T_ms = 6936 ; P_2 = list_sfxs1, L*N = 100*1000000, T_ms = 6502 ; P_2 = list_sfxs2, L*N = 100*1000000, T_ms = 5861 ; P_2 = list_tails, L*N = 100*1000000, T_ms = 5618 ; P_2 = list_sfxs1, L*N = 1000*100000, T_ms = 6434 ; P_2 = list_sfxs2, L*N = 1000*100000, T_ms = 5817 ; P_2 = list_tails, L*N = 1000*100000, T_ms = 9916 ; P_2 = list_sfxs1, L*N = 10000*10000, T_ms = 6328 ; P_2 = list_sfxs2, L*N = 10000*10000, T_ms = 5688 ; P_2 = list_tails, L*N = 10000*10000, T_ms = 9442 ; P_2 = list_sfxs1, L*N = 100000*1000, T_ms = 10255 ; P_2 = list_sfxs2, L*N = 100000*1000, T_ms = 10296 ; P_2 = list_tails, L*N = 100000*1000, T_ms = 14592 ; P_2 = list_sfxs1, L*N = 1000000*100, T_ms = 6955 ; P_2 = list_sfxs2, L*N = 1000000*100, T_ms = 6534 ; P_2 = list_tails, L*N = 1000000*100, T_ms = 9738.

Luego, repetimos la consulta previa 3 usando sicstus-prolog versión 4.3.2 (64-bit):

?- run_benchs([list_sfxs1,list_sfxs2,list_tails], P_2, L, N, T_ms). P_2 = list_sfxs1, L*N = 10*10000000, T_ms = 1580 ; P_2 = list_sfxs2, L*N = 10*10000000, T_ms = 1610 ; P_2 = list_tails, L*N = 10*10000000, T_ms = 1580 ; P_2 = list_sfxs1, L*N = 100*1000000, T_ms = 710 ; P_2 = list_sfxs2, L*N = 100*1000000, T_ms = 750 ; P_2 = list_tails, L*N = 100*1000000, T_ms = 840 ; P_2 = list_sfxs1, L*N = 1000*100000, T_ms = 650 ; P_2 = list_sfxs2, L*N = 1000*100000, T_ms = 660 ; P_2 = list_tails, L*N = 1000*100000, T_ms = 740 ; P_2 = list_sfxs1, L*N = 10000*10000, T_ms = 620 ; P_2 = list_sfxs2, L*N = 10000*10000, T_ms = 650 ; P_2 = list_tails, L*N = 10000*10000, T_ms = 740 ; P_2 = list_sfxs1, L*N = 100000*1000, T_ms = 670 ; P_2 = list_sfxs2, L*N = 100000*1000, T_ms = 650 ; P_2 = list_tails, L*N = 100000*1000, T_ms = 750 ; P_2 = list_sfxs1, L*N = 1000000*100, T_ms = 12610 ; P_2 = list_sfxs2, L*N = 1000000*100, T_ms = 12560 ; P_2 = list_tails, L*N = 1000000*100, T_ms = 33460.

Resumen:

  • El alias-cosa puede y mejora el rendimiento de manera significativa.
  • En las pruebas anteriores, el SICStus Prolog jit 4 ofrece 10 veces más velocidad que el SWI-Prolog.

Nota 1: ¿Por qué el truco de poner (@)/2 en la cabeza de la regla? ¿Para terminar con el código de Prolog no idiomático ?
Nota 2: estamos interesados ​​en el tiempo de ejecución total. ¿Por qué? ¡Porque los costos de recolección de basura se muestran con tamaños de datos más grandes!
Nota 3: la secuencia de respuesta se ha procesado posteriormente por razones de legibilidad.
Nota al pie 4: Disponible desde la versión 4.3.0 . Las arquitecturas de destino actuales incluyen IA-32 y AMD64 .

En Haskell, hay una función de idioma llamada "como" -operador (a veces conocido como alias). La idea es la siguiente: dado que tienes una función que, por ejemplo, toma como entrada una lista y quiere devolver todas las colas, puedes implementar esto como:

tails a@(_:xs) = a : tails xs tails [] = [[]]

El @ garantiza que tiene una referencia tanto al argumento completo como a una referencia a algunas partes de la estructura del parámetro. Esto es inteligente en cuanto a rendimiento (es más un truco de rendimiento, porque reconstruir una matriz (x:xs) ) en el cuerpo de la primera línea, si el compilador no lo optimiza, dará como resultado la asignación de un nuevo objeto, modificando los campos , etc. Consulte aquí para obtener más información.

Me preguntaba si Prolog tiene algo equivalente: por ejemplo, si quiere implementar colas en Prolog, puede hacerlo de la siguiente manera:

tails([H|T],[[H|T]|TA]) :- tails(T,TA). tails([],[[]]).

Pero podría ser más eficiente si hubiera un operador "as" como:

tails(L@[_|T],[L|TA]) :- %This does not compile tails(T,TA). tails([],[[]]).

¿Hay alguna construcción o una extensión de idioma?