Does anyone know whether returning and binding multiple values
conses? Or whether that is implementation dependent?
My function MOVE-ELEMENT seems to be consing 8 times (on average)
but I do not see where.
It is curious to me that MOVE-ELEMENT conses, but DELETE-ELEMENT
does not.
;; Destructively move an element from one list to another.
;; It always ends up on the beginning of the new list which is never
;; actually modified, but returned instead.
;; The from-list will be modified if the element was anywere except
;; the first element.
(defun move-element (element from-list to-list)
(declare (optimize speed
space
(compilation-speed 0)))
(multiple-value-bind (new-list cons-cell) (delete-element element
from-list)
(setf (cdr cons-cell) to-list)
(values new-list cons-cell)))
;; This function is similar to the DELETE function for lists.
;; returns a list which is either the CDR of the old list or the old
list
;; destructively modified to remove the cons cell whose CAR is EQ to
the
;; given element.
;; returns two values, the perhaps modified list and the cons cell
;; which has been "removed".
;; The calling function is then free to recycle the cons cell if he
likes.
(defun delete-element (element list)
(declare (optimize speed
space
(compilation-speed 0)))
(if (eq element (car list))
(values (cdr list) list)
(let ((ptr list))
(declare (cons ptr))
(loop while (not (eq element (cadr ptr)))
do (pop ptr))
(let ((cons-cell (cdr ptr)))
(declare (cons cons-cell))
(setf (cdr ptr) (cddr ptr))
(values list cons-cell)))))
Consed | Calls | Secs | Sec/Call | Bytes/C. | Name:
-----------------------------------------------------------------------
...
3,603,480 | 450,435 | 1.379 | 0.00000 | 8 |
VERILOG::MOVE-ELEMENT
...
0 | 450,435 | 0.059 | 0.00000 | 0 |
VERILOG::DELETE-ELEMENT
"Jimka" <·····@rdrop.com> writes:
> Does anyone know whether returning and binding multiple values
> conses? Or whether that is implementation dependent?
It is implementation dependent. In fact, I believe none of the CL
constructs have defined consing behavior.
> (defun move-element (element from-list to-list)
> (declare (optimize speed
> space
> (compilation-speed 0)))
> (multiple-value-bind (new-list cons-cell) (delete-element element
> from-list)
> (setf (cdr cons-cell) to-list)
> (values new-list cons-cell)))
I would not expect this to cons at all. First I'd study the
disassembly, then I'd ask the implementation vendor about this.
--
Frode Vatvedt Fjeld
Here is the disassembly. I must admid that i do not read
x86 assembly very well.
CL-USER> (disassemble 'VERILOG::MOVE-ELEMENT)
Warning:
Source file "/home/jimka/src/verilog/partition.lisp" has been
modified;
Using form offset instead of file index
5852FC20: .ENTRY VERILOG::MOVE-ELEMENT(element from-list to-list)
; (FUNCTION
; (T T ..))
38: POP DWORD PTR [EBP-8]
3B: LEA ESP, [EBP-32]
3E: CMP ECX, 12 ; [:NON-LOCAL-ENTRY]
41: JNE L2
43: MOV [EBP-12], ESI
46: MOV EBX, ESP ; No-arg-parsing entry
point
; [:NON-LOCAL-ENTRY]
48: SUB ESP, 12
4B: MOV EAX, [#x5852FC18] ; #<FDEFINITION object for
VERILOG::DELETE-ELEMENT>
51: MOV ECX, 8
56: MOV [EBX-4], EBP
59: MOV EBP, EBX
;;; [7] (DELETE-ELEMENT ELEMENT FROM-LIST)
5B: CALL DWORD PTR [EAX+5] ; [:CALL-SITE]
5E: JMP L0 ; [:UNKNOWN-RETURN]
60: MOV EDI, #x2800000B ; NIL
65: MOV EBX, ESP
67: L0: MOV ESP, EBX
;;; [8] (SETF (CDR CONS-CELL) TO-LIST)
69: CMP EDI, #x2800000B ; NIL
; [:BLOCK-START]
; [:BLOCK-START]
6F: JEQ L1
71: MOV EAX, [EBP-12] ; [:BLOCK-START]
; [:BLOCK-START]
74: MOV [EDI+1], EAX
77: MOV EBX, EBP ; [:BLOCK-START]
79: MOV ECX, 8
7E: MOV EBP, [EBP-4]
81: LEA ESP, [EBX-8]
84: MOV ESI, #x2800000B ; NIL
89: JMP DWORD PTR [EBX-8]
8C: L1: MOV EAX, [#x5852FC1C] ; 'CONS
; [:BLOCK-START]
92: BREAK 10 ; Error trap
94: BYTE #x05
95: BYTE #x21 ; OBJECT-NOT-TYPE-ERROR
96: BYTE #xFE, #xCE, #x01 ; EDI
99: BYTE #x0E ; EAX
9A: NOP
9B: NOP
9C: NOP
9D: NOP
9E: NOP
9F: NOP
A0: L2: BREAK 10 ; Error trap
A2: BYTE #x02
A3: BYTE #x19 ;
INVALID-ARGUMENT-COUNT-ERROR
A4: BYTE #x4D ; ECX
; No value
From: Edi Weitz
Subject: Re: ellusive consing with multiple-values
Date:
Message-ID: <uk6j75hg9.fsf@agharta.de>
On 31 Jul 2005 02:39:28 -0700, "Jimka" <·····@rdrop.com> wrote:
> Does anyone know whether returning and binding multiple values
> conses? Or whether that is implementation dependent?
>
> My function MOVE-ELEMENT seems to be consing 8 times (on average)
> but I do not see where.
Doesn't cons for me (LWW 4.4.5):
CL-USER 40 > (defun foo (i from to)
(loop for j from 1 below i do
(move-element j from to)))
FOO
CL-USER 41 > (compile 'foo)
FOO
NIL
NIL
CL-USER 42 > (let ((from (loop for i below 100000 collect i))
(to nil))
(time (foo 100000 from to)))
Timing the evaluation of (FOO 100000 FROM TO)
user time = 0.010
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes conses
0 Page faults
NIL
Maybe you've forgotten to compile your test code? It certainly conses
for me if I don't compile FOO.
Cheers,
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
I'm using cmucl 19a. And either i'm really confused or
it seems to be consing quite a lot.
I put a TIME call around the MOVE-ELEMENT call and
TIME says each call conses 16 times. Perhaps the
function calling mechanism is consing???
(defun foo ()
(let ((from (copy-list '(d a e c f b g)))
(to (copy-list '(x)))
(move (copy-list '(a b c d e f))))
(dolist (elt move)
(multiple-value-bind (x y)
(time (move-element elt from to))
(setf from x)
(setf to y)))))
And using the cmucl profile package.
(profile:profile foo move-element delete-element)
(profile:reset-time)
(foo)
(profile:report-time)
The TIME function thinks calling MOVE-ELEMENT conses
16 times, but PROFILE:REPORT-TIME thinks the function
itself conses 8 times. Does that mean that cmucl needs
to create 8 cons cells to call a multiple value function?
Here is the output:
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 18,598 CPU cycles
; 0 page faults and
; 16 bytes consed.
;
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 9,720 CPU cycles
; 0 page faults and
; 16 bytes consed.
;
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 8,943 CPU cycles
; 0 page faults and
; 16 bytes consed.
;
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 9,484 CPU cycles
; 0 page faults and
; 16 bytes consed.
;
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 9,135 CPU cycles
; 0 page faults and
; 16 bytes consed.
;
; Evaluation took:
; 0.0 seconds of real time
; 0.0 seconds of user run time
; 0.0 seconds of system run time
; 8,974 CPU cycles
; 0 page faults and
; 16 bytes consed.
;
; Byte Compiling Top-Level Form:
Consed | Calls | Secs | Sec/Call | Bytes/C. | Name:
-----------------------------------------------------------------------
35,408 | 1 | 0.010 | 0.01000 | 35,408 | FOO
0 | 6 | 0.000 | 0.00000 | 0 |
DELETE-ELEMENT
48 | 6 | 0.000 | 0.00000 | 8 |
MOVE-ELEMENT
-------------------------------------------------------------------
35,456 | 13 | 0.010 | | | Total
OOPS, i think i found the problem.
The PROFILE package is causing the consing.
If I turn off profiling, then TIME reports 0 bytes consed.
This is perhaps a case of Heisenberg Uncertainty Principle--
measuring a system always changes the result.
"Jimka" <·····@rdrop.com> writes:
> Does anyone know whether returning and binding multiple values
> conses? Or whether that is implementation dependent?
I think it's implementation dependant: I don't remember anything in
CLHS that prevents implementations to cons for multiple values.
But sane implementations try not to cons for multiple values.
> ;; This function is similar to the DELETE function for lists.
> ;; returns a list which is either the CDR of the old list or the old
> list
> ;; destructively modified to remove the cons cell whose CAR is EQ to
> the
> ;; given element.
> ;; returns two values, the perhaps modified list and the cons cell
> ;; which has been "removed".
> ;; The calling function is then free to recycle the cons cell if he
> likes.
> (defun delete-element (element list)
> (declare (optimize speed
> space
> (compilation-speed 0)))
> (if (eq element (car list))
> (values (cdr list) list)
> (let ((ptr list))
> (declare (cons ptr))
> (loop while (not (eq element (cadr ptr)))
> do (pop ptr))
> (let ((cons-cell (cdr ptr)))
> (declare (cons cons-cell))
> (setf (cdr ptr) (cddr ptr))
> (values list cons-cell)))))
It's quite different from DELETE: it loops infinitely when
(not (member element list :test (function eq))).
Don't try it on numbers!
--
"Specifications are for the weak and timid!"
yes, you are right in that it would loop forever. but my application
never calls the fuction unless it knows the element is actually in
the list. this is an optimization i've already made elsewhere in the
program.