SBCL se ejecuta para siempre en la segunda llamada de función

Question

La función:

Dada una lista, devuelve todas las permutaciones de los contenidos de la lista de exactamente longitud k, lo que predeterminado es la longitud de la lista si no se proporciona.

(defun permute (lst &optional (k (length lst)))
  (if (= k 1)
   (mapcar #'list lst)
   (loop for item in lst nconcing
     (mapcar (lambda (x) (cons item x)) 
             (permute (remove-if (lambda (x) (eq x item)) lst) 
                      (1- k))))))

El problema: estoy usando limo en emacs conectados a SBCL, todavía no he hecho demasiada personalización. La función funciona bien en entradas más pequeñas como LST = '(1 2 3 4 5 6 7 8) K = 3, que es para lo que se usará principalmente en la práctica. Sin embargo, cuando lo llamo con una entrada grande dos veces seguidas, la segunda llamada nunca regresa y SBCL ni siquiera aparece en la parte superior. Estos son los resultados en el repl:

CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))
Evaluation took:
12.263 seconds of real time
12.166150 seconds of total run time (10.705372 user, 1.460778 system)
[ Run times consist of 9.331 seconds GC time, and 2.836 seconds non-GC time. ]
99.21% CPU
27,105,349,193 processor cycles
930,080,016 bytes consed

(2 7 8 3 9 1 5 4 6 0)
CL-USER> (time (nth (1- 1000000) (permute '(0 1 2 3 4 5 6 7 8 9))))

Y nunca regresa de la segunda llamada. Solo puedo adivinar que por alguna razón estoy haciendo algo horrible para el recolector de basura, pero no puedo ver qué. ¿Alguien tiene alguna idea?

Answer 1

Una cosa que está mal en su código es su uso de la ecuación. EQ se compara para la identidad.

EQ no es para comparar números. El ecualizador de dos números puede ser verdadero o falso.

Use EQL si desea comparar por identidad, números por valor o caracteres. No la ecuación.

Realmente

(remove-if (lambda (x) (eql x item)) list)

es solo

(remove item list)

Para su código, el error de ecualización PUDO significa que Permute se llama en la llamada recursiva sin realmente un número eliminado de la lista.

Aparte de eso, creo que SBCL está ocupado con la gestión de la memoria. SBCL en mi Mac adquirió mucha memoria (más que un GB) y estaba ocupado haciendo algo. Después de algún tiempo se calculó el resultado.

Su función recursiva genera una gran cantidad de 'basura'. Lispworks dice: 1360950192 bytes

¿Quizás se le ocurra una implementación más eficiente?

Actualizar: basura

LISP proporciona algo de gestión automática de memoria, pero eso no libera al programador de pensar en los efectos de espacio.

LISP usa una pila y el montón para asignar memoria. El montón tal vez estructurado de ciertas maneras para el GC, por ejemplo, en generaciones, mitad espacios y/o áreas. Hay recolectores de basura precisos y colectores de basura 'conservadores' (utilizados por SBCL en máquinas Intel).

Cuando se ejecuta un programa, podemos ver varios efectos:

1. Los procedimientos recursivos normales asignan espacio en la pila. Problema: el tamaño de la pila generalmente se soluciona (aunque algunas LISP pueden aumentarlo en un manejador de errores).

2. Un programa puede asignar una gran cantidad de memoria y devolver un gran resultado. Permute es tal función. Puede devolver listas muy grandes.

3. Un programa puede asignar la memoria y usarla temporalmente y luego el recolector de basura puede reciclarla. La tasa de creación y destrucción puede ser muy alta, a pesar de que el programa no usa una gran cantidad de memoria fija.

Sin embargo, hay más problemas. Pero para cada uno de los programadores LISP anteriores (y cualquier otro programador que use una implementación del lenguaje con recolección de basura) tiene que aprender a lidiar con eso.

1. Reemplace la recursión con iteración. Reemplace la recursión con recursión de cola.

2. Devuelva solo la parte del resultado que se necesita y no genere la solución completa. Si necesita la permutación N-th, calcule eso y no todas las permutaciones. Utilice datos perezosos que se calculen a pedido. Use algo como series, que permite usar cálculo similar a la transmisión, pero eficiente. Ver SICP, PAIP y otros libros avanzados de Lisp.

3. Reutilizar la memoria con un administrador de recursos. Reutilizar buffers en lugar de asignar objetos todo el tiempo. Use un recolector de basura eficiente con un soporte especial para recolectar objetos efímeros (de corta duración). A veces también puede ayudar a modificar destructivamente objetos, en lugar de asignar nuevos objetos.

Anterior trata los problemas de espacio de los programas reales. Idealmente, nuestros compiladores o infraestructura de tiempo de ejecución pueden proporcionar algún soporte automático para abordar estos problemas. Pero en realidad esto realmente no funciona. La mayoría de los sistemas LISP proporcionan una funcionalidad de bajo nivel para tratar esto y LISP proporciona objetos mutables, porque la experiencia de los programas LISP del mundo real ha demostrado que los programadores desean usarlos para optimizar sus programas. Si tiene una gran aplicación CAD que calcula la forma de las cuchillas de la turbina, entonces las vistas teóricas/puristas sobre la memoria no mutable simplemente no se aplica: el desarrollador quiere el código más rápido/más pequeño y la huella de tiempo de ejecución más pequeña.

Answer 2

SBCL en la mayoría de las plataformas utiliza el recolector de basura generacional, lo que significa que la memoria asignada que sobrevive a más de una cantidad de colecciones rara vez se considerará para la recolección. Su algoritmo para el caso de prueba dado genera tanta basura que desencadena a GC tantas veces que los resultados reales, que obviamente tienen que sobrevivir a todo el tiempo de ejecución de la función, se mueven, es decir, se trasladan a una generación final que se recolecta muy raramente o no en absoluto. Por lo tanto, la segunda ejecución, en configuraciones estándar para sistemas de 32 bits, se ejecutará sin montón (512 MB, se puede aumentar con las opciones de tiempo de ejecución).

Los datos titulares se pueden recopilar basura activando manualmente el colector con (sb-ext:gc :full t). Obviamente, esto depende de la implementación.

Answer 3

De la apariencia de la salida, estás mirando la replicación de limo, ¿verdad?

Intente cambiar al búfer "*inferior-lisp*", probablemente verá que SBCL ha caído al LDB (depurador de bajo nivel incorporado). Lo más probable es que haya logrado volar la pila de llamadas.