Sbcl works forever on the second function call

Question

Function:

Given the lst list, return all permutations of the contents of the list to exactly length k, which by default matches the length of the list, if not specified.

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

Problem: I am using SLIME in emacs connected to sbcl, I have not done too many settings yet. The function works fine on smaller inputs, such as lst = '(1 2 3 4 5 6 7 8) k = 3, which will be used in practice. However, when I call it with more input twice in a row, the second call never returns and sbcl does not even appear at the top. These are the results in the 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)))) 

And he never returns from the second call. I can only guess that for some reason I am doing something terrible for the garbage collector, but I do not see that. Does anyone have any idea?

Answer 1

One thing that doesn't match your code is the use of an equalizer. EQ is compared for identity.

EQ is not for comparing numbers. The EQ of two numbers can be true or false.

Use EQL if you want to compare by identifier, numbers by value, or characters. Not an EQ.

In fact

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

just

 (remove item list) 

For your code, an EQ COULD error means that the permutation is called in a recursive call without the actual number removed from the list.

Other than that, I think SBCL is just busy managing memory. SBCL on my Mac acquired a lot of memory (more than GB) and was busy with something busy. After a while, the result was calculated.

Your recursive function generates a huge amount of garbage. LispWorks says: 1360950192 bytes

Perhaps you can come up with a more efficient implementation?

Update: trash

Lisp provides some automatic memory management, but this does not free the programmer from thinking about space effects.

Lisp uses both the stack and the heap to allocate memory. A heap can be structured in specific ways for a GC — for example, in generations, half-spaces, and / or regions. There are accurate garbage collectors and "conservative" garbage collectors (used by SBCL on Intel machines).

When the program starts, we can see various effects:

• normal recursive procedures allocate space on the stack. Problem: The stack size is usually fixed (although some Lisps may increase it in the error handler).

• a program can allocate a huge amount of memory and return a large result. PERMUTE is such a function. It can return very large lists.

• the program can allocate memory and use it temporarily, and then the garbage collector can recycle it. The speed of creation and destruction can be very high, although the program does not use a large amount of fixed memory.

However, there are more problems. But for each of the above, a Lisp programmer (and every other programmer using a garbage collection language implementation) must learn to deal with this.

• Replace recursion with an iteration. Replace recursion with tail recursion.

• It returns only the part of the result that is necessary and does not generate a complete solution. If you need the nth permutation, then calculate that not all permutations. Use lazy data structures that compute on demand. Use something like SERIES, which allows you to use streaming but efficient computing. See SICP, PAIP, and other extended Lisp books.

• Reusing memory with the resource manager. Reuse buffers instead of allocating objects all the time. Use an efficient garbage collector with special support to collect ephemeral (short-lived) objects. Sometimes it can also help destroy objects, rather than highlight new objects.

The space problems of real programs are considered above. Ideally, our compilers or runtimes can provide some automatic support to solve these problems. But actually it does not work. Most Lisp systems provide low-level functionality to solve this problem, and Lisp provides mutable objects because the experience of real Lisp programs has shown that programmers want to use them to optimize their programs. If you have a large CAD application that calculates the shape of turbine blades, then theoretical / puristic ideas about unchangeable memory are simply not applied - the developer needs faster / smaller code and shorter execution time.

Answer 2

SBCL on most platforms uses a collective garbage collector, which means that allocated memory that survives more than a certain number of collections will be rarely considered for collection. Your algorithm for this test case generates so much garbage that it launches the GC so many times that the actual results, which obviously must withstand the entire functional runtime, are saved, that is, they are transferred to the final generation, which is collected either very rarely or not at all . Thus, in the second launch, at the standard settings for 32-bit systems, the heap will end (512 MB, it can be increased using the runtime parameters).

Retained data can be collected in garbage by manually starting the collector with (sb-ext:gc :full t) . It obviously depends on the implementation.

Answer 3

From the look of the output, you look at slime-repl, right?

Try going to the buffer "* inferior- lisp *", you will probably see that SBCL fell to ldb (built-in low-level debugger). Most likely, you managed to blow up the call stack.