Python Effort for the ICFP'2000 programming contest
Back
The page for the effort of this year (2001) is on TwistedMatrix Wiki.

About ICFP'2000 programming contest

For the ICFP'2000 conference, a programming contest was proposed, as the 2 previous years. The task was to implement a raytracer and a small functional language in 72 hours.

Contest homepage is http://www.cs.cornell.edu/icfp/, which now displays the results.

Team and final contest submission

We managed to create a "Cobra" team: The entry was named "CuttySark" (a mandatory Monty Python reference: A model ship built in bed in complete darkness. MPFC) Here is the README written by Konrad.

CuttySark's result

We got eliminated in the early rounds as we feared.

Thank to Xavier Leroy who was in ICFP conference, we now know that the entry refered by: "We also eliminated one entry that exhausted our patience; it took over three days to complete one of the tier-3 tests.", is very likely to be the entry in Python that took 3 days for one test with a correct result, quoted in the ICFP conference.
Since there was only one Python entry, it's us !

We are proud to be one of (or the only) entries for which computation of the images takes longer than the programming contest itself: it was hard to code, it should be hard to run :-).

CuttySark's images

We think Tiers-1 and Tiers-2 features were implemented correctly. The main problem is with CSG, but this was expected, since CSG was designed, implemented and debugged in the last hour of the contest. We missed many hours to get something right.

You can find here the CuttySark-rendered example images, which were the example images provided during the contest.
On another page, you can find the result of the CuttySark-rendered contest images and GML errors . Here are the problems met with the examples:

CuttySark ICFP submissions in reverse chronological order

Why is CuttySark so slow ?

I intend to later analyze why it is so slow. Of course the main reasons are: a) the Python interpreter is generally slow, b) there are no optimisations at all.

A quick profiling on some example shows that 60% of the time was spent in Transform.inverseMul and 20% of the time in Transform.getInverse which are: 

class Transform:
[...]
    def inverseMul(self, vector, lastComponent=1.0):
        assert len(vector)==3
        vector=vector+[lastComponent]
        result=[0.0]*4
        for line in range(4):
            for column in range(4):
                result[line]=result[line] \
                  +self.getInverse(line,column)*vector[column]
        return result[0:3]

    def getInverse(self,line,column):
        return self.inverseData[line*4+column]
[...]

Which are easy to optimize a bit (especially if it is the method call, or the repeated attribute lookup, that takes most of the time as expected).

Of course, the astute reader might have guessed that these calculations are due to the fact that CuttySark computes back transforms of all the intersection points and normals, most of which aren't used and could be avoided, especially with a lazy functional language...

More information

After profiling more closely the interpreter with rdtsc, I've found that a number of primitive Python opcodes take 300-1000 cycles to execute (on a Celeron): including getting an attribute from an object, and also making a multiplication (probably in the context of "[0.0]*4"). Since those would take 0.5-10 cycles in compiled C++, a factor 100+ is not surprising.

Additional resource

A standalone statically linked Python 1.5.2 executable is in standalone-0.0.0.tar.gz. (change the "runme" script)

Link to (much) better ICFP entries

Here you can find links to several of your excellent opponets

What was is this ?

A temporary page to temporary lists resources for the Python team(s) for ICFP'2000 programming contest. It was put together in about 1/4 hour :-)
The idea was to keep Pythoneers in touch, and to attempt to form One or several teams (if we happen to have the knowledge to solve the problem ;-))

Initial resources (written before contest start)

Nothing is defined yet, but we tried to organize the Python team:

Cedric Adjih