Tuesday, July 29, 2014

ICFP Programming Contest 2014

Coder? Goto github repo.

I participated together with my friend and ex-colleague Jan, as team "A Storm of Minds".

Since, after a short glance at the specs, it was obvious we didn't want to implement our LambdaMan in its machine language gcc (no, I did not recognize the SECD machine - a bit embarrassing, but my university days were long ago). So we decided on a division of efforts:

me: implement compiler from some reasonable source language to gcc code.

Jan: design LambdaMan logic; implement and test lambdaman as soon as compiler works.

I had a parser for a untyped functional language with Haskell-like syntax lying around, and used that for a quick start. Generating gcc code is easy enough, and on the second try I also got the calling conventions right. 12 hours into the contest, the compiler was basically finished. I later rewrote the parse to get better error reporting, and also added better error reporting to the code generator.

Jan started to write lambdaman code as soon as the syntax of our language was fixed, and soon had a working version with the basics for adjacent cells (prefer pills to empty cells, flee from ghosts, try to eat ghosts when in fright mode).
He then started to extend that to take into account more than the immediate surroundings.

When the full task appeared after the lightning division ended, we decided that Jan would continue to improve the lambdaman, and I would start to work on the ghosts.

Given the limitations of the ghc language - only up to 256 instructions and 256 bytes of memory, I thought that it would be contraproductive to build a compiler from a C or Pascal-like language, complete with register allocator, calling convention, and so on. So I decided on a macro-assembler approach. I wrote a very simple assembler in Haskell, not even adding compile-time arithmetic. Surprisingly, I found the parser harder to write than for the gcc compiler, and really spent too much time on it (lack of sleep may have contributed to that, though).

Coding itself went well, even though a some familiarity with real microprocessors, most notably the 6502, kept me from fully realizing the potential of the ghc instruction for a long time - I subconsciously assumed that some addressing modes just could not be possible (such as indirect addressing in both operands). Things became much easier once I became aware of that mistake.

What stumped me was to come up with a good strategy for the ghosts, though. I finally settled on moving in the direction of the lambda when not in fright mode, and in the reverse direction when frightened. Too our surprise, that worked really well on the sample maps (until the ghostbusters map appeared, that is). That, plus a few refinements such as only fleeing when near the lambda, and some code to get out of the box on the classic map, ended up being our ghost submission.

Jan meanwhile implemented quite a lot of logic to detect dead-ends, look further in all directions, and a decision strategy to decide on the next move. His biggest problem was debugging and refactoring for readability. Since my compiler did not have any type-checking for tuples, "wrong tag" errors were quite common, with no indication where things went wrong. I amended the compiler to support the hlt and dbug instructions, but more was not possible at that time, so Jan was forced to use "printf"-style debugging with only integers for messages.

Our source code, submissions, and some more notes on strategy: https://github.com/bokesan/icfpc2014

Wednesday, March 26, 2014

Nikon D600 Service Experience

