consing

[Taoufik Dachraoui]

Hi

This is probably simple but I could not figure out the explanation, I hope that
someone could help me out

Using Clozure-CL
CL-USER> (defun fac (n) (if (= n 0) 1 (* n (fac (- n 1)))))
FAC
CL-USER> (time (fac 3))
(FAC 3)
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
6

As you can see, there is no consing when FAC is called

Now, knowing that pushing an element on the stack, (PUSH 1 X) is equivalent
to (SETQ X (CONS 1 X)), and since FAC is using a stack and thus pushing
values on the stack why there is no consing when (FAC 3) is called?

I believe there is a simple explanation but I could not figure it out

Kind regards

[Max Rottenkolber]

FAC is pushing to the internal call stack yes. Try calling (FAC 100):

(time (fac 100))
(FAC 100)

took 0 milliseconds (0.000 seconds) to run.

During that period, and with 2 available CPU cores,

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.

I guess when you call (FAC 3) the whole call graph fits into the
preallocated stack. As soon as FAC asks for more than it has by default
it will allocate more. It's just that a minimum stack size is allocated
in good faith so that cheap functions don't have to go the overhead of
allocation. What good would be (FAC 3) if it spent more time allocating
memory than calculating the faculty? So it is a time/space tradeoff.

I don't know how it is exactly handled in CCL. But my point is, the
compiler may employ optimizations that affect the programs memory
allocation "rythm". Pretty much the same way you could decide that a
certain function allocates and frees lots of cons cells and decide that
its faster to manage and reuse a pool of cons cells yourself instead of
asking the compiler for a single cell every time you need one.

In this specific case the compiler decided that its not worth to allocate
memory for small computations like (FAC 3), it probably had enough unused
memory laying around for cases just like this.

Hope this helps! :)


--
Max Rottenkolber
Rottenkolber Software Engineering
http://mr.gy

[Norbert_Paul]

The difference is, that CONS creates a new data structure with
a CAR-attribute (or "slot") and a "CDR"-slot. This is NOT the
processor stack and PUSH does NOT call the corresponding machine
code instruction. CONS can be used to emulate a stack.

Note this on SBCL:

* (defvar *stack* ())
==> *STACK*

* (disassemble #'(lambda (item) (push item *stack*)))
; disassembly for (LAMBDA (ITEM))
; 0AB6252F: 8B0D0025B60A MOV ECX, [#xAB62500] ; '*STACK*
; no-arg-parsing entry point
; 35: 8B4111 MOV EAX, [ECX+17]
; 38: 64 FS-SEGMENT-PREFIX
; 39: 8B00 MOV EAX, [EAX]
; 3B: 83F85A CMP EAX, 90
; 3E: 7503 JNE L0
; 40: 8B41FD MOV EAX, [ECX-3]
; 43: L0: 83F84A CMP EAX, 74
; 46: 742E JEQ L3
; 48: E897E549F6 CALL #x1000AE4 ; ALLOCATE-CONS-TO-ECX
; 4D: 8951FD MOV [ECX-3], EDX
; 50: 894101 MOV [ECX+1], EAX
; 53: 8B150025B60A MOV EDX, [#xAB62500] ; '*STACK*
; 59: 8B4211 MOV EAX, [EDX+17]
; 5C: 64 FS-SEGMENT-PREFIX
; 5D: 83385A CMP DWORD PTR [EAX], 90
; 60: 7405 JEQ L1
; 62: 64 FS-SEGMENT-PREFIX
; 63: 8908 MOV [EAX], ECX
; 65: EB03 JMP L2
; 67: L1: 894AFD MOV [EDX-3], ECX
; 6A: L2: 8BD1 MOV EDX, ECX
; 6C: 8BE5 MOV ESP, EBP
; 6E: F8 CLC
; 6F: 5D POP EBP
; 70: C3 RET
; 71: CC0A BREAK 10 ; error trap
; 73: 02 BYTE #X02
; 74: 18 BYTE #X18 ; INVALID-ARG-COUNT-ERROR
; 75: 4F BYTE #X4F ; ECX
; 76: L3: CC0A BREAK 10 ; error trap
; 78: 02 BYTE #X02
; 79: 1A BYTE #X1A ; UNBOUND-SYMBOL-ERROR
; 7A: 50 BYTE #X50 ; ECX
==> NIL

So there is no machine-PUSH instruction in sbcl when Lisp-PUSH is used.

Norbert

[Pascal J. Bourguignon]

Max Rottenkolber <m...@mr.gy> writes:

> FAC is pushing to the internal call stack yes. Try calling (FAC 100):

(/ (integer-length (alexandria:factorial 100)) (log 10 2))
--> 158.04076

> (time (fac 100))
> (FAC 100)
> took 0 milliseconds (0.000 seconds) to run.
> During that period, and with 2 available CPU cores,
> 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.

That covers the 90 bignums allocated on the heap, not the 100 stack
frames allocated on the system stack.

CONSing covers in general only the heap, not the stack.

See for example (ROOM t). It won't report the stack space used by the
various threads, only the lisp objects stored on the heap.


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
You can take the lisper out of the lisp job, but you can't take the lisp out
of the lisper (; -- antifuchs

[Barry Margolin]

In article <87zjvxi...@kuiper.lan.informatimago.com>,

"Pascal J. Bourguignon" <p...@informatimago.com> wrote:

> Max Rottenkolber <m...@mr.gy> writes:
>
> > FAC is pushing to the internal call stack yes. Try calling (FAC 100):
>
> (/ (integer-length (alexandria:factorial 100)) (log 10 2))
> --> 158.04076
>
>
> > (time (fac 100))
> > (FAC 100)
> > took 0 milliseconds (0.000 seconds) to run.
> > During that period, and with 2 available CPU cores,
> > 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.
>
> That covers the 90 bignums allocated on the heap, not the 100 stack
> frames allocated on the system stack.
>
> CONSing covers in general only the heap, not the stack.
>
> See for example (ROOM t). It won't report the stack space used by the
> various threads, only the lisp objects stored on the heap.

The reason for this is that heap allocations impact garbage collection
time, which can be a major influence on application performance (and
certainly was when much of this was designed in the 70's and 80's).
Stack allocation, in this regard, is almost free -- as long as you don't
run out of stack space, you're OK. If it's a copying GC, as I think is
most common in Lisp implementations, live heap objects need to be
copied, but stack-allocated objects do not (but they're still used as
the root of the GC scan).

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[Max Rottenkolber]

> That covers the 90 bignums allocated on the heap, not the 100 stack
> frames allocated on the system stack.
>
> CONSing covers in general only the heap, not the stack.

Thanks for clearing this up. I interpreted the "bytes of memory
allocated" in terms of all memory, not just consing. If my memory serves
correctly in SBCL it said "bytes consed" or so.