[Home]ICFP

ec2-3-81-184-170.compute-1.amazonaws.com | ToothyWiki | RecentChanges | Login | Webcomic

The International Conference on Functional Programming



Who have an annual [contest]. That page contains links to the previous contests, dating back to 1998.

Notable because recently (as of Jan 07) various ToothyWikizens have got excited about the 2006 contest that accompanied the conference, and have started trying to solve [the contest puzzles].

More details can be found on the website of the [Cult of the Bound Variable]. In particular the specification for the [Universal Machine-32] is worth looking at. Spoilers and other UM implementations can be found at the [icfpcontest-discuss] mailing list.
(PeterTaylor) Although as specs go I've seen better. The "Behaviour" section starts talking about something called the "execution finger" which wasn't mentioned in the "Physical specifications" section. I presume that it's a 32-bit register distinct from the 8 numbered registers, but it would be nice to be told that.
Yep, that's what it is. I found it confusing that it talks about 8 general registers, then talks about registers A, B, and C which are not part of the set of general registers. This kind of thing is probably obvious to people who have looked at such things before though. --RobHu

For those who are happy with spoilers the [video of the conference talk about the contest] is informative and amusing, while the [ICFP 2006 paper] is more informative but less amusing.

RobHu would like to know if anyone is interested in forming a ToothyWiki team for ICFP 2007? Previous years were less interesting but still orders of magnitude more interesting than what RobHu tends to do with his life.

Implementations


RobHu has a bad Ruby implementation [online], a pretty reasonable [C# implementation] (SANDmark in just a smidgeon less than 4 minutes! \o/), and dreams one day of learning enough C to attempt a C one. The Ruby implementation takes about 12 hours to complete 5 SANDmark tests. For reference a good C implementation takes about 1 minute to complete 100 tests. By way of comparison the ICFP paper says that the Python UM-32 implementation made by the contest designers was about 650 times slower than their C implementation.

Edwin has a [C++ implementation], which is a rather unpleasant combination of dodgy casts and C-style I/O.  Still, it works, and does Sandmark in 2:25.
I happened to come across this again, and for some reason decided to have a go at notching up the speed and the evil. Now [eats your children] and runs in 1:11 on my computer.  If you're curious, eliminating the switch and not using vector<> for arrays helped a lot. Mapping the zero array to memory address zero shaved off about two seconds, and probably isn't worth the wtf-ness. --Edwin

MoonShadow's [highly unsafe but quite fast hack] is here. Also, a version [with added evil] for the goto fans.
On my system your UM implementation runs SANDmark in 1:28, 1:20 for the Djikstra version. For reference my C# does it in 3:40, and PaulWright's one does it here in 1:30, so all the C ones are pretty damn close (and if I ran the test again yadda yadda maybe the results would differ slightly). --RobHu

(PeterTaylor) Looking at Edwin's or Moonshadow's code, I can't see where you copy the array that's loaded as a program (instruction 12). That's the major bottleneck in my Java implementation, and I'm not sure what to do about it.
The simplest is just a dumb free/allocate/copy the same as any other array copy.  Faster would be to set up a 'copy on write' scheme, where the old array id aliases the pointer and gets given a new copy only if you try to write to one of the two arrays.  --Vitenka
Edit.  Come to think of it, since it's a functional programming project, alias and renaming is probably the thing they're aiming at.  --Vitenka
(PeterTaylor) Thinking about it some more I had planned to add some benchmarking to see what difference COW would make. The other thing I might try, although I don't think it will have much impact, is object pooling. Edit: Cebsvyvat erirnyf gung ybnq cebtenz jvgu fbhepr neenl bgure guna 0 vf rkgerzryl ener, fb n fvzcyr grfg orsber V pbcl znxrf n ovg vzcnpg.
(PeterTaylor) I then spent ages trying to optimise to get it to complete SANDmark in a reasonable time (as opposed to 19.5 mins). Then I compared it with a C version, and that took 7 mins. Looks like it's a bit CPU-intense for my 700MHz machine. How long do other people have to wait after "ok" before codex is ready for input?
Codex is ready for input? Are you talking about the amount of time it takes to decrypt codex.umz? That takes 1 minute here with my C# implementation (from ok to LOADING:9876543210). --RobHu
I use a vector<> for my arrays, which has value semantics, so assignment makes a copy without any extra work from me. --Edwin
Having optimised the code for performance a little I now do the copy explicitly in the appropriate switch() case block. - MoonShadow
V'z abg fher V haqrefgnaq guvf - gur cebtenz vf qbvat n ybg bs pbcl neenl0 gb neenl 0?  (Bu unat ba, vg'f qbvat vg whfg nf n TBGB, vfa'g vg.  Qbu.) --Vitenka
:-) --RobHu

