| Jack Palevich 的个人资料GrammerJack日志 |  工具  帮助 |
|
2006/7/23 Software Archeology with ICFP contestThis weekend I spent about 15 hours on the Nineth Annual ICFP Programming Contest.
ICFP is the International Conference on Functional Programming (the real name is French), and it's actually held in September. The programming contest is held early, so that the results can be announced at the conference. The idea is for multiple teams of people to compete in writing programs, using the language of their choice. The prize is to have the winning team's language acknowleged as "the tool of discriminating hackers". (Here"hackers" is used in its older, more innocent meaning as someone who works very hard to quickly write a program.)
Every year is a different problem. Originally the problems tended to center around writing programs that directly competed against other teams programs, but in recent years the focus has shifted to more indirect competition.
This year's contest is designed by CMU, and is very clever -- you are given a specification for a virtual machine and a program written for that virtual machine. The story is that the spec and program are from an ancient now extinct cult of programmers, and you have three days to figure out as much as possible about their programming culture.
The program turns out (after you write a VM to interpret it) to be an image of an actual time-shared computer from the ancient days, with multiple professor's accounts on it. You get to break into each account. Each professor uses a different ancient computer language (all of them modeled loosely on a modern-world languages), and much of the contest is related to learning and writing programs in each of the different languages.
As an example, the first language you encounter is a variation of BASIC, but with Roman Numerals for literal constants and line numbers rather than Decimal Numerals.
I really enjoyed the 15 hours I spent on the contest. I wrote the VM using F#, which turned out to be very good for the task. It was easy to write, extend, and debug the code. And the resulting program ran more than fast enough to complete the rest of the contest. The only problem I ran into was that the default UTF8-based output routines munged the binary data that they wrote. (This is a .NET problem rather than a F# problem.) Switching to the BinaryStreamWriter class solved that problem.
I also got stuck for a while because the VM spec was unclear on how end-of-line characters in user input were to be processed. This was even worse because of the way the timesharing computer code provided by CMU was coded -- it went into an infinite loop rather than complaining that it was given bad input. It took me a while to decide that the simulated timesharing computer was actually in an infinite loop rather than just doing a lot of computation.
I stopped competing after 15 hours because of other obligations, and also because I was not very interested in learning the peculiar ancient programming languages (and peculiar programming problems) I had to master to continue with the contest.
This year's contest design was great fun -- I liked both the idea of writing a VM and the idea of hacking into an ancient computer system. It reminded me of the old days of using unix over a dial-up connection.
However, I didn't much care for the later stages of the contest. Learning toy functional programming languages to solve toy functional programming problems isn't very interesting to me. In my opinion it's also somewhat against the traditional spirit of the contest, which is to pit different real-world programming languages against each other. After the first few hours of VM programming, which is in the traditional spirit, the rest of the contest is spent programming in the ancient programming languages rather than in the contestent's choice of modern programming language.
I do think that this contest topoic is a great contest in general, and it does expose the contestants to many different functional programming languages, but it's just not what I was hoping for.
In the end I only scored 320 points, which I would call a respectable single player beginner's score. I think large teams have a big advantage in this contest because in the middle of the contest there are so many tasks that can be worked on in parallel.
I look forward to next year's contest. (Maybe I'll try and organize and/or join a team), and hope that next year's contest returns to the original contest spirit of competing modern languages.
2006/7/20 Quantifying the cost of garbage collection vs. malloc/freeHere's an interesting paper on the cost of garbage collection vs. Malloc.
Quantifying the Performance of Garbage Collection vs. Explicit Memory Management (pdf 1.6 MB)
The authors hacked up a Java VM so they could automatically convert benchmark programs from using garbage collection to using various forms of explicit memory management. (They ran the program several times -- the first time they collected data about when objects became garbage, the second time they used this data to decide when to "free" the objects.) Their study points out an important fact about GC: For many types of GC, GC cost is proportional to used heap size, but gc frequency is inversely proportional to the free heap size. (And they measure gc overhead as inversely proportional to the square of the heap size, but they don't understand why it's the square.)
The authors conclusion:
Now, what does this have to do with games? Well, Tim Sweeney says his Unreal 3 engine has around 50 MB of live pointer-base objects. So to run comfortably with a GC environment he would need an extra 100 MB of RAM. That's a lot for a game console, with only 512 MB of RAM total, shared between code, game data and graphics. On the other hand, for a 2 GB PC with a seperate graphics card 100 MB isn't much overhead at all.
Still, turn it around the other way -- if garbage collection was the norm, and someone had just invented explicit memory management, game developers would be the first to jump on this new paradigm, as it offered space savings of 60% combined with performance improvements of 17%. All in exchange for making programming just a little more difficult. :-)
|
|
|
