From: David Steuber
Subject: Lisp vs Speed, er, C
Date: 
Message-ID: <87r7c2azjb.fsf@david-steuber.com>
"Oh no, not again!" --- Bowl of petunias

I entered a contest to churn out fractals rather quickly.  Lisp was on
one of the eligible languages.  C was another.  Yannick Gingras wrote
an entry in C that is quite a bit faster than my Lisp implementation.

If anyone has the time or inclination, I'm curious if the Lisp version
can be made faster to close the gap.  Details and links to both sets
of code are reachable via this link:

  http://www.david-steuber.com/snippets/When_Speed_Is_King/

My code is pure ANSI.  I ripped the jpeg encoder from the Debian Sarge
cl-jpeg package which has a single lisp file to implement a general
purpose jpeg encoder.  The implementation was choosen for its license,
not its quality (there is more than one jpeg.lisp file floating
around).

Some of the folks on #lisp know about this already.  I'm posting this
here because I know how cll people like a challenge.  I'm also up for
comments on my coding style.

-- 
You should maybe check the chemical content of your breakfast
cereal. --- Bill Watterson

From: ··············@hotmail.com
Subject: Re: Lisp vs Speed, er, C
Date: 
Message-ID: <1126037995.158972.62800@g49g2000cwa.googlegroups.com>
David Steuber wrote:
> "Oh no, not again!" --- Bowl of petunias
>
> I entered a contest to churn out fractals rather quickly.  Lisp was on
> one of the eligible languages.  C was another.  Yannick Gingras wrote
> an entry in C that is quite a bit faster than my Lisp implementation.

"Fractals" in a general sense are usually a poor candidate for
apples-to-apples comparisons. In particular, finding the boundary of a
fractal set is theoretically an unbounded computation. To create pretty
pictures, one must arbitrarily cut off some aspect of the computation.
That cutoff can influence the run speed to an arbitrary extent,
depending on how large a chunk of the "infinite computation" you decide
to bite off.
From: David Steuber
Subject: Re: Lisp vs Speed, er, C
Date: 
Message-ID: <873boh21gs.fsf@david-steuber.com>
···············@hotmail.com" <············@gmail.com> writes:

> David Steuber wrote:
> > "Oh no, not again!" --- Bowl of petunias
> >
> > I entered a contest to churn out fractals rather quickly.  Lisp was on
> > one of the eligible languages.  C was another.  Yannick Gingras wrote
> > an entry in C that is quite a bit faster than my Lisp implementation.
> 
> "Fractals" in a general sense are usually a poor candidate for
> apples-to-apples comparisons. In particular, finding the boundary of a
> fractal set is theoretically an unbounded computation. To create pretty
> pictures, one must arbitrarily cut off some aspect of the computation.
> That cutoff can influence the run speed to an arbitrary extent,
> depending on how large a chunk of the "infinite computation" you decide
> to bite off.

Indeed.  One of the problems that Yannick and I had was that we were
not able to get a specific answer to the question of what should the
maximum iterations be to calculate an escape value.  Apress just says,
and kept saying, you need 32 colors.  The contest was underspecified.

There was some mention of pixel accurate.  But that doesn't quite jive
with the requirment for using JPEG over PNG as the file format.

-- 
You should maybe check the chemical content of your breakfast
cereal. --- Bill Watterson
From: Kenny Tilton
Subject: Re: Lisp vs Speed, er, C
Date: 
Message-ID: <7EmTe.14290$ZG2.2110261@twister.nyc.rr.com>
David Steuber wrote:
> "Oh no, not again!" --- Bowl of petunias
> 
> I entered a contest to churn out fractals rather quickly.  Lisp was on
> one of the eligible languages.  C was another.  Yannick Gingras wrote
> an entry in C that is quite a bit faster than my Lisp implementation.

How do you know? I see:

"For one, as I've already mentioned, Yannick's code does only 20 
regions, not 21. Another is that for the sampleinput.txt file, Yannick's 
code is running fewer iterations, producing lower quality images. 
Yannick has also told me that his code uses fork() to multiplex io and 
computation. Most of his time is spent in the jpeg encoding."

