As a Lisp newbie, I am curious how difficult it might be to manually
convert Common-Lisp source code to C source code.
Let's assume the CL is written in a C friendly fashion, using iteration
instead of recursion.
I am aware of one of the difficulties, such as the need to assign and
release ram memory in C, which is not necessary in Lisp, because of the
automatic garbage collector used by Lisp.
Are there any other difficulties that might trip me up?
Mark Conrad -
Off the subject, but might be of interest to some -
*************************************
P.S. - I know even less about C than I do about Lisp.
P.P.S. - My gear, operating system, prior experience, etc., etc. :
Mac 'Pismo' powerbook running OS 10.2.4 (OS X) with 1,024 MBs of
internal ram - - - waiting for the final OSX release of MCL, due out
shortly.
Over the years, I have fiddled around-the-edges of Common Lisp and
Scheme, learning a wee bit about the shiny-stuff associated with both
dialects of Lisp, such as Continuation Passing Style, various versions
of the Y Operator, Stream Programming, and other stray stuff.
I never learned CL in depth, know even less about Scheme.
Hope to remedy my lack of CL knowledge by hitting the books.
I hate OOP, just a personal thing, no rational reason. Lisp doesn't
seem to have as much need for OOP as other languages do.
My favorite Lisp book is "Essentials of Programming Languages",
unfortunately it was written in 1994 - - - wish I could find a more
recent book like that one.
**************************************
End of background info' - - -
Anyhow, thanks ahead of time for any "lists" of possible difficulties
in manually converting CL source-code to C source-code.
Mark Conrad <······@iam.invalid> wrote in message news:<·························@iam.invalid>...
> As a Lisp newbie, I am curious how difficult it might be to manually
> convert Common-Lisp source code to C source code.
>
> Let's assume the CL is written in a C friendly fashion, using iteration
> instead of recursion.
>
Use of macros, closures and higher-order functions is likely to
complicate conversion more than mere presence of recursion.
In general, if you want to end up with human-readable and maintainable
code, it would be easier to grok algorithm of the Lisp code and write
a corresponding C version from scratch.
--
Eugene
In article <···························@posting.google.com>, Eugene
Zaikonnikov <······@funcall.org> wrote:
> In general, if you want to end up with human-readable and maintainable
> code, it would be easier to grok algorithm of the Lisp code and write
> a corresponding C version from scratch.
Wow! , thanks everyone, I got a lot more help here than I had
anticipated.
Obviously, I forgot to post that I wanted to create the C version from
scratch, just using the CL source code as a guide - sorry about that
omission.
Oh yeah, my reason for wanting to create a C version is because C seems
to be the more-or-less universal language that computer applications
are written in. I realize that by itself, that is not an adequate
reason, but I get the definite "feeling" that using MCL to create an
executable from the CL source-code is not the way to go.
For one thing, the C executable created by MCL would likely not run
correctly on Apple's new operating system. (a Unix variant)
By contrast, if I created a C version from scratch, using Apple's own
Developer Tools, it would likely run correctly.
I think I will have to do the following:
First off, I gotta learn both CL and C well enough to be reasonably
competent in both languages.
Then I have to learn how to use Apple's developer tools, while I am
creating the C version, to ensure that the resulting output code will
run on the "Apple-Adulterated" version of Unix.
When I create the initial CL version, I can probably get by with using
macros, higher-order functions, lexical-closures, and all the other
great features that CL has, because _most_ of these features should
be able to be implemented the "hard way" in C. (using tables, arrays,
databases, and such)
What bugs me is that there are a few features that just plain can't be
reasonably re-created in C, such as run-time compilation and/or
evaluation -
...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".
Continuations do have a place in CL in my opinion, because some
run-time search techniques would then be "workable" in CL using Scheme
constructs like "wind" - - - which would otherwise not be feasable in
CL without continuations. (take much too long to run "unforeseen"
searches without the help of continuations)
...wind can not be implemented using catch/throw or other techniques
available in CL, continuations are definitely called for in the case of
wind.
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.
I think I better give up in trying to recreate a hairy CL app' in C.
Sounds difficult/impossible to me, even if I knew what I was doing.
Mark-
On Thu, Apr 10, 2003 at 05:22:34AM +0000, Mark Conrad wrote:
> In article <···························@posting.google.com>, Eugene
> Zaikonnikov <······@funcall.org> wrote:
>
> > In general, if you want to end up with human-readable and maintainable
> > code, it would be easier to grok algorithm of the Lisp code and write
> > a corresponding C version from scratch.
>
> Wow! , thanks everyone, I got a lot more help here than I had
> anticipated.
>
> Obviously, I forgot to post that I wanted to create the C version from
> scratch, just using the CL source code as a guide - sorry about that
> omission.
>
> Oh yeah, my reason for wanting to create a C version is because C seems
> to be the more-or-less universal language that computer applications
> are written in.
Only in the Unix world.
> I realize that by itself, that is not an adequate reason
Learning C is a far better reason, as you plan to do anyway.
> For one thing, the C executable created by MCL would likely not run
> correctly on Apple's new operating system. (a Unix variant)
MCL's new version works on OS X, as does OpenMCL. It's been around a
while, we know about this "Unix variant" ;) Oh yeah, MCL doesn't create
"C executables", MCL doesn't compile to C at all, it compiles to machine
code directly.
> By contrast, if I created a C version from scratch, using Apple's own
> Developer Tools, it would likely run correctly.
For some value of "correctly" ;)
> I think I will have to do the following:
>
> First off, I gotta learn both CL and C well enough to be reasonably
> competent in both languages.
Fair enough, but you really should do this separately. Programming C in
a CL style, or programming CL in a C style, is bound to result in
problems. Direct translation is almost always a mistake.
> When I create the initial CL version, I can probably get by with using
> macros, higher-order functions, lexical-closures, and all the other
> great features that CL has, because _most_ of these features should
> be able to be implemented the "hard way" in C. (using tables, arrays,
> databases, and such)
Heh, I wish. I've tried. It's not so easy. I gathered up a bunch of
handy libraries for C: The Boehm collector, GNU Multi-precision
arithmetic, s-expr-dot-c, glib... and started hacking away. The
show-stopper was the implementation of proper closures. There are ways
to fiddle with trampolines and such to get the effect, but it was more
than my patience could bear. A real pain in the ass, and decidedly
non-portable. This is the sort of grudge work that compilers are meant
to do.
> ...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.
> 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.
Since when? The whole family of Kyoto Common Lisp based Lisps compile
to C (KCL, AKCL, IBCL, ECLS/ECL, GNU CL). Many languages have compilers
to C. C may not be such an ideal language for this role, but it is
certainly done.
Now, readable generated C--that is rare.
> I think I better give up in trying to recreate a hairy CL app' in C.
> Sounds difficult/impossible to me, even if I knew what I was doing.
I think it's not worth your time.
--
; 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: Kenny Tilton
Subject: Re: Pitfalls? - Changing Lisp Code to C code, manually
Date:
Message-ID: <3E9507FD.9000206@nyc.rr.com>
Mark Conrad wrote:
> ....I get the definite "feeling" that using MCL to create an
> executable from the CL source-code is not the way to go.
>
> For one thing, the C executable created by MCL would likely not run
> correctly on Apple's new operating system. (a Unix variant)
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, btw. otoh, the
web page still says the release will be in Jan, 2003, so...?
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.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Everything is a cell." -- Alan Kay
Mark Conrad <······@iam.invalid> writes:
> Oh yeah, my reason for wanting to create a C version is because C seems
> to be the more-or-less universal language that computer applications
> are written in.
Except for the applications written in COBOL, Java, C++, Perl, Python,
VB, Delphi, Lisp etc...
In a way, C is a "universal language" indeed - about all Systems have
a C compiler, and about all languages can interface with C. But I
don't think that it is the only reasonable language to write whole
application in.
AFAIK, Apple advertises Objective C and Java as the primary
application development languages on OS X, not plain C.
> I realize that by itself, that is not an adequate
> reason, but I get the definite "feeling" that using MCL to create an
> executable from the CL source-code is not the way to go.
>
> 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.
> By contrast, if I created a C version from scratch, using Apple's own
> Developer Tools, it would likely run correctly.
I also have to impression that "running correctly" is not a one of the
greatest strengths of C applications. Think core dump.
> First off, I gotta learn both CL and C well enough to be reasonably
> competent in both languages.
That is never a bad idea, but both are not trivial to master.
> 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? Of course, the generated C code will likely be quite unreadable,
but why would you want to read it in the first place when you have the
original high-level Lisp source?
Both GCL and ECL (I don't know if there are other Lisps compiling to
C) are not new projects, they are modernized versions of an older
system that did this kind of thing. I guess many smart people will
have worked on them in all the years to make sure the generated code
works.
> I think I better give up in trying to recreate a hairy CL app' in C.
> Sounds difficult/impossible to me, even if I knew what I was doing.
It might be an interesting learning experience, but for "real work", I
wouldn't do by hand what computers can do better and faster.
Regards
Henrik
Mark Conrad <······@iam.invalid> writes:
> I think I better give up in trying to recreate a hairy CL app' in C.
Why? It would be a great learning experience.
Regards,
Mario.
Mario S. Mommer <········@yahoo.com> writes:
> Mark Conrad <······@iam.invalid> writes:
> > I think I better give up in trying to recreate a hairy CL app' in C.
>
> Why? It would be a great learning experience.
Most things in the world are great learning experiences for people
whose eyes are open. As such, I don't see the fact that something can
be learned as a per se reason to do any particular thing, since the same
argument would justify nearly anything.
Kent M Pitman <······@world.std.com> writes:
> Mario S. Mommer <········@yahoo.com> writes:
>
> > Mark Conrad <······@iam.invalid> writes:
> > > I think I better give up in trying to recreate a hairy CL app' in C.
> >
> > Why? It would be a great learning experience.
>
> Most things in the world are great learning experiences for people
> whose eyes are open. As such, I don't see the fact that something can
> be learned as a per se reason to do any particular thing, since the same
> argument would justify nearly anything.
Well, in this particular case it would be a kind of "that teaches you"
sort of learning experience; I bet you agree. If the OP starts, for
example, by trying to translate the memoization stuff from PAIP, he is
in for fast-track enlightenment. No argument made here could possibly
illustrate things more clearly.
Regards,
Mario.
Mario S. Mommer <········@yahoo.com> writes:
> Kent M Pitman <······@world.std.com> writes:
> > Mario S. Mommer <········@yahoo.com> writes:
> >
> > > Mark Conrad <······@iam.invalid> writes:
> > > > I think I better give up in trying to recreate a hairy CL app' in C.
> > >
> > > Why? It would be a great learning experience.
> >
> > Most things in the world are great learning experiences for people
> > whose eyes are open. As such, I don't see the fact that something can
> > be learned as a per se reason to do any particular thing, since the same
> > argument would justify nearly anything.
>
> Well, in this particular case it would be a kind of "that teaches you"
> sort of learning experience; I bet you agree. If the OP starts, for
> example, by trying to translate the memoization stuff from PAIP, he is
> in for fast-track enlightenment. No argument made here could possibly
> illustrate things more clearly.
Well, indeed, if one just starts with a few simple examples that are
fairly targeted, you get very good usage of your time because you don't
get side-tracked on irrelevancies.
But if you start, as originally suggested, with a 'hairy CL app', you
_could_ spend hours or days translating the thing that flashes up the
logo and keep postponing the hard parts, all the while reinforcing
your illusion that the translation is straightforward and that there
are no material differences. If you were _really_ unlucky, you'd give
up after doing 90% of it deciding you were bored and that nothing
seemed really different and that there was no point in continuing.
I'm reminded of the time I was in high school in 10th grade and
someone showed me a calculus book. (I hadn't even had analysis yet.)
I thought I was quite the math wiz, having a good strong understanding
of (high school) Algebra and Geometry. I flipped through the book
quickly, taking inventory of the frequency of math symbols that looked
familiar and eventually handed back the book saying "Well, it looks
mostly like stuff I know already. But what are these squiggly
operators here [integral signs and sigmas]?"
Surface syntax similarity can be deceptive.
Mark Conrad <······@iam.invalid> wrote in message news:<·························@iam.invalid>...
> As a Lisp newbie, I am curious how difficult it might be to manually
> convert Common-Lisp source code to C source code.
>
> Let's assume the CL is written in a C friendly fashion, using iteration
> instead of recursion.
Are you serious? For CL to be written in a ``C friendly'' fashion, you
would have to assume no dynamic typing, no garbage collection, no
object system, no non-trivial macros, no lexical closures, no integers
beyond the range [-2147483467, 2147483647], no dynamic variables, no
run-time compilation or evaluation, no local functions, ...
> I am aware of one of the difficulties, such as the need to assign and
> release ram memory in C, which is not necessary in Lisp, because of the
> automatic garbage collector used by Lisp.
>
> Are there any other difficulties that might trip me up?
The above difficulty won't just ``trip'' you up! Some programs that
rely on garbage collection are impossible to translate to programs
that compute object lifetimes explicitly, without transitively closing
over reachability graphs.
> P.S. - I know even less about C than I do about Lisp.
Believe me, it's obvious.
From: Peter Seibel
Subject: Re: Pitfalls? - Changing Lisp Code to C code, manually
Date:
Message-ID: <m3r88cknsc.fsf@javamonkey.com>
Mark Conrad <······@iam.invalid> writes:
> As a Lisp newbie, I am curious how difficult it might be to manually
> convert Common-Lisp source code to C source code.
Someone has to ask, and I'm up reading new because I can't sleep so it
might as well be me: why?
> Let's assume the CL is written in a C friendly fashion, using
> iteration instead of recursion.
There's a lot more to Common Lisp than just recursion. For that matter
the insistance on always using recursion is much more of a Scheme
thing than a Common Lisp thing; why recurse when you have great
iterative constructs like LOOP, DO, DOTIMES, and DOLIST.
> I am aware of one of the difficulties, such as the need to assign
> and release ram memory in C, which is not necessary in Lisp, because
> of the automatic garbage collector used by Lisp.
>
> Are there any other difficulties that might trip me up?
I think the short version is, you're asking for a world of pain if you
think you'll be able to write idiomatic Lisp and then translate it
into C. You'll be almost certain to immediately run afoul of
Greenspun's Tenth Rule of Programming: "Any sufficiently complicated C
or Fortran program contains an ad-hoc, informally-specified bug-ridden
slow implementation of half of Common Lisp."
Depending on why you think this translation to C is necessary, there's
bound to be a better (and totally different) answer such as:
- Use a Lisp implementation that performs native compilation (i.e. to
machine code) and supports building standalone executables.
- Use a Lisp that compiles to C (such as GCL or ECL). (Note, the C
these Lisp's produce is not like any C you'd write by hand. But you
can feed it to a C compiler and get an executable.)
- Write your own Lisp program that generates C code. This is unlikely
to be the right answer but if for some reason you *have* to have C
code but really want to be programming in Lisp, this might be the
way to go. You can google this group for a thread some months back
about a guy who wrote a Java code generator in Lisp in order to do
a job where the client wanted Java but it would have entailed a ton
of cut-n-paste coding.
Or maybe none of these are the right answer. It really depends what
actual problem you are trying to solve.
Also, don't wait for the final version of MCL--if they haven't shipped
the final, you may still be able to buy the beta for a couple hundred
bucks less and get a free upgrade to the final when it comes out.
-Peter
--
Peter Seibel ·····@javamonkey.com
The intellectual level needed for system design is in general
grossly underestimated. I am convinced more than ever that this
type of work is very difficult and that every effort to do it with
other than the best people is doomed to either failure or moderate
success at enormous expense. --Edsger Dijkstra
Mark Conrad <······@iam.invalid> writes:
> As a Lisp newbie, I am curious how difficult it might be to manually
> convert Common-Lisp source code to C source code.
>
> Let's assume the CL is written in a C friendly fashion, using iteration
> instead of recursion.
>
> I am aware of one of the difficulties, such as the need to assign and
> release ram memory in C, which is not necessary in Lisp, because of the
> automatic garbage collector used by Lisp.
>
> Are there any other difficulties that might trip me up?
Hmmm. Let's look at an analogy where you're on the other side of the
fence...
As a Klingon newbie, I am curious how difficult it might be to manually
convert English text to Klingon.
Let's assume the English is written in a Klingon friendly fashion, avoiding
use of 'please'.
I am aware of the difficulties, such as the need to use funny letters
that don't occur in English, which is not necessary in English, because
such letters are automatically available in English.
Are there any other difficulties that might trip me up?
- - - -
Do you mean things like the fact that
- the set of underlying base concepts are wholly different?
- the set of library routines (verbs) is wholly different?
- the vocabulary is (therefore) wholly different?
- the syntax rules (letters used, word order, grouping) are wholly different?
Your question presupposes that the differences between languages are
purely syntactic, and that you have need only to transliterate to
change between languages.
Translation among languages is not always a matter of just changing words.
Different languages actually require different effects to occur.
You are perhaps confused by translation among things like C++ and Java,
which are really little more than a few syntactic changes and the one
semantic change (lack of 'free' / automatic GC). But other languages
differ in remarkably more complex ways than you are imagining.
Also, in many ways, in spite of its syntax, C is effectively an assembly
language. You must do all of the work. Lisp is a high-level language
that provides a number of services for you. What you tell Lisp is not
"how to do something" but "what you want done". An important difference
is that a lot of the work you do in C is micromanaging how things get done.
In Lisp, you often don't have ultra-fine-tuned control of memory locations,
since you have no operators for reading or manipulating them. It is possible
that a competent user of Lisp has only dim awareness of how memory is laid
out, while it's nearly impossible to write a C program where this is true.
GC is only a small part of that...
I think this is not a good first programming problem for you.
I think asking this question to others is nearly isomorphic to asking
Teach me all of the subtleties of your language in response
to this one single question.
That's an unreasonable use of resources. It places too little
responsibility on you, and too much on others.
Mark Conrad <······@iam.invalid> writes:
> As a Lisp newbie, I am curious how difficult it might be to manually
> convert Common-Lisp source code to C source code.
>
> Let's assume the CL is written in a C friendly fashion, using iteration
> instead of recursion.
>
> I am aware of one of the difficulties, such as the need to assign and
> release ram memory in C, which is not necessary in Lisp, because of the
> automatic garbage collector used by Lisp.
>
> Are there any other difficulties that might trip me up?
>
> Mark Conrad -
That would be quite silly because there are CL compilers generating
better code than C compilers...
However, using a garbage collector in C would be very helpful and
would render the translation relatively straightforward..
In any case, you will need to implement a couple of "primitive" easy
functions, like car, cdr, cons and others. (And you'll end up having
reimplemented badly Lisp into your C program).
By the way, why do you want to do it by hand? What would be wrong to
change the back-end of a lisp compiler and generate automatically the
C code?
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
On 8344 day of my life Pascal Bourguignon wrote:
> That would be quite silly because there are CL compilers generating
> better code than C compilers...
Can you give me example? I need such compiler for Linux.
I tested CMU CL, LispWorks (demo) and ACL (demo). CMU CL was fastest,
but slower than C (it was floating-point calculations).
I provided all possible declarations.
--
Ivan Boldyrev
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Outlook has performed an illegal operation and will be shut down.
If the problem persists, contact the program vendor.
Ivan Boldyrev <···············@cgitftp.uiggm.nsc.ru> writes:
> On 8344 day of my life Pascal Bourguignon wrote:
>
> > That would be quite silly because there are CL compilers generating
> > better code than C compilers...
>
> Can you give me example?
GCL.
> I need such compiler for Linux.
Why?
> I tested CMU CL, LispWorks (demo) and ACL (demo). CMU CL was
> fastest, but slower than C (it was floating-point calculations).
I'm not sure that GCL's C will outrun CMUCL's code... C makes extreme
speed *possible* but not certain (in spades).
There's always stalin, if you want to see some completely crazy C :-)
Cheers,
M.
--
You can lead an idiot to knowledge but you cannot make him
think. You can, however, rectally insert the information,
printed on stone tablets, using a sharpened poker. -- Nicolai
-- http://home.xnet.com/~raven/Sysadmin/ASR.Quotes.html
On 8345 day of my life Michael Hudson wrote:
> > > That would be quite silly because there are CL compilers generating
> > > better code than C compilers...
> >
> > Can you give me example?
>
> GCL.
Wait a minute, GCL produces C code, how can it produce better code
than C compiler???
And does it respect dynamic features of Lisp and CLOS?
> > I need such compiler for Linux.
>
> Why?
I want implement system for parallel cluster computation with
Lisp's dynamic features. For example, after adding new node or fail
of existing node system will rebuild yourself and continue...
But nobody want system that runs usual code slowly than C, for
example. With CMU CL, I will need at least 3 cluster nodes to
outperform single-threaded program in C/Fortran.
Please, do not tell me that Lisp is not good for massive floating
point computation. CMUCL-produced code is slower than one of C, but
it is not guilt of Common Lisp, but rather our guilt. :)
I plan to dig CMU CL and SBCL code next summer. Hope, I will found
something to improve. :) I know how difficult and complex compilers
are, but I will try.
> > I tested CMU CL, LispWorks (demo) and ACL (demo). CMU CL was
> > fastest, but slower than C (it was floating-point calculations).
>
> I'm not sure that GCL's C will outrun CMUCL's code... C makes extreme
> speed *possible* but not certain (in spades).
Certainly.
OK, I will try.
> There's always stalin, if you want to see some completely crazy C :-)
It is Scheme compiler, isn't it? Scheme seems to be poor language...
But I will try it too.
--
Ivan Boldyrev
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Violets are red, Roses are blue. //
I'm schizophrenic, And so am I.
From: Bulent Murtezaoglu
Subject: Re: Pitfalls? - Changing Lisp Code to C code, manually
Date:
Message-ID: <87znmw9f11.fsf@acm.org>
>>>>> "IB" == Ivan Boldyrev <···············@cgitftp.uiggm.nsc.ru> writes:
[...]
IB> But nobody want system that runs usual code slowly than C, for
IB> example. With CMU CL, I will need at least 3 cluster nodes to
IB> outperform single-threaded program in C/Fortran. [...]
Can you show us the code? 3x might be a bit too much. I'd say less
than 2x between GCC and CMUCL on x86 when you optimize the Lisp code.
CMUCL doesn't really do anything about loop unrolling or smart register
allocation in inner loops though. Nor does it do things like
peephole optimization or extensive arch-specific optimizations during
code generation. On the other hand, you can do some of those yourself
and more by doing things like runtime/parameter-specific compilation etc.
and save quite a few cycles that way.
If you post sampe code we'll see where the slowness is coming from and
what, if anything, can be done about it.
cheers,
BM
Hi Ivan Boldyrev,
> I optimized it -- it doesn't cons anything, doesn't call generic
> functions etc. OK, 2Kb is not too much.
Can you please post the C code so people can benchmark against it and
compare the resulting assembly?
You appear to have done a thorough job with optimisation. It would make a
good test case for improving the output of the Python compiler.
Regards,
Adam
>>>>> "Ivan" == Ivan Boldyrev <···············@cgitftp.uiggm.nsc.ru> writes:
Ivan> I know other Intel-specific optimizations. For example, multiplying
Ivan> by 5 can be performed with LEA instruction (LEA AX,[4*AX+AX]), as GCC
Ivan> does. And with shifts, we can also multiply by 10, 100 etc faster.
Ivan> You can also do one-tact multiplication by 3 and 9 with this trick.
FWIW, I think SBCL has these tricks implemented. This should easily
port to CMUCL for anyone who cares.
Ivan> Another important (for me) optimization -- using BSR instruction for
Ivan> implementation of CL:INTEGER-LENGTH (for fixnums, of course).
Ivan> Currently it is implemented with shifts in loop.
Making CMUCL and SBCL aware of the newer instructions would be nice.
(What does BSR do?)
Ray
From: Alexey Dejneka
Subject: Re: Pitfalls? - Changing Lisp Code to C code, manually
Date:
Message-ID: <m3n0it0vt1.fsf@comail.ru>
Raymond Toy <···@rtp.ericsson.se> writes:
> Ivan> Another important (for me) optimization -- using BSR instruction for
> Ivan> implementation of CL:INTEGER-LENGTH (for fixnums, of course).
> Ivan> Currently it is implemented with shifts in loop.
>
> Making CMUCL and SBCL aware of the newer instructions would be nice.
> (What does BSR do?)
According to CMUCL CVS, BSR is used in INTEGER-LENGTH since, at least,
1997.
--
Regards,
Alexey Dejneka
"<Zhivago> mutants tend to turn evil after a while, and go around
eating people's brains." -- #lisp
On 8349 day of my life Alexey Dejneka wrote:
> Raymond Toy <···@rtp.ericsson.se> writes:
>
> > Ivan> Another important (for me) optimization -- using BSR instruction for
> > Ivan> implementation of CL:INTEGER-LENGTH (for fixnums, of course).
> > Ivan> Currently it is implemented with shifts in loop.
> >
> > Making CMUCL and SBCL aware of the newer instructions would be nice.
> > (What does BSR do?)
Bit Scan Reverse -- it searches index of leftmost 1.
> According to CMUCL CVS, BSR is used in INTEGER-LENGTH since, at least,
> 1997.
CMU Common Lisp 18d, running on localhost.localdomain
Send questions to ··········@cons.org. and bug reports to ·········@cons.org.
Loaded subsystems:
Python 1.0, target Intel x86
CLOS based on PCL version: September 16 92 PCL (f)
* (declaim (optimize (speed 3) (safety 0)))
* (defun try-it (x) (declare (type (unsigned-byte 29) x)) (integer-length X))
* (disassemble 'try-it)
Compiling LAMBDA (X):
Compiling Top-Level Form:
48043430: .ENTRY "LAMBDA (X)"(x) ; (FUNCTION (FIXNUM) (MOD 30))
48: POP DWORD PTR [EBP-8]
4B: LEA ESP, [EBP-32]
4E: SAR EDX, 2
51: CMP EDX, 0 ; No-arg-parsing entry point
54: JNL L0
56: NOT EDX
58: L0: BYTE #x0F
59: MOV EBP, 1107719378
5E: SHL EDX, 2
61: JMP L1
63: XOR EDX, EDX
65: L1: MOV ECX, [EBP-8]
68: MOV EAX, [EBP-4]
6B: ADD ECX, 2
6E: MOV ESP, EBP
70: MOV EBP, EAX
72: JMP ECX
74: NOP
75: NOP
76: NOP
77: NOP
Oh, really. BYTE #x0F is first byte of BSR instruction. So,
'disassemble is broken?
I couldn't decipher this code before, so I desided that BSR is not used.
But compiler doesn't take in account that x is unsigned-byte. NOT EDX
won't be ever executed. :)
--
Ivan Boldyrev
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Today is the first day of the rest of your life.
>>>>> "Ivan" == Ivan Boldyrev <···············@cgitftp.uiggm.nsc.ru> writes:
Ivan> On 8349 day of my life Alexey Dejneka wrote:
>> Raymond Toy <···@rtp.ericsson.se> writes:
>>
>> > Ivan> Another important (for me) optimization -- using BSR instruction for
>> > Ivan> implementation of CL:INTEGER-LENGTH (for fixnums, of course).
>> > Ivan> Currently it is implemented with shifts in loop.
>> >
>> > Making CMUCL and SBCL aware of the newer instructions would be nice.
>> > (What does BSR do?)
Ivan> CMU Common Lisp 18d, running on localhost.localdomain
Ivan> Send questions to ··········@cons.org. and bug reports to ·········@cons.org.
Ivan> Loaded subsystems:
Ivan> Python 1.0, target Intel x86
Ivan> CLOS based on PCL version: September 16 92 PCL (f)
Ivan> * (declaim (optimize (speed 3) (safety 0)))
Ivan> * (defun try-it (x) (declare (type (unsigned-byte 29) x)) (integer-length X))
Ivan> * (disassemble 'try-it)
Ivan> Compiling LAMBDA (X):
Ivan> Compiling Top-Level Form:
Ivan> 48043430: .ENTRY "LAMBDA (X)"(x) ; (FUNCTION (FIXNUM) (MOD 30))
Ivan> 48: POP DWORD PTR [EBP-8]
Ivan> 4B: LEA ESP, [EBP-32]
Ivan> 4E: SAR EDX, 2
Ivan> 51: CMP EDX, 0 ; No-arg-parsing entry point
Ivan> 54: JNL L0
Ivan> 56: NOT EDX
Ivan> 58: L0: BYTE #x0F
Ivan> 59: MOV EBP, 1107719378
Ivan> 5E: SHL EDX, 2
[snip]
Ivan> Oh, really. BYTE #x0F is first byte of BSR instruction. So,
Ivan> 'disassemble is broken?
Apparently so. I guess someone forgot to tell the disassembler how to
print out this function. It seems all of the bit manipulation
instructions don't have printers....
Ivan> I couldn't decipher this code before, so I desided that BSR is not used.
Ivan> But compiler doesn't take in account that x is unsigned-byte. NOT EDX
Ivan> won't be ever executed. :)
Because the VOP (virtual op) that implements the core of
integer-length was only written for (signed-byte 32), which is a
supertype of (unsigned-byte 29). If a version for (unsigned-byte 32)
were written, this could be optimized away.
Ray
"Ivan Boldyrev" <···············@cgitftp.uiggm.nsc.ru> wrote in message
··················@elaleph.borges.cgitftp.uiggm.nsc.ru...
> On 8346 day of my life Bulent Murtezaoglu wrote:
>
> Agree. But interprocess communication has own price too. Total
> slowdown IMHO is above 2x.
Depending on the volume of the data, this should be a wash for both systems.
One shouldn't be dramatically slower than the other given that the slow part
is the actual transmission of the data over the wire.
The cost of the communication would be the network cost, and then the price
of converting your data into a format suitable for the network traffic.
If the C version is working more on a native format, where little conversion
is being done to make it ready for transport (like sending C structs over
the wire directly, for example), then the C version would certainly be
faster for IPC in that case.
So, if you're doing a lot of data conversion before sending it over the
network, perhaps some work can be done on the protocol side to improve
performance there.
Regards,
Will Hartung
(·····@msoft.com)
From: Marco Antoniotti
Subject: Re: Pitfalls? - Changing Lisp Code to C code, manually
Date:
Message-ID: <6r%la.56$zV2.7505@typhoon.nyu.edu>
Ivan Boldyrev wrote:
> On 8345 day of my life Michael Hudson wrote:
>
> >>>That would be quite silly because there are CL compilers generating
> >>>better code than C compilers...
> >>
> >>Can you give me example?
> >
> >GCL.
>
>
> Wait a minute, GCL produces C code, how can it produce better code
> than C compiler???
>
> And does it respect dynamic features of Lisp and CLOS?
>
>
> >>I need such compiler for Linux.
> >
> >Why?
>
>
> I want implement system for parallel cluster computation with
> Lisp's dynamic features. For example, after adding new node or fail
> of existing node system will rebuild yourself and continue...
>
> But nobody want system that runs usual code slowly than C, for
> example. With CMU CL, I will need at least 3 cluster nodes to
> outperform single-threaded program in C/Fortran.
>
> Please, do not tell me that Lisp is not good for massive floating
> point computation. CMUCL-produced code is slower than one of C, but
> it is not guilt of Common Lisp, but rather our guilt. :)
>
> I plan to dig CMU CL and SBCL code next summer. Hope, I will found
> something to improve. :) I know how difficult and complex compilers
> are, but I will try.
One project that was mentioned on the CMUCL imp mailing list was to add
a "peep-hole" optimizer to Python (the real thing, not tllotbafir). GCC
has had such a thing from the beginning. Such thing is credited for
much of the performance that you can squeeze out of GCC.
I never was a compiler person, but I bet that that would definitively be
a very nice project for CMUCL (and SBCL).
Cheers
--
Marco Antoniotti
Marco Antoniotti <·······@cs.nyu.edu> writes:
> Python (the real thing, not tllotbafir).
OK, what the hell is "tllotbafir" ?
You've been referring to Python by this sequence of characters for a
couple of years now, and I can't suppress my curiosity any
more. Google doesn't help! What does it mean? Pleeeeeeeeeeeease !
From: Joe Marshall
Subject: Re: Pitfalls? - Changing Lisp Code to C code, manually
Date:
Message-ID: <el45dwpn.fsf@ccs.neu.edu>
Ivan Boldyrev <···············@cgitftp.uiggm.nsc.ru> writes:
> On 8345 day of my life Michael Hudson wrote:
> > > > That would be quite silly because there are CL compilers generating
> > > > better code than C compilers...
> > >
> > > Can you give me example?
> >
> > GCL.
>
> Wait a minute, GCL produces C code, how can it produce better code
> than C compiler???
Lisp -> C compilers *can* produce code that performs better than
hand-written C in some cases. The resulting C code doesn't look much
like C, though. I don't have any off-hand, but it resembles this:
LISP_OBJECT obj11392 = CAR (obj11381);
if (OBJECT_PRIMARY_TYPE (obj11392) == LISP_TYPE_CODE_IMMEDIATE)
goto L2253;
if (OBJECT_PRIMARY_TYPE (obj11392) == LISP_TYPE_CODE_NULL)
goto L2254;
LISP_OBJECT obj11393 = CDR (obj11381);
Sometimes the code is better because high-level optimizations that a C
compiler couldn't do have been performed prior to the generation of
the C code. (Other times it isn't as good. It depends a lot on the
compiler.)
>
> And does it respect dynamic features of Lisp and CLOS?
I don't know the details of GCL.
From: Michael J. Ferrador
Subject: Re: Pitfalls? - Changing Lisp Code to C code, manually - FP
Date:
Message-ID: <3E985FEE.6F71E43F@orn.com>
Ivan Boldyrev wrote:
>
> On 8344 day of my life Pascal Bourguignon wrote:
>
> > better code than C compilers...
>
> Can you give me example? I need such compiler for Linux.
>
> I tested CMU CL, LispWorks (demo) and ACL (demo). CMU CL was fastest,
> but slower than C (it was floating-point calculations).
>
> I provided all possible declarations.
I first saw a PPC (MCL) float compier at lemonodor:
http://lemonodor.com/archives/000329.html#000329
leading home to (the bottom of) - http://vorlon.cwru.edu/~beer/
maybe if this gets ported around - more people will use / abuse,
not undestand the limitations of FP -
http://lambda.weblogs.com/2003/01/21
I think it's kinda sad (for the alternative CPU club) if the
conclusion that the only hardware FP approaching correctness is
in x86, Then I really hope that one of the 64bit extensions
makes it big soon, with CL ports.