Hi, all,
I'm working my way the Graham's _ANSI Common Lisp_. Exercise 3.3 says
Define a function that takes a list and returns a list indicating the
number of times eah (eql) element appears, sorted from most common element
to least common:
> (occurrences '(a b a d a c d c a))
((A . 4) (C . 2) (D . 2) (B . 1))
I got it to work without much trouble. I timed it, though, and for the
interpreted functions it conses anywhere from 8k to 76k; for the compiled
functions it almost always conses 0 bytes, though if I run it many times in a
row, it'll occasionally cons 6-8k. (And eventually it'll GC, so I know
something, somewhere, allocates memory. :)
So, why "0 bytes consed"? I can *see* the cons calls! :) What've I missed?
Thanks!
-- Larry
Session follows:
Using CMUCL 18c (safe version) under Linux:
* (defun occurrences (lst)
(sort (occurrences-aux lst nil)
#'>
:key #'cdr))
OCCURRENCES
* (defun occurrences-aux (lst assoc)
(if lst
(occurrences-aux (remove (car lst) lst)
(cons (cons (car lst)
(count-em (car lst) lst))
assoc))
assoc))
OCCURRENCES-AUX
* (defun count-em (x lst)
(if (null lst)
0
(if (eql x (car lst))
(1+ (count-em x (cdr lst)))
(count-em x (cdr lst)))))
COUNT-EM
* (setq lst '(a b a d a c d c a))
* (time (occurrences lst))
Compiling LAMBDA NIL:
Compiling Top-Level Form:
Evaluation took:
0.02 seconds of real time
0.01 seconds of user run time
0.0 seconds of system run time
0 page faults and
73568 bytes consed.
((A . 4) (C . 2) (D . 2) (B . 1))
* (mapcar #'compile '(count-em occurrences occurrences-aux))
[...]
(COUNT-EM OCCURRENCES OCCURRENCES-AUX)
* (time (occurrences lst))
Compiling LAMBDA NIL:
Compiling Top-Level Form:
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
((A . 4) (C . 2) (D . 2) (B . 1))
Larry Clapp wrote:
>
>
> > (occurrences '(a b a d a c d c a))
> ((A . 4) (C . 2) (D . 2) (B . 1))
>
> I got it to work without much trouble. I timed it, though, and for the
> interpreted functions it conses anywhere from 8k to 76k; for the compiled
> functions it almost always conses 0 bytes, ...
>
> So, why "0 bytes consed"? I can *see* the cons calls! :) What've I missed?
>
Nothing! You spotted the diff between interpreted and compiled, there ya
go.
If you know "C", you probably know literals such as "Hello, world." are
allocated once and stuffed somewhere during compilation, then referenced
by pointer at runtime. If you perform destructive operations on such
pointers you are whacking the binary image. etc etc.
Likewise in all regards with a quoted list: quoted lists are allocated
once by the compiler and reused thereafter, so (a) the consing happens
at compile time and (b) don't change them at run time.
--
kenny tilton
clinisys, inc
---------------------------------------------------------------
"Be the ball...be the ball...you're not being the ball, Danny."
- Ty, Caddy Shack
In article <·················@nyc.rr.com>,
Kenny Tilton <·······@nyc.rr.com> wrote:
>> So, why "0 bytes consed"? I can *see* the cons calls! :) What've I missed?
>Nothing! You spotted the diff between interpreted and compiled, there ya
>go.
...
>Likewise in all regards with a quoted list: quoted lists are allocated
>once by the compiler and reused thereafter, so (a) the consing happens
>at compile time and (b) don't change them at run time.
But he's calling CONS in his function, not just returning quoted lists.
I'm as confused as the OP.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
* Barry Margolin wrote:
> But he's calling CONS in his function, not just returning quoted lists.
Which CMUCL is he using? I'm fairly sure that at least some of them
reported consing fairly bogusly.
--tim
Barry Margolin wrote:
>
> In article <·················@nyc.rr.com>,
> Kenny Tilton <·······@nyc.rr.com> wrote:
> >> So, why "0 bytes consed"? I can *see* the cons calls! :) What've I missed?
>
> >Nothing! You spotted the diff between interpreted and compiled, there ya
> >go.
> ...
> But he's calling CONS in his function, not just returning quoted lists.
Oh. Never mind.
:)
--
kenny tilton
clinisys, inc
---------------------------------------------------------------
"Be the ball...be the ball...you're not being the ball, Danny."
- Ty, Caddy Shack
Larry Clapp <·····@theclapp.org> writes:
> > (occurrences '(a b a d a c d c a))
> ((A . 4) (C . 2) (D . 2) (B . 1))
>I got it to work without much trouble. I timed it, though, and for the
>interpreted functions it conses anywhere from 8k to 76k; for the compiled
>functions it almost always conses 0 bytes, though if I run it many times in a
>row, it'll occasionally cons 6-8k. (And eventually it'll GC, so I know
>something, somewhere, allocates memory. :)
>So, why "0 bytes consed"? I can *see* the cons calls! :) What've I missed?
The function that get the currently allocated number of bytes (and is
used by time) does not immediately reflect every small allocation in
CMUCL with the generational GC for x86. You get it later after more
allocation.
I have fixes for that, but they come in an unsubmittably ugly
space-profiling package. Working on it.
Martin
--
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Martin Cracauer <········@bik-gmbh.de> http://www.bik-gmbh.de/~cracauer/
FreeBSD - where you want to go. Today. http://www.freebsd.org/