[Prev][Next][Index][Thread]
Re: Dylan Hackers entry won second prize at ICFP 2001
Andreas Bogk <andreas@andreas.org> wrote in message news:<87r8tjqj6g.fsf@teonanacatl.andreas.org>...
> Brad Settlemyer <nobody@nowhere.com> writes:
>
> > Interesting. The guy Bruce thought would win didn't even make top 5. A
> > bit of a surprise there since I think he had the other top 3 finishers
> > picked out. :-|
>
> This is easy to explain: Bruce looked at both execution speed and
> optimizer quality, whereas the real judges didn't look at execution
> speed at all.
While that's perfectly true, the real reason is that his program
didn't manage its RAM use well enough on some of the later test files
and wen't into swap-yourself-to-death mode and failed to terminate
within the time limit.
> And everybody who gets the joke in the name of the winning program,
> which is "LALR(5000000)", must admit that they deserved the first
> place
Yeah. their write-up boggles me.
But, y'know what? From what I've seen in all the new stuff the judges
posted today, If I'd only had the extra half-hour necessary to
implement dynamic adjustment of my "fudge factors" then we would have
beaten them solidly even with our lack of theoretical elegance. Dylan
Hacker was just dragged down too much in the final rounds by a lot of
cases in which it ran out of time and had to fall back to the much
poorer Dylan Lightning result. You can see this because it's the same
output size as for Dylan Lightning. When the judges re-ran those
files with much longer timeouts Dylan Hacker kicked booty.
The Haskell Carrots clearly had the better algorithm, but I think we
had a big edge on them for sheer brute-force speed.
I'm pretty sure that speed is the reason that Andreas' "Beam Search"
didn't do better -- it was a good algorithm and elegantly-written, but
it hadn't been tweaked into producing efficient code. With "Dylan
Hacker" I at least found time to grep the intermediate C code and find
any cases of gf-call in critical loops and do whatever was necessary
to nuke them.
Again with the later tests with much longer timeouts Beam Search
started doing much better, finding better solutions than Dylan Hacker
in several cases -- Dylan hacker was quite well tuned but had a fixed
level of effort and had no way to take advantage of any extra time
that was available. Well, that was an explicit decision of mine so I
can't complain...
All said, we did great. We submitted three quite different programs.
The worst of them (written in 24 hours) got 13th place, the two
72-hour entries both got into the final ten, and the best of them got
2nd.
References: