January 31st, 2005

belize

Minesweeper

Yesterday I wrote a little program to play Minesweeper so I could graph what the likelihood of winning was given certain bomb densities.

Over 19,000 games:



(The X axis is bomb density, Y is winning percentage)

Currently the AI only flags bombs based on O(n) algorithms. I don't do any hypothetical-true-leads-to-inconsistent-state eliminations which get into exponential time, though I'll probably add that sometime.

Of course, sometimes it's just a 50/50 chance and no logic will help.

BOARD 511:

 1 2 X 2 1   1 1 1   1 1 2 1 1   1 * * 1       1 * 2 * 1 1 * * 2
 3 * . * 2   1 * 2 1 2 * 3 * 1 1 2 3 2 1   1 1 2 1 2 1 2 2 4 * 2
 * * * * 2   1 2 * 1 2 * 3 1 1 2 * 2 1 1 2 2 * 2 2 2 2 2 * 2 2 2
 3 4 3 3 3 2 1 1 1 1 1 1 1     2 * 3 2 * 3 * 4 * 2 * * 2 1 2 2 *
 * 2   1 * * 2       1 1 1     1 1 2 * 2 3 * 3 1 2 2 3 2 1 2 * 3
 * 3 1 1 4 * 4 1     1 * 1         2 2 3 3 3 2       1 * 1 2 * 2
 2 * 1   2 * * 1 1 1 2 1 2 1 1 1 1 2 * 3 * * 1   1 1 3 2 2 1 2 2
 2 2 2   1 3 3 2 1 * 1 1 2 * 1 1 * 3 3 * 3 2 1   2 * 4 * 1   1 *
 1 * 2 2 2 3 * 3 2 1 1 1 * 3 2 1 1 2 * 2 2 1 1   3 * * 2 2 1 3 2
 1 1 2 * * 3 * * 2 1 1 3 4 * 2     1 1 1 1 * 1 1 3 * 3 1 2 * 4 *
     1 2 2 2 3 * 2 1 * 2 * * 4 3 3 2 1   1 2 2 2 * 3 3 2 4 * 4 *
       1 1 1 1 2 2 2 1 2 2 3 * * * * 1     2 * 3 2 * 2 * * 2 2 1
       1 * 1 1 2 * 1       1 2 5 * 4 1     2 * 2 1 2 3 3 3 2 2 1
       2 2 2 1 * 2 1         1 3 * 3 1     2 2 2   1 * 1 1 * 3 *
 1 1 1 1 * 1 1 1 1       1 1 2 * 3 * 1     1 * 1   1 1 1 1 2 4 *
 1 * 1 1 1 1             1 * 2 1 2 1 1     1 1 1           1 * 2
DEAD!
belize

lazyweb: buggy XS code

We profiled Perlbal a couple months back and found the only offensively slow part was parsing the incoming HTTP headers. The rest was just system-level stuff like read()/write()/sendfile() that was pretty fast.

So marksmith went home one weekend and busted out an XS module that was a drop-in replacement for the existing Perl code, and could even be enabled/disabled at runtime.

It works great, drastically reducing CPU, but only for about 20 minutes or 2 hours, and then it crashes.

Mad props and a permanent account or so if you want to bug hunt for us and find the problem:

http://www.danga.com/dist/misc/Perlbal-XS-HTTPHeaders-0.13.tar.gz

Four or five times we've seen it crash in getReconstructed() and the this pointer is always messed... usually with a value of like "18" instead of a real memory address.

Seems easy to find, right?

We ran it under valgrind with a debug perl built to not use Perl's malloc or Perl's slabs, but didn't find anything. But we didn't run it in production on the site, and it only crashes in production and only after millions of requests. So it's some weird corner case.

I don't pretend to understand XS that well, in particular the implict refcount changes coming in/out of XS code. Or the typemap stuff.

Update: Oh, and before Mark tells me --- I'm sure he'll want you to know that this is his first XS code, so don't hate too much.