[Openmcl-devel] consing

[Joshua TAYLOR]

On Tue, May 14, 2013 at 12:23 PM, Taoufik Dachraoui
<dachraoui.taoufik at gmail.com> wrote:
> I did the following test with (fac 100) and (ack 3 12) and (ack 3 13) ;;
> ack is the ackermann function
>
> CL-USER> (time (fac 100))
> (FAC 100)
> took 0 milliseconds (0.000 seconds) to run.
> During that period, and with 1 available CPU core,
>      0 milliseconds (0.000 seconds) were spent in user mode
>      0 milliseconds (0.000 seconds) were spent in system mode
>  3,864 bytes of memory allocated.
> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
>
> CL-USER> (time (ack 3 12))
> (ACK 3 12)
> took 3,325 milliseconds (3.325 seconds) to run.
> During that period, and with 1 available CPU core,
>      3,360 milliseconds (3.360 seconds) were spent in user mode
>          0 milliseconds (0.000 seconds) were spent in system mode
> 32765
>
> (ack 3 13) fails with stack overflow, this I do not understand; (ack 3 12)
> did not show any use of memory allocation
> and (ack 3 13) fails for stack overflow?

Re factorial: If your numbers are big, you'll end up using
heap-allocated bignums, I expect, so it's no suprise that you start
consing.

Re Ackerman: Though a stack overflow is in one sense a problem with
memory usage, it's not a heap-allocation problem.  It's a problem with
the recursion in the program going too deep and not having enough
space to store the program stack.  If you had more space to store you
stack, and (ack 3 13) didn't overflow, you still wouldn't see memory
allocation as a result of the stack, but of the large numbers you end
up using that are allocated in the heap.

Tracing data that reports memory allocation isn't telling you about
how much memory was used by the stack, but rather in the heap.

As an example, consider two silly functions:

(defun deep-list-1 (n &optional (acc '()))
  (if (zerop n) (cons 1 2)
      (let ((acc (cons n acc)))
        (deep-list-1 (1- n) acc))))

(defun deep-list-2 (n &optional (acc '()))
  (if (zerop n) (cons 1 2)
      (let ((acc (cons n acc)))
        (declare (dynamic-extent acc))
        (deep-list-2 (1- n) acc))))

Each constructs a list of length n and then returns a cons cell '(1 .
2) so that there is some heap allocation in both.  Deep-list-1
constructs the list out of cons cells in the heap, allocating lots of
memory.  Deep-list-2 uses a dynamic-extent declaration to create the
cons cells on the stack, using no heap allocation aside from the final
return value.  Look what happens:

CL-USER> (time (deep-list-1 10000))
(DEEP-LIST-1 10000) took 102 microseconds (0.000102 seconds) to run
                    with 4 available CPU cores.
During that period, 0 microseconds (0.000000 seconds) were spent in user mode
                    0 microseconds (0.000000 seconds) were spent in system mode
 160,016 bytes of memory allocated.
(1 . 2)

CL-USER> (time (deep-list-2 10000))
(DEEP-LIST-2 10000) took 156 microseconds (0.000156 seconds) to run
                    with 4 available CPU cores.
During that period, 0 microseconds (0.000000 seconds) were spent in user mode
                    0 microseconds (0.000000 seconds) were spent in system mode
 16 bytes of memory allocated.
(1 . 2)

Now, if we increase the depth, we get different behaviors.
Deep-list-1 can go deeper, because each stack frame is smaller, and
deep-list-2 fails much earlier.



-- 
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/