PaulWright has a horribly unsafe C version [here].

(PeterTaylor) Does anyone have a decryption key I can use? I requested one a few hours ago, but it hasn't been sent.
Seconded. - MoonShadow
(\b.bb)(\v.vv)06AAtlg5Cr2wlxETlm --RobHu

Rachael is working on a C implementation, where "working on" means "spent a couple of hours on Saturday writing it and has been staring at it since then trying to discover why it doesn't work".
...Today I am comparing my implementation in great detail with PaulWright's (both with lots of logging added) to see where I've gone wrong. It seems it's in the reading in of the file into the zero array, not the processing of the instructions. This would be why I'm not seeing any of the error messages they cunningly encoded into sandmark. --Rachael
OK, so I printed out the exact sequence of instructions being read in by my implementation and Paul's, and they were out by one. His seemed to be not using the first four bytes of the input. So I got mine to throw away the first four bytes, and was thereby able to get mine working the same as his does, i.e. printing the loadprog error message (because having the program array off by one is equivalent to having the loadprog instruction off by one). But presumably his does actually work, so, um, maybe I'm compiling it wrong or something?? *confused*
I think your loading of 4-byte platters from the file might have the wrong endian-ness. --Edwin
I don't think so, because that's one of the things sandmark prints out an error for. Also, if I look at all the instructions which mine is doing, they're "sensible" - load numbers into registers x and y, compare x with y and put the result in z, jump to z - which they'd be unlikely to be if the endianness were wrong, because then I'd be using the registers as the instructions and vice versa. (Just to make sure, I tried reversing the endianness, and did get the error message.)
Why not post your code for us to have a look?
Two obvious suggestions.  First, check the spec for when the finger updates - it's not when you might expect it to.  Secondly, check where it specifies what 'position zero' actually means in an array of platters, I recall it being hard to parse, so may be wrongly implemented.  --Vitenka
Pretty confident those two things are OK. But ... it's working now! (Well, nearly. It's printing out part of the expected output, and I can use that to see where I'm still going wrong.) The only change I made to achieve this was using fstat to get the initial file size (I hadn't heard of fstat before I saw it in Paul's code).
Yay! Congrats :-) Nearly there. Then the actual challenges begin! --RobHu
Now at Rachael/ICFP.
ChrisHowlett has ChrisHowlett/ICFP, which originally sandmarked in 3:38 on his work machine. After fixing orthography, it sandmarks in 2:22! (He invites others to try it, as his work machine is not a greased weasel).
(PeterTaylor) 8 mins on mine, so not much better than my Java implementation. Is it doing array bounds checks?
Heh? Actually, there's presumably a bottleneck where I copy the command in case of orthography. I can work around that. --CH

Non-spoiler puzzle discussion




ICFP 2007


[Registration has just opened] for the competition this year (20-23rd July). The rumour is that they're taking the lead from ICFP 06, so it should have a similar style (although more emphasis on things FP is good at). Anyone interested in forming a ToothyWiki team? --RobHu

The puzzle revolved around decoding an alien lifeform's DNA equivalent, which encoded drawing instructions. The ultimate task was to find a DNA prefix which would convert the crashed and damaged scene currently depicted into a bright, sunny, repaired one.

ICFP 2008


The [contest this year] involved writing a system to provide real-time control inputs to a Mars rover, navigating a series of obstacles (including Martians) while providing sensor feedback.

ChrisHowlett is currently uninterested.

ec2-3-81-184-170.compute-1.amazonaws.com | ToothyWiki | RecentChanges | Login | Webcomic
Edit this page | View other revisions | Recently used referrers
Last edited July 13, 2012 8:06 pm (viewing revision 56, which is the newest) (diff)
Search: