sbcl é executado para sempre na segunda chamada de função

Question

A função:

Dada uma lista, lst retorna todas as permutações do conteúdo da lista com comprimento exato k, cujo padrão é o comprimento da lista, se não for fornecido.

(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))))))

O problema:Estou usando SLIME no emacs conectado ao sbcl, ainda não fiz muita customização.A função funciona bem em entradas menores, como lst = '(1 2 3 4 5 6 7 8) k = 3, que é para isso que será usada principalmente na prática.No entanto, quando eu chamo com uma entrada grande duas vezes seguidas, a segunda chamada nunca retorna e o sbcl nem aparece no topo.Estes são os resultados do 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))))

E nunca volta da segunda ligação.Só posso imaginar que, por algum motivo, estou fazendo algo horrível com o coletor de lixo, mas não consigo ver o quê.Alguém tem alguma idéia?

Answer 1

Uma coisa que está errada no seu código é o uso do EQ.EQ compara a identidade.

EQ não serve para comparar números.EQ de dois números pode ser verdadeiro ou falso.

Use EQL se quiser comparar por identidade, números por valor ou caracteres.Não EQ.

Na verdade

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

é apenas

(remove item list)

Para o seu código, o bug EQ PODERIA significa que permute é chamado na chamada recursiva sem realmente remover um número da lista.

Fora isso, acho que o SBCL está ocupado apenas com gerenciamento de memória.O SBCL no meu Mac adquiriu muita memória (mais de um GB) e estava ocupado fazendo alguma coisa.Depois de algum tempo o resultado foi computado.

Sua função recursiva gera uma enorme quantidade de ‘lixo’.LispWorks diz:1360950192 bytes

Talvez você possa criar uma implementação mais eficiente?

Atualizar: lixo

Lisp fornece algum gerenciamento automático de memória, mas isso não libera o programador de pensar nos efeitos de espaço.

Lisp usa uma pilha e um heap para alocar memória.O heap pode ser estruturado de certas maneiras para o GC - por exemplo, em gerações, meios espaços e/ou áreas.Existem coletores de lixo precisos e coletores de lixo 'conservadores' (usados ​​pelo SBCL em máquinas Intel).

Quando um programa é executado, podemos ver vários efeitos:

1. procedimentos recursivos normais alocam espaço na pilha.Problema:o tamanho da pilha geralmente é fixo (mesmo que alguns Lisps possam aumentá-lo em um manipulador de erros).

2. um programa pode alocar uma grande quantidade de memória e retornar um grande resultado.PERMUTE é uma dessas funções.Pode retornar listas muito grandes.

3. um programa pode alocar memória e usá-la temporariamente e então o coletor de lixo pode reciclá-la.A taxa de criação e destruição pode ser muito alta, mesmo que o programa não utilize uma grande quantidade de memória fixa.

Existem mais problemas, no entanto.Mas para cada um dos itens acima, o programador Lisp (e todos os outros programadores que usam uma implementação de linguagem com coleta de lixo) precisa aprender como lidar com isso.

1. Substitua recursão por iteração.Substitua a recursão pela recursão de cauda.

2. Retorne apenas a parte necessária do resultado e não gere a solução completa.Se você precisar da enésima permutação, calcule-a e não todas as permutações.Use estruturas de dados preguiçosas que são computadas sob demanda.Use algo como SERIES, que permite usar computação semelhante a um fluxo, mas eficiente.Consulte SICP, PAIP e outros livros avançados sobre Lisp.

3. Reutilize a memória com um gerenciador de recursos.Reutilize buffers em vez de alocar objetos o tempo todo.Use um coletor de lixo eficiente com suporte especial para coletar objetos efêmeros (de curta duração).Às vezes também pode ajudar modificar objetos de forma destrutiva, em vez de alocar novos objetos.

Acima trata dos problemas de espaço de programas reais.Idealmente, nossos compiladores ou infraestrutura de tempo de execução podem fornecer algum suporte automático para lidar com esses problemas.Mas, na realidade, isso realmente não funciona.A maioria dos sistemas Lisp fornece funcionalidade de baixo nível para lidar com isso e o Lisp fornece objetos mutáveis ​​- porque a experiência de programas Lisp do mundo real mostrou que os programadores desejam usá-los para otimizar seus programas.Se você tiver um aplicativo CAD grande que calcula a forma de pás de turbina, as visões teóricas/purísticas sobre memória não mutável simplesmente não se aplicam - o desenvolvedor deseja o código mais rápido/menor e o menor espaço de tempo de execução.

Answer 2

O SBCL na maioria das plataformas usa coletor de lixo geracional, o que significa que a memória alocada que sobrevive mais do que algum número de coleções será mais raramente considerada para a coleta. Seu algoritmo para o caso de teste fornecido gera tanto lixo que desencadeia o GC tantas vezes que os resultados reais, que obviamente precisam sobreviver a todo o tempo de execução da função, são titulares, ou seja, movidos para uma geração final que é coletada muito raramente ou de jeito nenhum. Portanto, a segunda execução, em configurações padrão para sistemas de 32 bits, ficará sem heap (512 MB, pode ser aumentada com as opções de tempo de execução).

Dados titulares podem ser coletados de lixo, acionando manualmente o coletor com (sb-ext:gc :full t). Isso é obviamente dependente da implementação.

Answer 3

Pela aparência da saída, você está olhando para o Slime-Repl, certo?

Tente mudar para o buffer "*inferior-lisp*", você provavelmente verá que o SBCL caiu para o LDB (depurador de baixo nível embutido). Provavelmente, você conseguiu explodir a pilha de chamadas.