From Henrik Motakef -
> > For one thing, the C executable created by MCL would likely not run
> > correctly on Apple's new operating system. (a Unix variant)
>
> I stongly doubt that, it seems to me that basically all MCL people are
> on OS X nowadays. But you might want to hear that from one of them.
Okay, I did not realize that MCL could do that. My logic was that MCL
was designed long before Apple's OS X came out, so I thought that some
necessary critical things would be "left out" of MCL, things that might
be necessary for the C executable to run at all in OS X.
From Henrik Motakef -
> > I don't have the confidence in the "automatic" convert-to-C features
> > that some CL implementations have; I get the impression that they don't
> > do all that great a job.
>
> Why?
Oh, because I had the idea that the more exotic CL stuff like closures
and run-time-evaluation could not be handled.
It was pointed out to me that the automatic convert-to-C really
converts to machine code, not C, so I was wrong in my above assumption.
Anything that is "do-able" can be done in machine code :)
Mark-
Mark Conrad <······@iam.invalid> wrote in message news:<·························@iam.invalid>...
> From Henrik Motakef -
> > > I don't have the confidence in the "automatic" convert-to-C features
> > > that some CL implementations have; I get the impression that they don't
> > > do all that great a job.
> >
> > Why?
>
> Oh, because I had the idea that the more exotic CL stuff like closures
> and run-time-evaluation could not be handled.
There are Lisp implementations that compile to C; notably Kyoto Common
Lisp and its derivatives like GCL an ECL. But this is not really
portable ANSI C, and it's gobbledygook that no human C programmer
could write any significant amount of.
You could have closures, but then the references to the bindings would
not be normal C variable references. You wouldn't recognize the
construct as a closure; only if you were very famiiliar with the
translator you could point to the code and recognize the pattern: ``oh
yeah, that incomprehensible crap looks like it's in that space of
generated code that corresponds to closures.'' And from there you
could drill down into it and understand some microscopic piece: ''Aha,
this cryptic expression is storing a value to the third binding in the
closure which, thanks to having access to the original Lisp source, we
can guess to be the variable x''.
In article <····························@posting.google.com>, Kaz
Kylheku <···@ashi.footprints.net> wrote:
> There are Lisp implementations that compile to C ...<snipped>...
Excuse me again (everyone) - I really got these threads all messed up.
When I started these threads, I thought that the Lisp compilers
converted the Lisp source-code to C - - - that was wrong, as someone
here pointed out to me.
The Lisp compiler that makes the standalone executable creates
machine-code, I am told, not C code.
Thanks for pointing that out.
As _you_ pointed out, Kaz, there are also CL implementations that
convert the Lisp source-code to "incomprehensible" C code, code that
looks entirely different than regular C code.
I got all mixed up as to what was converted to what, in light of the
above statements<g>
I learned a lot from everyone here, and I wanna thank everyone for
helping me out.
Did I answer everyone's questions as to what I am trying to accomplish?
I hope so. Lemme know if I forgot to reply to any questions.
Basically, I like to use CL because I appreciate the extreme
flexibility of Lisp compared to C for example; until just recently, I
thought it was necessary to 'Create-in-CL' then to 'Re-create the CL
source code in C' (recreate from scratch, using the Lisp source code as
a guide)
Not necessary, it was pointed out to me.
Now for one last question, and then I will retreat into my cave.
Is there anything that C is 'better at' than Lisp? <MCL Lisp>
(other than C being able to work on practically every hardware platform)
Be truthful now, fellas <g>
Mark-
From: Robert Amble
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <87he95bx0v.fsf@chartermi.net>
Mark Conrad <······@iam.invalid> writes:
> In article <····························@posting.google.com>, Kaz
> Kylheku <···@ashi.footprints.net> wrote:
>
> > There are Lisp implementations that compile to C ...<snipped>...
>
> Excuse me again (everyone) - I really got these threads all messed up.
>
> When I started these threads, I thought that the Lisp compilers
> converted the Lisp source-code to C - - - that was wrong, as someone
> here pointed out to me.
>
> The Lisp compiler that makes the standalone executable creates
> machine-code, I am told, not C code.
>
> Thanks for pointing that out.
>
> As _you_ pointed out, Kaz, there are also CL implementations that
> convert the Lisp source-code to "incomprehensible" C code, code that
> looks entirely different than regular C code.
>
> I got all mixed up as to what was converted to what, in light of the
> above statements<g>
>
> I learned a lot from everyone here, and I wanna thank everyone for
> helping me out.
>
> Did I answer everyone's questions as to what I am trying to accomplish?
>
> I hope so. Lemme know if I forgot to reply to any questions.
>
> Basically, I like to use CL because I appreciate the extreme
> flexibility of Lisp compared to C for example; until just recently, I
> thought it was necessary to 'Create-in-CL' then to 'Re-create the CL
> source code in C' (recreate from scratch, using the Lisp source code as
> a guide)
>
> Not necessary, it was pointed out to me.
>
> Now for one last question, and then I will retreat into my cave.
>
> Is there anything that C is 'better at' than Lisp? <MCL Lisp>
> (other than C being able to work on practically every hardware platform)
>
> Be truthful now, fellas <g>
>
> Mark-
Well, as someone who worked with C/C++ and MCL on the Mac, I would say writing
device drivers would be better done in C. Since MCL has full access to the Mac
toolbox (if needed), there is little reason to resort to C. (Ok, you can write
a 'hello world' app that is smaller in C than in MCL).
Happy Hacking,
rca
From: Kenny Tilton
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <3E962237.9000803@nyc.rr.com>
Mark Conrad wrote:
> Is there anything that C is 'better at' than Lisp? <MCL Lisp>
> (other than C being able to work on practically every hardware platform)
1. calling C, but once you learn the FFI (which is kinda like learning a
very small API) it's a little easier in Lisp because you do not sit
around worrying about types and pointers and whatever hassles remain can
be handle with some slick macros... ok, i take it back, calling C is
easier with Lisp. Indeed, a nasty API like OpenGL presents many
opportunities for Lisp macros to simplify my code and keep me from
shooting myself in the foot.
2. does "trashing the OS so you can spend a few minutes rebooting"
count? I never lose NT when doing Lisp, but when talking to C...
> Be truthful now, fellas <g>
Lispniks are not threatened by C, it is C that cannot handle the truth.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Everything is a cell." -- Alan Kay
Mark Conrad <······@iam.invalid> writes:
> Is there anything that C is 'better at' than Lisp?
Raw speed. But it is often expensive (in terms of human resources) to
get there. Lisp programs can also be very fast, but there seems to be
always a very last bit of performance hit coming from things like
garbage collection.
> (other than C being able to work on practically every hardware platform)
But I guess the same is true for Lisp. Maybe a lack of implementations
here and there, but nothing of principle.
Mario.
From: Joe Marshall
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <ptnseqmf.fsf@ccs.neu.edu>
Mario S. Mommer <········@yahoo.com> writes:
> Mark Conrad <······@iam.invalid> writes:
> > Is there anything that C is 'better at' than Lisp?
>
> Raw speed.
Shorter time to failure.
From: Florian Weimer
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <877ka0oj9t.fsf@deneb.enyo.de>
Mario S. Mommer <········@yahoo.com> writes:
> Mark Conrad <······@iam.invalid> writes:
>> Is there anything that C is 'better at' than Lisp?
>
> Raw speed.
Only if you carefully tune the memory management, which is
error-prone.
> But it is often expensive (in terms of human resources) to
> get there. Lisp programs can also be very fast, but there seems to be
> always a very last bit of performance hit coming from things like
> garbage collection.
Garbage collection is cheap compared to the safe approach to memory
management a few C programmers choose.
Florian Weimer <··@deneb.enyo.de> wrote in message news:<··············@deneb.enyo.de>...
> Mario S. Mommer <········@yahoo.com> writes:
>
> > Mark Conrad <······@iam.invalid> writes:
> >> Is there anything that C is 'better at' than Lisp?
> >
> > Raw speed.
>
> Only if you carefully tune the memory management, which is
> error-prone.
Here is the rub. Given a blank computer, and some basic tools like a C
cross-compiler for that system's CPU, an assembler, and a way to
transfer the image to that system so that it can be cold-booted, you
can probably make some working control program for that computer more
quickly in C than you would in Lisp. Your language of choice needs
next to no run-time support.
So you write a simple interrupt service routine, glorify it a little
bit with some C, and find that it runs. You push some button connected
to the board, a C function is called, and lights up some LED. Great!
From there, it's all uphill. You eventually end up writing all of the
run-time support that the Lisp language would need, in some ad-hoc
way. Dynamic memory management, but probably with no garbage
collection. Linked lists, vector abstractions, etc.
By the time you have something that can be called an operating system,
you also have an ad-hoc, ill-specified, bug-ridden, slow half of
Common Lisp in there.
> > But it is often expensive (in terms of human resources) to
> > get there. Lisp programs can also be very fast, but there seems to be
> > always a very last bit of performance hit coming from things like
> > garbage collection.
>
> Garbage collection is cheap compared to the safe approach to memory
> management a few C programmers choose.
One safe approach is this: rather than compute the lifetime of a
single object, you make a copy of that object. The problem is then
divided and somewhat conquered; because you now have two lifetime
computations, each of which is simpler. If every place in the C
program that deals with some object has its own copy, it's easy to see
what the proper lifetime of each one is.
Copying is quite expensive.
If you wrote the layers of a TCP/IP protocol stack that way, for
instance--copying the packet data when transferring it between
layers--you'd be stuck at 10BaseT speeds on a gigabit Ethernet, if you
were lucky, even given a gigahertz CPU.
In article <··············@cupid.igpm.rwth-aachen.de>, Mario S. Mommer
<········@yahoo.com> wrote:
> > Is there anything that C is 'better at' than Lisp?
>
> Raw speed. But it is often expensive (in terms of human resources) to
> get there. Lisp programs can also be very fast, but there seems to be
> always a very last bit of performance hit coming from things like
> garbage collection.
Uh, that brings up a question. Can CL garbage collection be somehow
"controlled" manually, so that the performance hit does not occur.
I know, it is a dumb question, but I can get by with it because I am a
newbie.<g>
Mark-
From: Greg Menke
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <m33ckn4reo.fsf@europa.pienet>
Mark Conrad <······@iam.invalid> writes:
> In article <··············@cupid.igpm.rwth-aachen.de>, Mario S. Mommer
> <········@yahoo.com> wrote:
>
> > > Is there anything that C is 'better at' than Lisp?
> >
> > Raw speed. But it is often expensive (in terms of human resources) to
> > get there. Lisp programs can also be very fast, but there seems to be
> > always a very last bit of performance hit coming from things like
> > garbage collection.
>
>
> Uh, that brings up a question. Can CL garbage collection be somehow
> "controlled" manually, so that the performance hit does not occur.
>
> I know, it is a dumb question, but I can get by with it because I am a
> newbie.<g>
It depends on the implementation. Manual gc control, or even
adjustment of whatever parameters are available is something to
consider when there are particular performance requirements that your
program isn't meeting. On the other hand, the impact of gc is very
dependent on how your code is written- in general, if you don't cons a
lot, the gc overhead will be lower.
Gregm
Greg Menke <··········@toadmail.com> writes:
> Mark Conrad <······@iam.invalid> writes:
>
> > In article <··············@cupid.igpm.rwth-aachen.de>, Mario S. Mommer
> > <········@yahoo.com> wrote:
> >
> > > > Is there anything that C is 'better at' than Lisp?
> > >
> > > Raw speed. But it is often expensive (in terms of human resources) to
> > > get there. Lisp programs can also be very fast, but there seems to be
> > > always a very last bit of performance hit coming from things like
> > > garbage collection.
> >
> >
> > Uh, that brings up a question. Can CL garbage collection be somehow
> > "controlled" manually, so that the performance hit does not occur.
> >
I wanted to point out my own recent experiences on this subject,
because I feel they're directly relevant. I recently wrote a
medium-sized (maybe 1000 LOC) system in CL. This program was entirely
a number crunching program --- it reads in data from a file, performs
a bunch of math of varying kinds, and spits out more data. I'd heard
many people on the newsgroup say that CL could be made fast with
careful tuning, and I wanted to test this. I wrote the program using
CMUCL.
Key points.
1. The program was much easier and more enjoyable to write than it
would have been in C.
2. The initial version was SLOW, roughly 50x-100x times slower than
the same program written in C.
3. The problem was NOT garbage collection per se, which is fast.
Instead, one problem was that the "natural" (or perhaps "naive")
approach to writing CL leads to consing up hundreds of times as
much memory as the corresponding C program uses (because it's easy
to generate lots of copies of things). Fixing this essentially
involved reusing lots of arrays --- I stored them inside memoized
functions that allocate them, which is in this case just one thin
layer of abstraction above storing them in special (global)
values. This corresponds to the common, but not overly scalable,
C/C++ strategy of allocating the vectors I need, resuing them
extensively, and NEVER deallocating them. To sum up this point, I
think that if I'm consing a reasonable amount, garbage collection
is plenty fast enough. The real problem is allocating was too
much memory in the first place, not GC.
4. Other reason(s) that the program was slow essentially stemmed
from two different issues related to types. The first (and
easier) was simply type declarations within a function, so that
generic arithmetic could be avoided. The second was realizing
that although CL encourages one to program in a functional style
and write a large number of very small functions, that whenever
you write a small function that takes a double-float argument and
returns a double-float value, that you're going to lose because
the system has to "box" the argument and the "return" value, and
that this can easily make your whole program 10x-20x times slower
if you do it in inner loops. The key to avoiding this is inlining
(or perhaps macros/compiler macros).
5. The final version seemed to be within a factor of 2 of the
equivalent program in C, which was fast enough for my purposes.
So I tentatively concluded that at least on CMUCL, if you take the
time to make careful type and inlining declarations and avoid
excessive consing, you can get a program that's quite fast. I
don't think I could make the program much faster without a LOT
more work.
6. It took quite a while (and was not easy) to learn how to make CL
programs fast. Now that I've learned these things, I think it
will be much easier to optimize my next program.
I hope this "case study" is useful to others considering the issue of
writing fast CL programs.
Cheers,
rif
"rif" <···@mit.edu> wrote in message
····················@five-percent-nation.mit.edu...
> I wanted to point out my own recent experiences on this subject,
> because I feel they're directly relevant. I recently wrote a
> medium-sized (maybe 1000 LOC) system in CL. This program was entirely
> a number crunching program --- it reads in data from a file, performs
> a bunch of math of varying kinds, and spits out more data. I'd heard
> many people on the newsgroup say that CL could be made fast with
> careful tuning, and I wanted to test this. I wrote the program using
> CMUCL.
>
> Key points.
>
> 1. The program was much easier and more enjoyable to write than it
> would have been in C.
>
> 2. The initial version was SLOW, roughly 50x-100x times slower than
> the same program written in C.
>
> *snip* tuning tips
>
> 5. The final version seemed to be within a factor of 2 of the
> equivalent program in C, which was fast enough for my purposes.
>
> *snip*
>
> 6. It took quite a while (and was not easy) to learn how to make CL
> programs fast. Now that I've learned these things, I think it
> will be much easier to optimize my next program.
>
> I hope this "case study" is useful to others considering the issue of
> writing fast CL programs.
I don't know how "important" this program you wrote was, or what kind of
time pressure you were under.
So, here are the real questions.
Considering you, ideally, went through the "make it right, make it fast"
process, in the end was the program done any faster, or with more
capability, than if you had done it initially in C?
Not counting any personal gain you got out of this, which no doubt has its
own benefits, but considering all of the time spent on the task, to end up
with a program that is half as fast, was the end result a better enough
program to justify the cost in performance? How is it better?
Given that you consider the C version to be the benchmark in terms of
performance, how long would it have taken you to write the "fast" C version
in comparison with what you had to do with the CL version? The assumption
there is that it would take more time to get the C version "right", but less
time to get it "fast".
Finally, now that you know the tricks, techniques and idioms that work for
you in improving performance on this class of programs, how much less time
would it take to create a new program using CL that would get to roughly
half the performance of the C version?
Basically, now that you've gone through this process, was the CL version
"worth it" for the first program considering time spent and final result,
and now that you've made the knowledge gain, is CL going to be worth it in a
future program?
Also, do you think you could write up what steps you took to speed up your
CL program, what idioms your relied on? How different was the original slow
version compared to the final fast version? How dramatic and invasive were
the changes to the source code and how much risk was there to "breaking
working code", thus jeapordizing "getting it right", in order to make it
faster?
Regards,
Will Hartung
(·····@msoft.com)
"Will Hartung" <·····@msoft.com> writes:
> I don't know how "important" this program you wrote was, or what kind of
> time pressure you were under.
>
> So, here are the real questions.
>
> Considering you, ideally, went through the "make it right, make it fast"
> process, in the end was the program done any faster, or with more
> capability, than if you had done it initially in C?
>
> Not counting any personal gain you got out of this, which no doubt has its
> own benefits, but considering all of the time spent on the task, to end up
> with a program that is half as fast, was the end result a better enough
> program to justify the cost in performance? How is it better?
>
> Given that you consider the C version to be the benchmark in terms of
> performance, how long would it have taken you to write the "fast" C version
> in comparison with what you had to do with the CL version? The assumption
> there is that it would take more time to get the C version "right", but less
> time to get it "fast".
>
> Finally, now that you know the tricks, techniques and idioms that work for
> you in improving performance on this class of programs, how much less time
> would it take to create a new program using CL that would get to roughly
> half the performance of the C version?
>
> Basically, now that you've gone through this process, was the CL version
> "worth it" for the first program considering time spent and final result,
> and now that you've made the knowledge gain, is CL going to be worth it in a
> future program?
>
> Also, do you think you could write up what steps you took to speed up your
> CL program, what idioms your relied on? How different was the original slow
> version compared to the final fast version? How dramatic and invasive were
> the changes to the source code and how much risk was there to "breaking
> working code", thus jeapordizing "getting it right", in order to make it
> faster?
To write this particular program, I spent substantially more time
writing it than I would have in C or C++ to get a program twice as
fast. But I've been programming in C/C++ for ten years, and this was
my first attempt to make a decent-sized fast program in CL. My sense
is that the CL program is substantially shorter than the same program
in C, and that right now, having put in the time and effort to learn
how to make my CL fast, given another task in roughly the same
universe of tasks, I could write the CL program much faster than the
same C program (assuming I'm willing to accept a program that's half
as fast).
This is great for me, because the biggest constraint on me is not the
runtime of my programs (within a factor of about 2), but my own time.
(Aside: The computer I just got is more than twice as fast the one I
had last year.) My sense is that the large majority of time I spent
doing this program was learning skills and writing macros that will
directly transfer to future programs.
A prime example is the use of the map idiom. My code often needs to
operate on multiple arrays of typed (generally double-float) elements.
I find it much simpler and more concise to write in terms of map than
in terms of for loops. Of course, if I say
(map 'vector #'+ v1 v2)
The problem is that the result (all observations are under CMUCL) will
have array-element-type T, even if v1 and v2 are both declared as
arrays of double-floats. Furthermore, this will always cons a
new array, which is often unnecessary. So I wrote some macros to
handle these kinds of situations, which can be used (and already have
been) in other programs I'm writing. For instance, I can now say:
(df-vmap #'+ :in-place v1 v2)
This will automatically expand into code which does the type
declarations for me, and stores the result into v1. So with very
little change in the code, I have a version of "map" that does my type
declarations for me and conses nothing. (Of course, consing up a new
vector every time is in some sense "safer" --- now it's my
responsibility to make sure I'm not overwriting something I need).
(df-vmap is built on top of a more generic vmap, where you specify the
"default type" of each argument. You can also override the types, so
you could have a specific argument to df-vmap be a vector of fixnum's,
for instance.)
So I spent a substantial amount of time figuring out that what kinds
of type declarations would be needed, figuring out that inlining was
important, then figuring out that I could avoid doing a lot of type
declarations by writing the "vmap" language, then actually
implementing it. Once I'd done that, it was very straightforward to
replace a bunch of instances of map in my program with df-vmap, and
that gave me most of the speedup, allowing me to simultaneously avoid
consing and have my type declarations done. Now all that's done, and
I can enjoy the fruits of my labors.
Other features of CL that were extremely useful were:
1. The ability to get different sorts of desirable behavior based on
compilation settings --- high safety and high debug makes it easy
to find problems (array bounds overflows, type errors), and then
when it's working, all I have to do is change the compilation
settings to get something that works. I find this much simpler
than (for instance) using debugging mallocs on a misbehaving C
program.
2. Closures and hash tables. Closures just make it so natural to
have functions which take functional arguments, which often leads
to cleaner designs. Having hash tables built into the language
makes many kinds of bookkeeping tasks very simple.
If my only goal had been to get this particular program going as fast
as possible, I'd have been better off writing in C. Going forward, I
fully expect that I'll be able to write new programs that are half as
fast as the corresponding C programs in substantially less time and
with substantially less frustration. We'll see how it pans out.
Cheers,
rif
From: Paul F. Dietz
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <3aadnaT7OKKuKgSjXTWcqw@dls.net>
rif wrote:
> A prime example is the use of the map idiom. My code often needs to
> operate on multiple arrays of typed (generally double-float) elements.
> I find it much simpler and more concise to write in terms of map than
> in terms of for loops. Of course, if I say
>
> (map 'vector #'+ v1 v2)
>
> The problem is that the result (all observations are under CMUCL) will
> have array-element-type T, even if v1 and v2 are both declared as
> arrays of double-floats. Furthermore, this will always cons a
> new array, which is often unnecessary. So I wrote some macros to
> handle these kinds of situations, which can be used (and already have
> been) in other programs I'm writing. For instance, I can now say:
>
> (df-vmap #'+ :in-place v1 v2)
Did you consider using MAP-INTO?
Paul
> Did you consider using MAP-INTO?
>
I hadn't heard of it. Shows what I get for not studying carefully
enough. That still happens to me a lot, actually. Thanks. My
approach still makes some things easier I think (automating certain
kinds of type declarations), but map-into probably could've done a lot
of that for me.
rif
rif <···@mit.edu> writes:
>> Did you consider using MAP-INTO?
> I hadn't heard of it. Shows what I get for not studying carefully
> enough. That still happens to me a lot, actually.
And here we may have another point where C is better than CL:
In CL, I too often discover clever ways to do stuff on my own, only to
learn that something like it is already defined in the standard. This
is both enlightening and frustrating.
I haven't had this kind of frustration too often when using C (or
other languages, to varying degrees). So it is clear that the lack of
clever ways to do stuff in the C standard is better than CLs
usefullness, scince C leaves more room for programmer pride when some
code actually runs, does what it is supposed to, and even qualifies as
elegant. Proud programmers are more likely to become language
advocates.
Regards
Henrik, only half joking
Henrik Motakef <··············@web.de> writes:
> rif <···@mit.edu> writes:
>
> >> Did you consider using MAP-INTO?
> > I hadn't heard of it. Shows what I get for not studying carefully
> > enough. That still happens to me a lot, actually.
>
> And here we may have another point where C is better than CL:
>
> In CL, I too often discover clever ways to do stuff on my own, only to
> learn that something like it is already defined in the standard. This
> is both enlightening and frustrating.
>
> I haven't had this kind of frustration too often when using C (or
> other languages, to varying degrees). So it is clear that the lack of
> clever ways to do stuff in the C standard is better than CLs
> usefullness, scince C leaves more room for programmer pride when some
> code actually runs, does what it is supposed to, and even qualifies as
> elegant. Proud programmers are more likely to become language
> advocates.
>
> Regards
> Henrik, only half joking
Right. In retrospect, I'd probably still have done it my way, rather
than using map-into, which does maybe 2/3 of what I want. But it's
still embarrassing to realize that map-into was sitting there the
whole time.
rif
rif <···@mit.edu> writes:
>> Did you consider using MAP-INTO?
>
> I hadn't heard of it. Shows what I get for not studying carefully
> enough. That still happens to me a lot, actually. Thanks. My
> approach still makes some things easier I think (automating certain
> kinds of type declarations), but map-into probably could've done a lot
> of that for me.
Well, note also that compilers can optimize calls to map-into based on
their own knowledge.
I had highly brittle experimental support in SBCL for (a) x86's SSE
and (b) using it automatically in suitable MAP-INTO calls, so that
calls like
(map-into a #'+ b c)
under suitable compilation policy and type declarations would compile
into quadword adds. I never really polished it because I lack the
hardware to run it on, but it's retrievable and could be made to work.
Christophe
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
In article <···············@five-percent-nation.mit.edu>,
rif <···@mit.edu> wrote:
> > Did you consider using MAP-INTO?
>
> I hadn't heard of it. Shows what I get for not studying carefully
> enough. That still happens to me a lot, actually. Thanks. My
> approach still makes some things easier I think (automating certain
> kinds of type declarations), but map-into probably could've done a lot
> of that for me.
I can't get MAP-INTO to not cons a ton in CMUCL on x86.
(defparameter *a* (make-array 1048576
:element-type 'double-float
:initial-element 1.0d0))
(defparameter *b* (make-array 1048576
:element-type 'double-float
:initial-element 1.0d0))
(defun vector-+-map-into (x y)
(declare (optimize (speed 3) (safety 0) (debug 0))
(type (simple-array double-float) x y))
(map-into x #'+ x y)
(values (aref x 0) (aref y 0)))
(defun vector-+-loop (x y)
(declare (optimize (speed 3) (safety 0) (debug 0))
(type (simple-array double-float) x y))
(loop for i from 0 to (1- (length x))
do (setf (aref x i) (+ (aref x i) (aref y i))))
(values (aref x 0) (aref y 0)))
This compiles with no notes or warnings.
* (time (vector-+-map-into *a* *b*))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 1.44 seconds of real time
; 0.11 seconds of user run time
; 1.31 seconds of system run time
; [Run times include 0.14 seconds GC run time]
; 3 page faults and
; 92,293,080 bytes consed.
;
2.0d0
1.0d0
;;;; Quit, restart lisp, reload
* (time (vector-+-loop *a* *b*))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.03 seconds of real time
; 0.03 seconds of user run time
; 0.0 seconds of system run time
; 0 page faults and
; 32 bytes consed.
;
2.0d0
1.0d0
Does anybody know how to get MAP-INTO to not cons on CMUCL? It would seem
that you're stuck using custom map macros otherwise if you want speed.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
>>>>> "Brian" == Brian Downing <···········@lavos.net> writes:
[snip]
Brian> Does anybody know how to get MAP-INTO to not cons on CMUCL? It would seem
Don't use map-into? Hack the definition of map-into in CMUCL?
:-)
Looking at the code, it seems that map-into hasn't been optimized
nearly as much as some of the other sequence functions.
Patches welcome!
Ray
From: Alexey Dejneka
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <m3he8mcwyc.fsf@comail.ru>
Raymond Toy <···@rtp.ericsson.se> writes:
> >>>>> "Brian" == Brian Downing <···········@lavos.net> writes:
>
> [snip]
>
> Brian> Does anybody know how to get MAP-INTO to not cons on CMUCL? It would seem
>
> Don't use map-into? Hack the definition of map-into in CMUCL?
Use latest SBCL from CVS? (It is slightly slower than LOOP, but it is
not hard to fix.)
--
Regards,
Alexey Dejneka
Alexey Dejneka wrote:
> Raymond Toy <···@rtp.ericsson.se> writes:
>
>
>>>>>>>"Brian" == Brian Downing <···········@lavos.net> writes:
>>
>>[snip]
>>
>> Brian> Does anybody know how to get MAP-INTO to not cons on CMUCL? It would seem
>>
>>Don't use map-into? Hack the definition of map-into in CMUCL?
>
>
> Use latest SBCL from CVS? (It is slightly slower than LOOP, but it is
> not hard to fix.)
>
Or series:
(defun vector-+-series (x y)
(declare (optimize (speed 3) (safety 0) (debug 0))
(type (simple-array double-float (*)) x y))
(iterate ((x1 (scan '(simple-array double-float (*)) x))
(y1 (scan '(simple-array double-float (*)) y))
(i (scan-range :type 'fixnum)))
(setf (aref x i) (+ x1 y1)))
(values (aref x 0) (aref y 0)))
On my box, I get
; Evaluation took:
; 0.12 seconds of real time
; 0.09 seconds of user run time
; 0.0 seconds of system run time
; 106,021,975 CPU cycles
; 0 page faults and
; 96 bytes consed.
versus the loop version which gets
; Evaluation took:
; 0.03 seconds of real time
; 0.03 seconds of user run time
; 0.0 seconds of system run time
; 0 page faults and
; 32 bytes consed.
Not too bad.
Ray
From: Alexey Dejneka
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <m31xzoe7rw.fsf@comail.ru>
Raymond Toy <····@earthlink.net> writes:
> (defun vector-+-series (x y)
> (declare (optimize (speed 3) (safety 0) (debug 0))
> (type (simple-array double-float (*)) x y))
> (iterate ((x1 (scan '(simple-array double-float (*)) x))
> (y1 (scan '(simple-array double-float (*)) y))
> (i (scan-range :type 'fixnum)))
> (setf (aref x i) (+ x1 y1)))
> (values (aref x 0) (aref y 0)))
Nice thing!
> On my box, I get
>
> ; Evaluation took:
> ; 0.12 seconds of real time
> ; 0.09 seconds of user run time
> ; 0.0 seconds of system run time
> ; 106,021,975 CPU cycles
> ; 0 page faults and
> ; 96 bytes consed.
>
> versus the loop version which gets
> ; Evaluation took:
> ; 0.03 seconds of real time
> ; 0.03 seconds of user run time
> ; 0.0 seconds of system run time
> ; 0 page faults and
> ; 32 bytes consed.
>
> Not too bad.
What is "the loop version"? Those using one index for all three
vectors (and thus doing different thing)? On my machine:
* (defun vector-+-series (x y)
(declare (optimize (speed 3) (safety 0) (debug 0))
(type (simple-array double-float (*)) x y))
(iterate ((x1 (scan '(vector double-float) x))
(y1 (scan '(vector double-float) y))
(i (scan-range :type 'fixnum)))
(setf (aref x i) (+ x1 y1)))
(values (aref x 0) (aref y 0)))
; in: LAMBDA NIL
; (VALUES (AREF X 0) (AREF Y 0))
;
; note: doing float to pointer coercion (cost 13) to "<return value>"
; compilation unit finished
; printed 2 notes
VECTOR-+-SERIES
* (defun vector-+-loop (x y)
(declare (optimize (speed 3) (safety 0) (debug 0))
(type (simple-array double-float (*)) x y))
(loop for x1 double-float across x
and y1 double-float across y
and i fixnum from 0
do (setf (aref x i) (+ x1 y1)))
(values (aref x 0) (aref y 0)))
; in: LAMBDA NIL
; (VALUES (AREF X 0) (AREF Y 0))
;
; note: doing float to pointer coercion (cost 13) to "<return value>"
; compilation unit finished
; printed 2 notes
VECTOR-+-LOOP
* (time (vector-+-series *a* *b*))
Evaluation took:
0.164 seconds of real time
0.16 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
2.0d0
1.0d0
* (time (vector-+-loop *a* *b*))
Evaluation took:
0.175 seconds of real time
0.18 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
3.0d0
1.0d0
* (time (vector-+-loop *a* *b*))
Evaluation took:
0.179 seconds of real time
0.17 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
4.0d0
1.0d0
* (time (vector-+-series *a* *b*))
Evaluation took:
0.165 seconds of real time
0.16 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
5.0d0
1.0d0
BTW, does an implementation exist, allowing to write just (SCAN
'VECTOR X) above without performance loss?
--
Regards,
Alexey Dejneka
Alexey Dejneka wrote:
> Raymond Toy <····@earthlink.net> writes:
>
>
>>(defun vector-+-series (x y)
>> (declare (optimize (speed 3) (safety 0) (debug 0))
>> (type (simple-array double-float (*)) x y))
>> (iterate ((x1 (scan '(simple-array double-float (*)) x))
>> (y1 (scan '(simple-array double-float (*)) y))
>> (i (scan-range :type 'fixnum)))
>> (setf (aref x i) (+ x1 y1)))
>> (values (aref x 0) (aref y 0)))
>
>
> Nice thing!
>
>
>>On my box, I get
>>
>>; Evaluation took:
>>; 0.12 seconds of real time
>>; 0.09 seconds of user run time
>>; 0.0 seconds of system run time
>>; 106,021,975 CPU cycles
>>; 0 page faults and
>>; 96 bytes consed.
>>
>>versus the loop version which gets
>>; Evaluation took:
>>; 0.03 seconds of real time
>>; 0.03 seconds of user run time
>>; 0.0 seconds of system run time
>>; 0 page faults and
>>; 32 bytes consed.
>>
>>Not too bad.
>
>
> What is "the loop version"? Those using one index for all three
> vectors (and thus doing different thing)? On my machine:
Yes, the vector-+-loop that Brian Downing gave. And yes, you are right,
the series version has checks for the end of BOTH arrays while doing
the work. That probably explains why series is slower than Brian's
loop and why it's comparable to your loop over both arrays.
> BTW, does an implementation exist, allowing to write just (SCAN
> 'VECTOR X) above without performance loss?
>
I just tried that. Yes, you can do that, and it looks like CMUCL will
be able to derive the element type of the array. Unfortunately, series
does a (setq element (aref x k)), and CMUCL isn't smart enough to figure
out that element is always a double-float and hence doesn't have to box
it. Then you lose. By using the (scan '(simple-array double-float)
...), series puts in the appropriate declarations for element.
Ray
From: Joe Marshall
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <of2uekpd.fsf@ccs.neu.edu>
Brian Downing <···········@lavos.net> writes:
> I can't get MAP-INTO to not cons a ton in CMUCL on x86.
>
> (defparameter *a* (make-array 1048576
> :element-type 'double-float
> :initial-element 1.0d0))
> (defparameter *b* (make-array 1048576
> :element-type 'double-float
> :initial-element 1.0d0))
> (defun vector-+-map-into (x y)
> (declare (optimize (speed 3) (safety 0) (debug 0))
> (type (simple-array double-float) x y))
> (map-into x #'+ x y)
> (values (aref x 0) (aref y 0)))
>
> * (time (vector-+-map-into *a* *b*))
> ; Compiling LAMBDA NIL:
> ; Compiling Top-Level Form:
>
> ; Evaluation took:
> ; 1.44 seconds of real time
> ; 0.11 seconds of user run time
> ; 1.31 seconds of system run time
> ; [Run times include 0.14 seconds GC run time]
> ; 3 page faults and
> ; 92,293,080 bytes consed.
> ;
> 2.0d0
> 1.0d0
>
> Does anybody know how to get MAP-INTO to not cons on CMUCL? It would seem
> that you're stuck using custom map macros otherwise if you want speed.
It may be that CMUCL simply does not know how to inline the call to
MAP-INTO. If that is the case, then the implementation of MAP-INTO
will be using generic sequence functions and calling the generic
addition routine which will lead to a ton of consing of boxed floats.
See if you can determine whether CMUCL can inline MAP-INTO.
Maybe if the function were a literal lambda expression?
(map-into x (lambda (a b)
(declare (type double-float a b))
(+ a b))
x y)
Just a guess.
From: Brian Downing
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <yTcqa.619183$F1.82724@sccrnsc04>
In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu> wrote:
> It may be that CMUCL simply does not know how to inline the call to
> MAP-INTO. If that is the case, then the implementation of MAP-INTO
> will be using generic sequence functions and calling the generic
> addition routine which will lead to a ton of consing of boxed floats.
>
> See if you can determine whether CMUCL can inline MAP-INTO.
> Maybe if the function were a literal lambda expression?
> (map-into x (lambda (a b)
> (declare (type double-float a b))
> (+ a b))
> x y)
> Just a guess.
A good guess too, it did reduce boxing by a little bit. But it's still
not too good:
* (time (vector-+-map-into *a* *b*))
; Evaluation took:
; 1.44 seconds of real time
; 0.1 seconds of user run time
; 1.31 seconds of system run time
; [Run times include 0.15 seconds GC run time]
; 0 page faults and
; 92,295,704 bytes consed.
* (time (vector-+-map-into-2 *a* *b*))
; Evaluation took:
; 1.29 seconds of real time
; 0.13 seconds of user run time
; 1.16 seconds of system run time
; [Run times include 0.14 seconds GC run time]
; 1 page fault and
; 75,513,248 bytes consed.
I may try and take a look at how to optimize MAP-INTO, but the
CMUCL development process is intimidating to say the least, and I
know almost nothing about compilers (and am pretty new at Lisp to
boot).
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
From: Joe Marshall
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <n0iea0yz.fsf@ccs.neu.edu>
Brian Downing <···········@lavos.net> writes:
> In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu> wrote:
> > It may be that CMUCL simply does not know how to inline the call to
> > MAP-INTO. If that is the case, then the implementation of MAP-INTO
> > will be using generic sequence functions and calling the generic
> > addition routine which will lead to a ton of consing of boxed floats.
> >
> > See if you can determine whether CMUCL can inline MAP-INTO.
> > Maybe if the function were a literal lambda expression?
> > (map-into x (lambda (a b)
> > (declare (type double-float a b))
> > (+ a b))
> > x y)
> > Just a guess.
>
> A good guess too, it did reduce boxing by a little bit. But it's still
> not too good:
>
> * (time (vector-+-map-into *a* *b*))
> ; Evaluation took:
> ; 1.44 seconds of real time
> ; 0.1 seconds of user run time
> ; 1.31 seconds of system run time
> ; [Run times include 0.15 seconds GC run time]
> ; 0 page faults and
> ; 92295704 bytes consed.
>
> * (time (vector-+-map-into-2 *a* *b*))
> ; Evaluation took:
> ; 1.29 seconds of real time
> ; 0.13 seconds of user run time
> ; 1.16 seconds of system run time
> ; [Run times include 0.14 seconds GC run time]
> ; 1 page fault and
> ; 75,513,248 bytes consed.
That reduced the consing by about 1/5th.
I'm going to guess that all we saved here was `restifying' the
argument to #'+
Brian Downing <···········@lavos.net> writes:
> In article <···············@five-percent-nation.mit.edu>,
> rif <···@mit.edu> wrote:
> > > Did you consider using MAP-INTO?
> >
> > I hadn't heard of it. Shows what I get for not studying carefully
> > enough. That still happens to me a lot, actually. Thanks. My
> > approach still makes some things easier I think (automating certain
> > kinds of type declarations), but map-into probably could've done a lot
> > of that for me.
>
> I can't get MAP-INTO to not cons a ton in CMUCL on x86.
This is definately not the most efficient part of CMUCL.
First of all:
> (defun vector-+-map-into (x y)
> (declare (optimize (speed 3) (safety 0) (debug 0))
> (type (simple-array double-float) x y))
> (map-into x #'+ x y)
> (values (aref x 0) (aref y 0)))
Here, the call to + is having its arguments boxed going in and its
return value is being boxed coming out. You can at least fix that
easily:
(defun vector-+-map-into-flet (x y)
(declare (optimize (speed 3) (safety 0) (debug 0))
(type (simple-array double-float) x y)
(inline map-into))
(flet ((+ (x y)
(declare (double-float x y))
(+ x y)))
(map-into x #'+ x y))
(values (aref x 0) (aref y 0)))
With this definition, Python is able to figure out that it can use a
specialized + variant, not the full generic one.
As for MAP-INTO, well, here's the definition:
(defun map-into (result-sequence function &rest sequences)
(let* ((fp-result
(and (arrayp result-sequence)
(array-has-fill-pointer-p result-sequence)))
(len (apply #'min
(if fp-result
(array-dimension result-sequence 0)
(length result-sequence))
(mapcar #'length sequences))))
(when fp-result
(setf (fill-pointer result-sequence) len))
(dotimes (index len)
(setf (elt result-sequence index)
(apply function
(mapcar #'(lambda (seq) (elt seq index))
sequences)))))
result-sequence)
Note the call to APPLY and MAPCAR at the end. That's why inlining
doesn't help too much -- you still cons up an arglist every time (ug).
You can ameliorate this somewhat by compiling and loading a file
containing the following new definition, that at least reuses the cons
cells for the arglist:
(declaim (ext:maybe-inline map-into))
(defun map-into (result-sequence function &rest sequences)
(let* ((fp-result
(and (arrayp result-sequence)
(array-has-fill-pointer-p result-sequence)))
(len (apply #'min
(if fp-result
(array-dimension result-sequence 0)
(length result-sequence))
(mapcar #'length sequences)))
(arglist (make-list (length sequences))))
(when fp-result
(setf (fill-pointer result-sequence) len))
(dotimes (index len)
(loop for arg-cell on arglist
for seq in sequences
do (setf (car arg-cell) (elt seq index)))
(setf (elt result-sequence index)
(apply function arglist))))
result-sequence)
These two changes reduce consing by about 1/2, and overall run-time by
1/3. This still sucks compared to the loop though.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> These two changes reduce consing by about 1/2, and overall run-time by
> 1/3. This still sucks compared to the loop though.
Perhaps I'm naive, but doesn't this suggest an implementation strategy
for map-into that
a. does some setup work (to figure out whether one is mapping into a
list or vector, etc.)
b. and then uses loop
?
-russ
Russell McManus <···············@yahoo.com> writes:
> ···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > These two changes reduce consing by about 1/2, and overall run-time by
> > 1/3. This still sucks compared to the loop though.
>
> Perhaps I'm naive, but doesn't this suggest an implementation strategy
> for map-into that
>
> a. does some setup work (to figure out whether one is mapping into a
> list or vector, etc.)
> b. and then uses loop
Well, the right thing to do is to teach the compiler about MAP-INTO,
and let Python go at it. I was just making the obvious changes that
could be easily loaded into a running CMUCL, without spending more
than 10 min at it. Note that if it's inlined, the calls to ELT become
efficient, thanks to Python.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
From: Gabe Garza
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <878ytyt707.fsf@ix.netcom.com>
Brian Downing <···········@lavos.net> writes:
> I can't get MAP-INTO to not cons a ton in CMUCL on x86.
>
That's because it's not well optimized. I've been itching to learn
DEFTRANSFORM and friends, so here's a stab at it. It makes your
example consless and fast.
I haven't used DEFTRANSFORM before, so I'd love some criticism--I'd
especially like to know if there's a way to avoid having to make one
DEFTRANSFORM form for each combination of arguments.
(in-package :c)
(defun make-inline-map-into (target target-type
function
sources source-types)
(flet ((make-end-test (index types seqs)
(multiple-value-bind (lists arrays)
(loop for type in types
and seq in seqs
if (eq type 'list)
collect seq into lists
else if (eq type 'vector)
collect seq into arrays
end
finally (return (values lists arrays)))
(let ((min-array-length (gensym "MIN-ARRAY-LENGTH")))
(values
(if (null arrays) nil
`(,min-array-length
(min ,@(loop for array in arrays
collect `(array-dimension ,array 0)))))
`(or ,@(loop for list in lists collect `(null ,list))
,@(unless (null arrays) `((= ,index ,min-array-length)))))))))
(let* ((index (gensym "MAP-INTO-INDEX"))
(result (gensym "RESULT"))
(there-are-arrays (or (eq 'vector target-type)
(find 'vector source-types))))
(multiple-value-bind (end-test-init end-test-form)
(make-end-test index
(cons target-type source-types)
(cons target sources))
`(let* ((,result ,target)
,@(and end-test-init (list end-test-init))
,@(and there-are-arrays `((,index 0))))
,@(and (eq target-type 'vector)
`((when (array-has-fill-pointer-p ,target)
(setf (fill-pointer ,target)
,(car end-test-init)))))
(loop
(when ,end-test-form
(return ,result))
(setf ,(if (eq target-type 'vector)
`(aref ,target ,index)
`(car ,target))
(funcall ,function
,@(loop for source in sources
and type in source-types
if (eq type 'vector)
collect `(aref ,source ,index)
else
collect `(car ,source)
end)))
,@(loop for type in (cons target-type source-types)
and pointer in (cons target sources)
when (eq type 'list)
collect `(pop ,pointer))
,@(when there-are-arrays `((incf ,index)))))))))
(defknown map-into (sequence t &rest sequence) sequence (call))
(macrolet ((make-map-into-transform (num width)
(let ((types (loop for j from (1- width) downto 0
if (= 1 (logand (ash num (- j)) 1))
collect 'vector
else
collect 'list
end))
(args (loop repeat width collect (gensym "S"))))
`(deftransform map-into
((,(car args) f ,@(cdr args))
(,(car types) * ,@(cdr types))
* :when :both :important t)
"inline map-into"
(make-inline-map-into ',(car args) ',(car types)
'f
',(cdr args) ',(cdr types)))))
(make-map-into-transforms ()
`(progn
,@(loop for width from 2 to 4 append
(loop for j from 0 below (expt 2 width)
collect `(make-map-into-transform ,j ,width))))))
(make-map-into-transforms))
; Gabe Garza
From: Alexey Dejneka
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <m3he8lrjq0.fsf@comail.ru>
Gabe Garza <·······@ix.netcom.com> writes:
> I haven't used DEFTRANSFORM before, so I'd love some criticism--I'd
> especially like to know if there's a way to avoid having to make one
> DEFTRANSFORM form for each combination of arguments.
Yes.
> (in-package :c)
>
> (defun make-inline-map-into (target target-type
> function
> sources source-types)
> (flet ((make-end-test (index types seqs)
> (multiple-value-bind (lists arrays)
> (loop for type in types
> and seq in seqs
> if (eq type 'list)
> collect seq into lists
> else if (eq type 'vector)
> collect seq into arrays
> end
> finally (return (values lists arrays)))
> (let ((min-array-length (gensym "MIN-ARRAY-LENGTH")))
> (values
> (if (null arrays) nil
> `(,min-array-length
> (min ,@(loop for array in arrays
> collect `(array-dimension ,array 0)))))
> `(or ,@(loop for list in lists collect `(null ,list))
> ,@(unless (null arrays) `((= ,index ,min-array-length)))))))))
> (let* ((index (gensym "MAP-INTO-INDEX"))
> (result (gensym "RESULT"))
> (there-are-arrays (or (eq 'vector target-type)
> (find 'vector source-types))))
> (multiple-value-bind (end-test-init end-test-form)
> (make-end-test index
> (cons target-type source-types)
> (cons target sources))
> `(let* ((,result ,target)
> ,@(and end-test-init (list end-test-init))
> ,@(and there-are-arrays `((,index 0))))
> ,@(and (eq target-type 'vector)
> `((when (array-has-fill-pointer-p ,target)
> (setf (fill-pointer ,target)
> ,(car end-test-init)))))
> (loop
> (when ,end-test-form
> (return ,result))
> (setf ,(if (eq target-type 'vector)
> `(aref ,target ,index)
> `(car ,target))
> (funcall ,function
> ,@(loop for source in sources
> and type in source-types
> if (eq type 'vector)
> collect `(aref ,source ,index)
> else
> collect `(car ,source)
> end)))
> ,@(loop for type in (cons target-type source-types)
> and pointer in (cons target sources)
> when (eq type 'list)
> collect `(pop ,pointer))
> ,@(when there-are-arrays `((incf ,index)))))))))
>
> (defknown map-into (sequence t &rest sequence) sequence (call))
>
> (macrolet ((make-map-into-transform (num width)
> (let ((types (loop for j from (1- width) downto 0
> if (= 1 (logand (ash num (- j)) 1))
> collect 'vector
> else
> collect 'list
> end))
> (args (loop repeat width collect (gensym "S"))))
> `(deftransform map-into
> ((,(car args) f ,@(cdr args))
> (,(car types) * ,@(cdr types))
> * :when :both :important t)
> "inline map-into"
> (make-inline-map-into ',(car args) ',(car types)
> 'f
> ',(cdr args) ',(cdr types)))))
> (make-map-into-transforms ()
> `(progn
> ,@(loop for width from 2 to 4 append
> (loop for j from 0 below (expt 2 width)
> collect `(make-map-into-transform ,j ,width))))))
> (make-map-into-transforms))
Your code ignores fill pointers:
* (funcall (compile nil '(lambda ()
(let ((a (vector 1 2 3))
(b (make-array 4 :initial-contents '(a b c d) :fill-pointer 2)))
(map-into a (lambda (x) (cons x x)) b)))))
Compiling LAMBDA NIL:
Compiling Top-Level Form:
#((A . A) (B . B) (C . C))
Should be:
[2]> (funcall (compile nil '(lambda ()
(let ((a (vector 1 2 3))
(b (make-array 4 :initial-contents '(a b c d) :fill-pointer 2)))
(map-into a (lambda (x) (cons x x)) b)))))
#((A . A) (B . B) 3)
A transformer can return a lambda expression - it allows to deal with
&REST arguments.
Arguments of a transformer are continuations. Use CONTINUATION-TYPE on
them to get an inferred type (an object of type CTYPE; use
CSUBTYPEP/CTYPEP on it; SPECIFIER-TYPE parses CL type specifiers).
Below is a slightly modified version used in SBCL. It does not work
when the result is a list, but is applicable to any number of
arguments and to complex vectors.
(in-package :c)
(defknown map-into (sequence callable &rest sequence)
sequence
(call)
:derive-type #'result-type-first-arg)
(defun build-sequence-iterator (seqs seq-names &key result into body)
;; shared between MAP and MAP-INTO optimizers
(declare (type list seqs seq-names)
(type symbol into))
(collect ((bindings)
(declarations)
(vector-lengths)
(tests)
(places))
(let ((found-vector-p nil))
(flet ((process-vector (length)
(unless found-vector-p
(setq found-vector-p t)
(bindings `(index 0 (1+ index)))
(declarations `(type index index)))
(vector-lengths length)))
(loop for seq of-type continuation in seqs
for seq-name in seq-names
for type = (continuation-type seq)
do (cond ((csubtypep type (specifier-type 'list))
(let ((index (gensym "I")))
(bindings `(,index ,seq-name (cdr ,index)))
(declarations `(type list ,index))
(places `(car ,index))
(tests `(endp ,index))))
((csubtypep type (specifier-type 'vector))
(process-vector `(length ,seq-name))
(places `(aref ,seq-name index)))
(t
(give-up
"can't determine sequence argument type"))))
(when into
(process-vector `(array-dimension ,into 0))))
(when found-vector-p
(bindings `(length (min ,@(vector-lengths))))
(tests `(= index length)))
`(do (,@(bindings))
((or ,@(tests)) ,result)
(declare ,@(declarations))
(let ((funcall-result (funcall fun ,@(places))))
(declare (ignorable funcall-result))
,body)))))
(deftransform map-into ((result fun &rest seqs)
(vector * &rest *)
*)
"open code"
(let ((seqs-names (mapcar (lambda (x)
(declare (ignore x))
(gensym))
seqs)))
`(lambda (result fun ,@seqs-names)
,(build-sequence-iterator
seqs seqs-names
:result '(when (array-has-fill-pointer-p result)
(setf (fill-pointer result) index))
:into 'result
:body '(setf (aref result index) funcall-result))
result)))
If Python were smarter, the transformer could be simplified and emit
(loop for i from 0 below (array-dimension result 0)
for x1 in/across arg1
...
do (setf (aref result i) (funcall fun x1 ...))
finally ...)
but it is compiled to a less efficient code than the expansion built
by the code above :-(.
--
Regards,
Alexey Dejneka
From: foomaster1200
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <87wuhyaubm.fsf@killr.ath.cx>
Greg Menke <··········@toadmail.com> writes:
> Mark Conrad <······@iam.invalid> writes:
>
>> I know, it is a dumb question, but I can get by with it because I am a
>> newbie.<g>
>
> It depends on the implementation. Manual gc control, or even
> adjustment of whatever parameters are available is something to
> consider when there are particular performance requirements that your
> program isn't meeting. On the other hand, the impact of gc is very
> dependent on how your code is written- in general, if you don't cons a
> lot, the gc overhead will be lower.
I'm newbie too, I read in Graham's ANSI CL book that this consing/GC
relationship is more dependent on your CL implementation these
days. He goes onto describe the use of pools to lower GC overhead.
--
You were s'posed to laugh!
In article <··············@killr.ath.cx>, foomaster1200
<·············@yahoo.com> wrote:
> I'm newbie too...<snipped>...
Ahh, Newbie, take my Newbie's hand, together we will become confused<g>
On a side issue, I see you also read Paul Graham's books like I do.
Lotsa stuff in his books that makes life easier for newbies.
I was facinated by Graham's "On Lisp" book. The subtitle of that book
is: "Advanced Techniques for Common Lisp"
Among other 'advanced' techniques, he shows that a crippled version of
Scheme's "continuations" can be implemented in Common Lisp.
He does this with six CL macros, in his book. Unfortunately, there
seems to be some typos in the book description of the macros.
I 'repaired' the macros by rewriting them slightly, then the macros
worked okay with CL. (MCL Common Lisp)
According to the various Lisp books that I have here, continuations can
add even more flexibility to CL than it already has.
(by flexibility, I mean the ability of a CL programmer to create code
that would be almost impossible to create in languages like C)
There are several downsides, though. CL code with continuations is
much harder to understand, therefore much more subject to inadvertant
errors if one is not extremely careful when using continuations, and
when "maintaining" code that has continuations in it.
Not only that, but worse yet nasty errors can crop up, due to the fact
that CL and Scheme are inherently different from each other.
Still, I had fun playing with continuations in CL, doing stuff that was
ordinarily only possible in Scheme.
What I would really like to do, when continuations are needed, is to
temporarily "drop out" of CL, then "go into" Scheme just long enough to
do my continuation thingy, then return to CL with the results of the
Scheme detour.
In other words, "call" the Scheme language from CL, temporarily.
As a Lisp newbie, that sounds like it might work - - - but then, a lot
of things sound like they might work, only to find out later that they
are not feasible.
Mark-
On Mon, Apr 14, 2003 at 01:17:10PM +0000, Mark Conrad wrote:
> What I would really like to do, when continuations are needed, is to
> temporarily "drop out" of CL, then "go into" Scheme just long enough
> to do my continuation thingy, then return to CL with the results of
> the Scheme detour.
>
> In other words, "call" the Scheme language from CL, temporarily.
Sure, that's what you're doing with the macros. Creating your own
domain-specific language for the task, and using it within CL.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
From: Joe Marshall
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <8yuddvmj.fsf@ccs.neu.edu>
Mark Conrad <······@iam.invalid> writes:
> Uh, that brings up a question. Can CL garbage collection be somehow
> "controlled" manually, so that the performance hit does not occur.
Yes.
> I know, it is a dumb question, but I can get by with it because I am a
> newbie.<g>
It isn't really a dumb question.
The first thing about controlling the impact of GC is this:
The rate of collection is equal to the rate of consing.
This is simply an equalibrium statement. There may be short-term
fluctuations and exceptional situations, but the fact remains that if
your collection rate is less than your consing rate, you'll eventually
run out of memory. Therefore,
To avoid collecting garbage, don't allocate.
If you absolutely cannot tolerate a GC pause, you have to carefully
manage memory such that you never allocate fresh structures.
However, if `some' amount of GC is tolerable, the situation is quite
different. First, *measure* the performance hit! If you are spending
less than about 5% of your time in GC, is it really worth optimizing?
A generational collector working with a `typical' lisp program takes
only a few percent of processor time.
Second, add some RAM and use it. The more RAM you have, the longer
you can go without collecting the youngest generation. The less
frequent the GCs, the more time for young objects to die, and the less
work the GC has to do. Make sure your youngest generation takes up a
substantial portion of your RAM. For some reason, the default
settings in many lisps are absurdly frugal: a few hundred K for the
youngest generation.
Third, if you are allocating something that you know will live a long
time, try to allocate it in an older generation.
In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu>
wrote:
> > Can CL garbage collection be somehow "controlled" manually,
> > so that the performance hit does not occur.
>
> Yes.
> The first thing about controlling the impact of GC is...<snipped>...
Thanks for the tips on somewhat controlling the CL automatic garbage
controller; I was not even aware that there was any way to control the
default settings of the garbage controller in the MCL implementation of
CL.
Obviously, I have been away from Lisp too long. I am going to have to
start from scratch about learning CL fundamentals.
Mark-
Mark Conrad <······@iam.invalid> wrote in message news:<·························@iam.invalid>...
> In article <····························@posting.google.com>, Kaz
> Kylheku <···@ashi.footprints.net> wrote:
>
> > There are Lisp implementations that compile to C ...<snipped>...
>
> Excuse me again (everyone) - I really got these threads all messed up.
>
> When I started these threads, I thought that the Lisp compilers
> converted the Lisp source-code to C - - - that was wrong, as someone
> here pointed out to me.
>
> The Lisp compiler that makes the standalone executable creates
> machine-code, I am told, not C code.
Not necessarily. Those compilers that produce C instead of machine
object code can also produce stand-alone executables.
> Thanks for pointing that out.
>
> As _you_ pointed out, Kaz, there are also CL implementations that
> convert the Lisp source-code to "incomprehensible" C code, code that
> looks entirely different than regular C code.
That's right. C is used this way not only by some Lisp
implementations, but by the implementations of other high level
languages, because using C eliminates the need to write
machine-specific code generation. C can only be used this way because
it is popular and because it has certain machine-language-like
semantics, like the flexible treatment of memory with pointer
arithmetic, and the ease by which the type system can be defeated (at
the penalty of writing C that is no longer well-defined by the ANSI C
standard).
> Is there anything that C is 'better at' than Lisp? <MCL Lisp>
> (other than C being able to work on practically every hardware platform)
C is currently better at being popular, and consequently better at
being found everywhere, including rare embedded systems. There are
probably machines for which your only programming alternative beside
assembly language is C.
C is more cleanly separated into a language and library than Lisp, and
the ANSI C standard even defines the requirements for a ``freestanding
implementation'' in which most of the C library is missing. Such an
implementation requires little or no run-time support. What this means
is that there is a readily identifiable subset of C which is suitable
for writing a kernel of code that runs on the bare hardware, with a
minimal amount of machine language glue or other run-time support.
People use C for writing embedded operating system kernels and other
components such as device drivers because it's a boneheadedly simple
technology for doing so that someone with an EE degree can understand.
On the other hand, these systems written in C exhibit bugs that
require years to hunt down, not to mention laughable security holes
that are discovered years after initial deployment. So it's hard to
conclude that C is actually a successful tool in its domain of
application. But when it's not corrupting data, or sending a copy of
it to an intruder's machine, and when it's carefully written to avoid
doing stupid things like copying the same data many times between
layers of code, code written in C can run fast as hell!
From: Joe Marshall
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <3ckldvba.fsf@ccs.neu.edu>
···@ashi.footprints.net (Kaz Kylheku) writes:
> People use C for writing embedded operating system kernels and other
> components such as device drivers because it's a boneheadedly simple
> technology for doing so that someone with an EE degree can understand.
> On the other hand, these systems written in C exhibit bugs that
> require years to hunt down, not to mention laughable security holes
> that are discovered years after initial deployment. So it's hard to
> conclude that C is actually a successful tool in its domain of
> application.
Consider sendmail for example.
From Mario S. Mommer -
> > ...and for that matter "continuations", which can be implemented in a
> > crippled fashion in CL using Paul Graham's techniques, or better yet
> > using advanced Continuation-Passing-Style techniques, which preserve
> > _all_ the features of Scheme continuations, according to the Scheme
> > book "Essentials of Programming Languages".
>
> Continuation-passing style doesn't require Scheme's call/cc. The
> "technique" of which you speak is simply an inclusion of the
> continuation in the parameters of every function you write. Scheme
> makes this unnecessary, with call/cc.
Uh, I think I failed to communicate to you exactly what I meant, lemme
try again -
I know that CPS does not require Scheme's call/cc
Rather, CPS is an advanced technique to _implement_ continuations in
CL. Common Lisp does not support continuations, as you know.
The closest CL comes to supporting continuations is by using the CL
constructs "throw" and "catch", along with other CL constructs like
"go" and "block" and a few other CL constructs.
All the above mentioned CL constructs can not exactly implement
continuations. They do some of what continuations can do, but not all
of what continuations can do.
For example, the Scheme code below:
(+ 1 (call/cc (lambda (cc)
(set! old-cc cc)
(+ 20 (cc 300)))))
301
(old-cc 500)
501
...can't be duplicated in CL because of CL's inability to return to a
continuation point more than once.
The equivalent CL code returns an error:
(+ 1 (catch 'tag (+ 20 (throw 'tag 300))))
301
(throw 'tag 500)
Error: there was no pending CATCH for the tag TAG
In other words, call/cc's continuations have indefinite extent, while
throw/catch tags only have dynamic extent.
(all the above code and comments reference page 771 of:
Paradigms of Artificial Intelligence Programming
subtitle - Case Studies in Common Lisp)
This raises all sorts of nasty problems when a CL app' tries to do
automatic backtracking, which is why I think it might be a good idea to
implement "true" continuations in CL by using CPS techniques.
> The "technique" of which you speak is simply an inclusion of the
> continuation in the parameters of every function you write.
I assume you mean including a continuation in a CL function's parameter.
I don't believe it is all that simple, because CL does not "understand"
Scheme continuations.
Please forgive me if I am misunderstanding you, these topics are
difficult for me to comprehend, under the best of circumstances.
Implementing CPS in CL is discussed in detail pages 241-289 of the book
that I refered to.
Be aware that CPS it is a _very_ hairy technique. (at least for me)
Both "wind" and "unwind-protect" are discussed in the same book.
(pages 321, 322)
Both the "wind" and "unwind" mechanisms, when implemented in CL, can
eliminate errors that would otherwise occur in automatic backtracking
applications written in CL. Examples of such errors are described in
pages 321 and following pages.
Both wind and unwind can be implemented in CL provided that "true"
continuations are first implemented in CL by the very hairy CPS.
<sigh> - if this is simple stuff, I shudder to think what I am in for
once I get more CL under my belt.
Mark-
From Kenny Tilton -
> 1. what makes you think MCL cannot generate a standalone executable for
> OS X? get in now while it's got a pre-release discount
I did not realize that MCL was capable of creating a standalone
executable for OS X, that was pointed out to me by several people here.
I have the pre-release beta version of MCl (for OS X)
> 2. what do you need an executable for? i know, dumb question, but often
> non-lispniks think that is the only way to "run" a Lisp app.
Mainly, because I like to code in CL, and I was not initially aware
that MCL could create standalone executables that would run in OSX.
Sure will be glad when my Lisp newbie days are over, ten years from now.
Mark-
FWIW, the title of this thread no longer applies, because I have been
're-educated' to know that what I really want is to convert a CL
program to machine code.
It certainly is rough being a CL newbie.
Anyone care to venture a guess as to how long it might take me to get
my CL smarts, assuming I hit the books hard and have somewhat average
intelligence?
Mark-
In article <·························@iam.invalid>, Mark Conrad
<······@iam.invalid> wrote:
> FWIW, the title of this thread no longer applies, because I have been
> 're-educated' to know that what I really want is to convert a CL
> program to machine code.
Then you're in luck. There are tools that do this for you. They are
called Lisp compilers.
> It certainly is rough being a CL newbie.
Hang in there.
> Anyone care to venture a guess as to how long it might take me to get
> my CL smarts, assuming I hit the books hard and have somewhat average
> intelligence?
I've been programming in Lisp for over twenty years and I still learn new
things about CL on a pretty regular basis.
On the other hand, learning enough Lisp to allow me to run circles around
C programmers took me about a week (in 1981).
E.
--
The opinions expressed here are my own and do not necessarily
reflect the views of JPL or NASA.
In article <····················@k-137-79-50-101.jpl.nasa.gov>, Erann
Gat <···@jpl.nasa.gov> wrote:
> I've been programming in Lisp for over twenty years and I still learn new
> things about CL on a pretty regular basis.
Yipes!
> On the other hand, learning enough Lisp to allow me to run circles
> around C programmers took me about a week (in 1981).
Hokay, I will study hard for a week, then go into the C forums and lord
it over those guys ;-)
Heck, I don't even hafta study fer a week. Lemme see, right now I know
that C does not support first-class functions, doesn't have automatic
GC, not nearly as self-documenting as Lisp, and CLOS has a lot more
going for it than C++ does as far as OOP is concerned, and C escape
features are sad indeed compared to what can be leveraged in CL if some
Scheme 'features' are hijacked over to CL - - - related to that,
automatic backtracking is a breeze in CL, compared to C.
I better get off this kick, I just thought of a dozen more thingies
that CL is better at than C, which I won't bore everyone with.
Hmm, given the drawbacks of C and C++, wonder why they ever became so
'popular'.
Mark-
From: Kenny Tilton
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <3E962309.4090908@nyc.rr.com>
Mark Conrad wrote:
> Hmm, given the drawbacks of C and C++, wonder why they ever became so
> 'popular'.
their exes could run on 4K, when 4K cost a lot (I think I paid $500 to
upgrade my Apple II from the already whopping 16K to 24K back in '78 or
so) and microcomputers were exploding and a whole generation or two took
up computing.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Everything is a cell." -- Alan Kay
Kenny Tilton <·······@nyc.rr.com> writes:
> their exes could run on 4K, when 4K cost a lot (I think I paid $500 to
> upgrade my Apple II from the already whopping 16K to 24K back in '78
> or so) and microcomputers were exploding and a whole generation or two
> took up computing.
a little later than that (in 1988), you could actually run lisp (MCL)
pretty well on off-the-shelf macintoshes, but the unix lisps were
really heavy and expensive, and unix was the driving force behind the
C revolution. I think lisp had a unique chance around that time
(the NeXt cube even came bundled with ACL!), but that the vendors missed
it.
--
(espen)
From: Nils Goesche
Subject: Re: Pitfalls? - Changing Lisp to C (enlightened<g>)
Date:
Message-ID: <877ka2jh3a.fsf@darkstar.cartan>
Mark Conrad <······@iam.invalid> writes:
> FWIW, the title of this thread no longer applies, because I
> have been 're-educated' to know that what I really want is to
> convert a CL program to machine code.
Uhm, that meaning you want to compile it?
> It certainly is rough being a CL newbie.
Naw...
> Anyone care to venture a guess as to how long it might take me
> to get my CL smarts, assuming I hit the books hard and have
> somewhat average intelligence?
Not that long. Stop worrying so much, go ahead and write some
programs in it.
Regards,
--
Nils G�sche
Ask not for whom the <CONTROL-G> tolls.
PGP key ID #xD26EF2A0
In article <··············@darkstar.cartan>, Nils Goesche
<···@cartan.de> wrote:
> > Anyone care to venture a guess as to how long it might take me
> > to get my CL smarts, assuming I hit the books hard and have
> > somewhat average intelligence?
>
> Not that long. Stop worrying so much, go ahead and write some
> programs in it.
That sounds right to me, the best way of learning something is to get
right in there and do it.
Talking about it is not the same, one has to get one's hands dirty.
Lemme see, I gotta pick a project that would frighten the life out of a
C programmer<g>
Mark-