I recently sent my Nikon D600 in for servicing because of the shutter / oil on sensor problem. Here's a transcript, sort of:

  • Nikon has a special support notice on the problem. Finally.
  • The support notice has a service submission link - cool, so I don't have to enter that much stuff, and the Nikon service will know what to do right away.
  • Not so - the link leads to the general service submission form.
  • So I fill that out - lots of choices, but unclear what to enter for the "D600 problem".
  • Still, I manage to fill out the form and get a free shipping label.
  • Strange, camera sent to somewhere near Hamburg, while Nikon's central service, which is probably the only place where they'll do a shutter assembly replacement, is in D├╝sseldorf. But I support they know what they are doing.
  • Carry packet to post office
  • two days later:
  • Mail from Nikon: They have analyzed the problem and determined that my camera can only be handled by the central repair center. So they are sending it to D├╝sseldorf.
  • two days later:
  • Mail from Nikon with a receipt.
  • Being the anally retentive type, I actually look at the receipt: Camera - check, neck strap (funny, I thought I took that off), battery (funny, I thought I took that out), battery grip (funny, I don't even own a battery grip). Not. My. Camera.
  • Check serial number of camera. Now, what was my camera's serial no.? Can't find it.
  • search documents for half an hour
  • Get my camera serial no. from EXIF data in images. Nope, definitely not my camera.
  • Send mail to Nikon service telling them that they have some packets confused.
  • Nikon responds immediately: "Sorry for the error, we corrected that".
  • a few hours later:
  • Mail from Nikon service: Servicing my camera will take longer than expected - they had to order parts in Japan. Oh, and it's that other D600 with battery grip again.
  • Decide not to respond, assuming that it will just take some time for the news to trickle through the service center.
  • a few days later:
  • I discover that I miss the D600.
  • Ok, which camera to use instead? Panasonic GF1? Nice, but I only have the 20mm pancake and am in short telephoto mood. Mothballed D70s? No metering with the lenses I want to use.
  • Wait, what about analog? Cameras I have (lots). But only a few old rolls of Velvia 50. Bit slow for hand-held shots.
  • Discover that my F2AS has a roll of Kodak BW400CN in it, with only 6 frames used. That will do.
  • Take that F2, a 2.5/105 and 1.4/35 MF.
  • Spring starts in all it's glory. Colors everywhere. Blue sky, cherry trees blossoming in pink, all manner of flowers, red-golden sunsets.
  • Actually take a shot or two, as I wonder how this will come over in black and white. Once I finish that roll and get it developed, that is.
  • few (long) days later:
  • Mail from Nikon: service completed, camera on it's way back to me. No mention of any serial numbers.
  • two days later:
  • Packet arrives. Inside: one D600, one battery grip.
  • No, it's not like you think.
  • Check serial no.: it is my D600!
  • But obviously, not my battery grip. (I don't own one, remember?)
  • Send Mail to Nikon: would you like me to send back the battery grip?
  • Nikon: sends free shipping label for battery grip.

I sure hope that other person will eventually get his/her battery grip back. (I don't want to think about how far the neck strap and battery might have travelled).

Oh yes: there are some dust spots on the sensor. Luckily, I learned how to clean that during my first year with the D600...

Update 2014-07-16 - Good news: no new oil spots have appeared yet. So the servicing seems to have been successful.

Sunday, January 26, 2014

Join the Kaveri

... or you might want to wait a bit.

Last week, I replaced the A8-6600K in my FM2+ system by the A10-7850K. I have to admit that had not read up on state of drivers beforehand - I just assumed that Windows would work out of the box, and Linux would work, but maybe without graphics acceleration.

I was wrong: Windows worked, but without graphics acceleration, and Linux failed to boot.

Windows first: downloaded the „latest Windows beta driver“ (13.11) from the catalyst site. Still no go. Turns out that there’s an apparently much „later“ beta driver (13.30). That one works like a charm. So why don’t I get it when downloading the „latest“ driver, AMD?

On to Linux. I’m running Fedora 20, and for some reason, I thought that would be leading-edge enough to work with Kaveri. I could boot to the console (runlevel 3), but GDM always crashed. Tried kernel 3.13, but no change. Updated mainboard BIOS - nope. Adding „nomodeset“ to the kernel command line works nicely, though. I now have graphics, but (as expected) without acceleration. I can currently live with that on Linux, and anyway, I expect it’ll be fixed soon. (2014-02-03: fixed with Fedora kernel 3.12.9-301).

Performance is disappointing, though. Except for 3D graphics on Windows, everything seems a little slower than on the A8-6600K. Now, if I had been upgrading from a A10-6800K, I’d have expected that, but from the A8?! According to turbostat, turbo is working, but only up to about 3.9GHz, while the 6600K was always reaching top turbo. It’s not a thermal problem - in fact, the new CPU seems to run about 5° cooler on average. I will have to analyze the turbo problem further, or just hope that the next BIOS or kernel update will help.

Saturday, December 28, 2013

CPU Cooler for ASRock FM2A88X-ITX+

I'm just building a system using the ASRock FM2A88X-ITX+ mainboard in a SilverStone FT03-Mini case. The CPU is currently a AMD A8-6600K, likely to be replaced by a Kaveri model, as soon as that is available. Since the AMD boxed cooler is sorely challenged to cool a 100W CPU, I clearly needed a better solution. Searching the web only revealed a lot of compatibility problems with earlier ASRock Mini-ITX boards, in particular because of components interfering with the backplate needed by most coolers.
I finally ordered a Scythe Big Shuriken Rev. B and can say that it fits without a problem, after I removed the silly heat spreaders from the RAM modules. The cooler works very well, keeping the CPU at 55° celsius while never going above 900 RPM.

Underside with backplate

RAM module with heat spreader removed (top)

The cooler does not interfere with the PCI-Express slot

But, as mentioned in some reviews, the case HD-audio connector (the yellow one, to the right in the images above and below) is placed in line with the slot, and might interfere with a GPU if the circuit board extends downward behind the connector. Not a major problem, though - I suppose you could always use the backplate connectors if your GPU interferes here.

Friday, April 20, 2012

IntervalMap released

I added some benchmarks using criterion. There is a benchmark section in the cabal spec, so you can run the benchmarks using cabal bench (more info in Johan Tibell's blog entry). Here is a sample report from a run on my machine.

Next steps: implement a hedge-union algorithm, and look at delete performance.

IntervalMap home page, hackage

Monday, February 13, 2012

CoffeScript performance hints

This applies only if you have tight loops in your code - if you are manipulating the DOM or making network requests, ignore this.

1. Specify a direction for counting loops

In a range such as [m..n] CoffeeScript can't know if n is larger or smaller then m, so it generates code like this:

n = 10
for i in [1..n]
  foo i

translates to

for (i = 1; 1 <= n ? i <= n : i >= n; 1 <= n ? i++ : i--) {

Add a "by 1" after the range, and you get

for (i = 1; i <= n; i += 1) {

2. No return value might be bad

CoffeeScript will return a list of expression values from a for loop, even if you do not care about the return value.

foo = (n) ->
  for x in [1..n] by 1
    bar x

translates to

foo = function(n) {
  var x, _results;
  _results = [];
  for (x = 1; x <= n; x += 1) {
  return _results;

CoffeeScript allocates a list to hold the result from each iteration! If your code does not otherwise allocate memory, this could easily get you a factor of 10 slowdown.

If you add an explicit return value, all is well:

foo = (n) ->
  for x in [1..n] by 1
    bar x

translates to

foo = function(n) {
  var x;
  for (x = 1; x <= n; x += 1) {
  return false;

Monday, January 2, 2012

Haskell Interval Maps

I just released my first package on Hackage: a library similar to Data.Map, but taking intervals as keys and allowing efficient search for all keys containing a point or contained in an interval, for example.

I needed a data structure - in Java - to search in a set of overlapping appointments, that is, intervals of timestamps. I found nothing suitable on the web, and so I started to implement it on my own. Wikipedia yielded augmented search trees as the basic idea. I often use Haskell for prototyping stuff I'll eventually have to implement in Java, C, or whatever.

After that I had a leftover Haskell implementation, and thought that completing it might be a good project to get a bit more into Haskell again. I've been following Haskell for a long time (since before there were type classes, actually), but never used it for larger projects, and I've not kept up with recent developments.

I used How to Write a Haskell Program as a guideline.

The first thing to do was to implement a reasonably full-featured interface. Data.Map was the obvious guideline to use, and I was dismayed by the number of functions it offers. It really seems a bit too rich. It's certainly nice to have all these functions, but on the other hand the pure mass of them also makes it harder to use the library (now, which function should I use...) and to read code using it. In the end I did implement most of them, but it was really a tough decision not to go for a leaner interface.

Next step was going for better test coverage. QuickCheck is great, so that did not take too long (but my test code looks ugly and could use some refactoring). What did take much longer was fixing the bugs this uncovered, especially in the delete... functions.

Next was the standard Haskell build system: cabal. This also took some time. Despite the good user manual, I still had trouble with many aspects. For starts: which version of base do I need? To my surprise, I did not find reasonable documentation about this anywhere. Integrating the tests was also a bit tricky.

I also wrote some performance tests using criterion, but found that the results are very unreliable on my system. But at least I was able to see that the performance was reasonably close to Data.Map for the basic functions, and that fromDistinctAscList seemed indeed to be linear.

Here's the projects home page: http://www.chr-breitkopf.de/comp/IntervalMap/
Hackage: http://hackage.haskell.org/package/IntervalMap