You mentioned other differences earlier. You have his C, can't you 
normalize the tests. Agree on 20 vs 21, elim the fork, elim the print 
diagnostics, etc etc? Note that I have no idea if this will make any 
difference, but I do not think we know anything just yet.


-- 
Kenny

Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film

"I've wrestled with reality for 35 years, Doctor, and I'm happy to state 
I finally won out over it."
     Elwood P. Dowd, "Harvey", 1950
From: David Steuber
Subject: Re: Lisp vs Speed, er, C
Date: 
Message-ID: <878xy926pp.fsf@david-steuber.com>
Kenny Tilton <·······@nyc.rr.com> writes:

> David Steuber wrote:
> > "Oh no, not again!" --- Bowl of petunias
> > I entered a contest to churn out fractals rather quickly.  Lisp was
> > on
> > one of the eligible languages.  C was another.  Yannick Gingras wrote
> > an entry in C that is quite a bit faster than my Lisp implementation.
> 
> How do you know? I see:
> 
> "For one, as I've already mentioned, Yannick's code does only 20
> regions, not 21. Another is that for the sampleinput.txt file,
> Yannick's code is running fewer iterations, producing lower quality
> images. Yannick has also told me that his code uses fork() to
> multiplex io and computation. Most of his time is spent in the jpeg
> encoding."
> 
> You mentioned other differences earlier. You have his C, can't you
> normalize the tests. Agree on 20 vs 21, elim the fork, elim the print
> diagnostics, etc etc? Note that I have no idea if this will make any
> difference, but I do not think we know anything just yet.

You make a valid point.  And Yannick told me at least one way to slow
his code for sampleinput.txt:

int nb_iter(val inc)
{
  return 128; // Added by David Steuber for comparison

  int nb = ceil((logf(inc)*L2F)*-21.333048 - 168.944852);
  nb = (nb > MAX_COL) ? MAX_COL : nb;
  return (nb < 60) ? 60 : nb;
}

To "speed up" my code, I commented out the status report lines and
added a condition to the loop to limit myself to 20 images.  After
these changes, I made a few runs:

·····@apostrophe:~/usr/src/apress-fractal/ygingras/fast_fract-1.0
$ time src/fast_fract ../../sampleinput.txt 

real    0m4.236s
user    0m4.085s
sys     0m0.063s
·····@apostrophe:~/usr/src/apress-fractal/ygingras/fast_fract-1.0
$ time src/fast_fract ../../sampleinput.txt 

real    0m4.206s
user    0m4.059s
sys     0m0.073s
·····@apostrophe:~/usr/src/apress-fractal/ygingras/fast_fract-1.0
$ time src/fast_fract ../../sampleinput.txt 

real    0m4.202s
user    0m4.075s
sys     0m0.053s
·····@apostrophe:~/usr/src/apress-fractal/ygingras/fast_fract-1.0
$ time src/fast_fract ../../sampleinput.txt 

real    0m4.204s
user    0m4.068s
sys     0m0.057s
·····@apostrophe:~/usr/src/apress-fractal/ygingras/fast_fract-1.0
$ cd ../..
·····@apostrophe:~/usr/src/apress-fractal
$ time ./run sampleinput.txt 
Generating fractals from "sampleinput.txt"

DONE


real    0m9.036s
user    0m8.729s
sys     0m0.160s
·····@apostrophe:~/usr/src/apress-fractal
$ time ./run sampleinput.txt 
Generating fractals from "sampleinput.txt"

DONE


real    0m9.053s
user    0m8.725s
sys     0m0.153s
·····@apostrophe:~/usr/src/apress-fractal
$ time ./run sampleinput.txt 
Generating fractals from "sampleinput.txt"

DONE


real    0m9.044s
user    0m8.711s
sys     0m0.149s
·····@apostrophe:~/usr/src/apress-fractal
$ time ./run sampleinput.txt 
Generating fractals from "sampleinput.txt"

DONE


real    0m9.085s
user    0m8.755s
sys     0m0.142s
·····@apostrophe:~/usr/src/apress-fractal
$

That closes the gap I guess.

And while I was typing this response I had a simultaneous conversation
on #lisp where salex offered some useful ideas.

More later?

-- 
You should maybe check the chemical content of your breakfast
cereal. --- Bill Watterson