rendimiento de coincidencia de patrones Erlang

Question

nuevo en Erlang. Estoy a punto de comenzar a escribir un código. La solución que tengo en mente puede ser de dos maneras. Puedo hacer un montón de cálculos matemáticos, o puedo codificar esto en gran medida como coincidencia de patrones. Cuando digo "coincidencia de patrones", NO me refiero a expresiones regulares ni a nada de eso, me refiero a la coincidencia de patrones en los encabezados de las cláusulas.

El rendimiento no suele ser una preocupación, sin embargo, en esta aplicación sí lo es. No te estoy preguntando qué método sería más rápido; estoy seguro de que dirías que no lo sabes (depende de muchos factores). Lo que estoy preguntando es el rendimiento general de la coincidencia de patrones de Erlang en los encabezados de las cláusulas. En otras palabras, en Prolog, el motor está optimizado para hacer este tipo de cosas, para que todo lo demás sea igual, se le "alienta" a diseñar una solución que aproveche la coincidencia de patrones y la unificación en los encabezados de las cláusulas.

¿Es lo mismo cierto de Erlang, es decir, es Erlang optimizado para la coincidencia de patrones en los encabezados de las cláusulas, similar a Prolog? En lugar de hacer la pregunta aquí, en realidad traté de hacer un perfil de esto en Erlang, y escribí un programa de juguete para hacer un patrón de coincidencia de cabezas de cláusulas un par de millones de veces versus resumir una lista un par de millones de veces. Pero el sistema se bloqueará si se configura para "un par de millones de veces". Pero establecido en menos de un par de millones, los resultados volverían demasiado rápido para saber algo sobre el rendimiento.

Gracias por cualquier idea.

Answer 1

En general, la coincidencia de patrones en los lenguajes funcionales es tan rápida o más rápida que en Prolog. Esperaría que Erlang se desempeñara dentro de un factor de 2 en comparación con Prolog, más rápido o más lento. Como un programa funcional no es más que una coincidencia de patrones, es una de esas áreas que optimiza mucho.

Las partes internas suelen tener un compilador de coincidencias de patrones que convierte una coincidencia de patrón avanzada en una serie más sencilla de comprobaciones con el objetivo de minimizar el número de comprobaciones.

---

Ok, la primera Gotcha: "Cualquier cosa introducido en la cáscara se interpreta". Por lo tanto, compilamos módulos en su lugar:

-module(z). 

-compile(export_all). 

%% This pattern is highly uninteresting because it only matches 
%% on a single value. Any decent system can do this quickly. 
cl(0) -> 0; 
cl(1) -> 0; 
cl(2) -> 0; 
cl(3) -> 0; 
cl(4) -> 0; 
cl(5) -> 0; 
cl(6) -> 0; 
cl(7) -> 0; 
cl(8) -> 0; 
cl(9) -> 0. 

mcl(L) -> 
    [cl(E) || E <- L]. 

Esto nos da un corredor de su ejemplo.

cl2(a, 0) -> a0; 
cl2(a, 1) -> a1; 
cl2(a, 2) -> a2; 
cl2(b, 0) -> b0; 
cl2(b, 1) -> b1; 
cl2(b, 2) -> b2; 
cl2(c, 0) -> c0; 
cl2(c, 1) -> c0; 
cl2(c, 2) -> c0. 

mcl2(L) -> 
    [cl2(A, V) || {A, V} <- L]. 

Un corredor de un ejemplo más interesante. Aquí, podemos explotar omisiones en el patrón. Si (a, 0) no concuerda en el a, sabemos que podemos pasar directamente al caso (b, 0) porque la información de coincidencia negativa se puede propagar como información en el sistema. El compilador de coincidencias de patrones usualmente hace esta optimización.

test1() -> 
    L1 = [X rem 10 || X <- lists:seq(1, 2000000)], 
    %% A Core 2 Duo 2.4Ghz P8600 eats this in 132984 microseconds without HiPE 
    %% c(z). 
    %% With HiPE it is 91195 or in 0.6857591890753775 of the time the non-HiPE variant use 
    %% c(z, [native, {hipe, [o3]}]). 
    timer:tc(z, mcl, [L1]). 

Debe ejecutar este ejemplo usted mismo y evaluar si cree que es lo suficientemente rápido para su caso de uso. Tenga en cuenta que también se gasta algo de tiempo en el código de asignación y se debe dedicar bastante tiempo a extraer datos de la memoria principal a través de las memorias caché de la CPU y en la CPU.

test2() -> 
    random:seed(erlang:now()), 
    L2 = [{case random:uniform(3) of 
        1 -> a; 
        2 -> b; 
        3 -> c 
        end, V rem 3} || V <- lists:seq(1, 2000000)], 
    %% With HiPE this is 220937 
    %% Without HiPE this is 296980 
    timer:tc(z, mcl2, [L2]). 

Naturalmente este ejemplo es más lento, ya que necesitamos para que coincida más datos antes de que tengamos un éxito. Pero es un caso más interesante porque da alguna indicación de la velocidad real del compilador de partidos.

---

versiones paralelas fueron juzgados, pero son aproximadamente 10 veces más lento que en este caso ya que la sobrecarga de crear 2 millones de procesos de trabajo ahora domina el procesamiento real :)

Answer 2

Es básicamente como @ (no muy) RESPUESTAS DE MOLDE :-) ha dicho y muestra su ejemplo.

Prolog en realidad no hace coincidencia de patrones que es unidireccional, lo hace unificación que es algo así como un patrón bidireccional a juego con las variables lógicas. Es mucho más fácil optimizar la coincidencia de patrones y los lenguajes funcionales serios como Erlang y Haskell ponen bastante trabajo en un compilador de coincidencia de patrones optimizado. Esto es especialmente notable con patrones profundos.

Entonces, sí, Erlang hará patrones que coincidan más rápido que Prolog.