This is a utility class that seems to come in handy every few months.

It just provides four methods to save to/load from a normal/isolated storage file.

Here's one way to use it: 

I host a Minecraft server for myself and some friends. It’s a lot of fun; highlights include an extensive public transport network, several castles, a chalet-under-construction, and some cave networks that are pretty imposing, but still nothing close to what the real world has to offer (Mammoth Cave has 630km of explored passageways!)

Minecraft stores its state as a set of binary files in a directory named “world”:

Our world folder is currently just under 200MB. But there’s a problem – if the Minecraft server is halfway through a write when the box shuts down (maybe because a fuse blows), then you end up with corrupted world state, and have to restore from backup. In the four months or so I’ve been paying attention, this has happened four times.

The naïve approach would be a nightly backup of the full 200MB of world state to a single backup folder. The problem here is that if the worldstate becomes corrupted, but you don’t notice before the next backup runs, then you’re out of luck – your active worldstate is corrupted, and so is your only backup.

A nicer approach would be to retain your old backups – each night, you copy the current state to world_backup_20110728, then 29, then 30, etc. The problem here is that each week you chew up 1.4GB of hard drive space.

So then you could have a backup retention policy based on the good old backup tape rotation approach – keep the 6 most recent daily backups, 4 most recent Friday backups, 12 most recent first-of-the-month backups, and all of your first of January backups, say. But that would be a bit more Powershell excitement than I want a quick backup of a game server to extend to.

The approach I’ve settled with for now is this:

1. Download and install Mercurial (including TortoiseHg).
2. Create a backup folder d:\backups\minecraft\worldrepo
3. Run “hg init” in that folder to initialise the backup folder as a Mercurial repository.
4. Schedule a nightly backup script that copies my world state to that backup folder, and then tells Mercurial to update the repository to match the current working directory:

robocopy "c:\program files (x86)\minecraft server\world" d:\backups\minecraft\worldrepo /s
cd d:\backups\minecraft\worldrepo
d:
hg commit --addremove --user backup --message backup

The result is this:

It’s a Mercurial repository that grows each night only by the size of the individual files that have actually changed in the Minecraft world state (plus around 1Kb of bookkeeping; in practice, if nobody’s done any building in Minecraft, I’m seeing the repo grow by 1 Kilobyte each backup). It’d be rare for one player to affect more than, say, 4 region files in a single session, causing around 12MB growth in the backup repo.

The internals of the Minecraft save format (there’s a step at the end of the persistence pipeline that ZLib compresses each 3d area of the map state) are such that a small change in world state (from the PoV of a player) can easily yield a new binary world file that’s quite different to the original. This means that Mercurial’s not going to be able to efficiently store deltas between worldstate versions for a given area of the map, so the size increase of the repository each time you modify an area of the map and add a new backup to the repo is going to be signficant.

One possible solution to this is counter-intuitive – I believe it would be much more space efficient to instead back up a de-compressed version of the individual *.mcr files, so that Mercurial could better exploit the high-inter-version coherence (on average, the change between versions of an area in Minecraft are very small – a tunnel dug here, a small hut here, etc. etc. - not much major terraforming work gets done unless you’re Chris). Under this approach, the first version you store under Mercurial would be much larger, but the increase in repo size with each version you back up would be significantly lower.

I’d like to play with this idea someday.

In conclusion: Mercurial – is there anything it doesn’t improve? The answer: no.

I enjoy a nice apocalyptic vision, me. Of course, “enjoy” is the wrong word. It’s a masochistic pleasure. The Road, for example, was exquisite torment. I wanted to stop, but didn’t, then I wanted to keep going, but couldn’t. Then I had a biscuit and a lie down.

But that was me, on a soft brown couch in a suburban flat. A dark fantasy of the world turned upside-down is only a fantasy if your world is right-side-up. If you’re in a refugee camp or a war-zone, then I imagine the story of The Road holds less of a morbid fascination founded in imagination; its connection to your day-to-day experience would be more direct.

If I was genuinely just interested in a story of a father trying to protect his son against mortal danger in an amoral world, then I would read the news.

I tend not to.

If I’m honest, I think I’m fascinated because I can imagine myself into this father’s shoes, and so the story is about me, and understanding by juxtaposition exactly what it means to have the good fortune to live in a good land at a good time with good genes.

I have a near-total failure of empathy for real people living this a less fortunate life today. Apocalyptic fiction works around that by describing a world in which a white, middle-class, educated man from Australia could find himself in that kind of situation. The line I’ve etched over thirty years between “those to whom bad things might happen” and “me and my family” is broken down and I end up half-choked by the thought of what might happen to me and mine if we’re not past caring when the oil runs out.

That’s what’s good about apocalyptic fiction.

I have an intermittent issue in SQL Server Management Studio when connecting to a SQL Server on my work LAN from a desktop on the same LAN. SSME intermittently cracks it and gives me a “Cannot generate SSPI context” message box, which prevents connection.

Google tells me that a lot of people receive this message occasionally, but none of the fixes I found worked for me.

Anyway, as it turns out, I only ever receive the error when I have a Citrix Access Gateway connection up. So I’m posting this blog entry in the hope that someday it saves someone some time. Disconnect from CAG when you don’t actively need it.

Task #1 today was to uninstall a vestigial Exchange 2010 installation that was using up space on our TFS box. Uninstall wouldn’t proceed until I’d cleaned up remaining mailboxes, etc., so I launched Exchange Management Console, intending to scorch some earth. When I clicked “Microsoft Exchange On-Premises”, I got this error:

[server FQDN] Connecting to remote server failed with the following error message : The WinRM client cannot process the request. The WinRM client tried to use Kerberos authentication mechanism, but the destination computer (server FQDN:80) returned an 'access denied' error. Change the configuration to allow Kerberos authentication mechanism to be used or specify one of the authentication mechanisms supported by the server. To use Kerberos, specify the local computer name as the remote destination. Also verify that the client computer and the destination computer are joined to a domain. To use Basic, specify the local computer name as the remote destination, specify Basic authentication and provide user name and password. Possible authentication mechanisms reported by server:     Negotiate For more information, see the about_Remote_Troubleshooting Help topic.

Turns out that as of 2010, the Exchange Management Console works by remoting PowerShell commands over to a http://servername:80/powershell virtual directory on the target server. Since this Exchange server had been set up (and after the last time anyone had used it), some port-juggling had been done on IIS on that box; SharePoint was now listening on port 80, and the default website (in which the powershell virtual directory was configured) had been moved off to port 8888.

The fix was simple: temporarily stop the SharePoint website (currently listening on port 80), create a new binding for the Default Web Site so that it would listen on port 80, and then re-launch Exchange Management Console.

Now, back to mailbox-razing.

I've written before about fumbling around with the Mandelbrot set.

When I first read about the Mandelbrot set, I had this feeling that I was a lucky guy. Something like this: What right do I have to know something so beautiful? How many of my ancestors died before computers (and before Mandelbrot), and so never had the chance to appreciate it? All but six. Of course, you can apply that logic in reverse... maybe I'll have just as many descendants who DO get to see it.

A couple of weeks ago, just before Mandelbrot died, I got that same feeling again watching this video of the very recently discovered Mandelbox.

It’s a 3-d relation of the Mandelbrot set, in that an iterative process rules points in or out of a set, and it’s the set that’s rendered. Unlike other 3-d Mandelbrotians (such as the Mandelbulb), though, it has a richness that draws me inwards even more than renderings of the Mandelbrot set.

Plus, if you save the music from only one hypnotic fractal video this year, make it Dajuin Yao’s “Satisfaction of Oscillation”.

I saw a pattern in the sand yesterday.

I’ve never noticed it before. It’s a kind of cross-hatching pattern on the part of the beach that’s recently been over-washed by waves.

The lines aren’t perpendicular – there’s maybe a 30 or 35 degree angle between them. If you bisect the lines, the result points pretty much straight down the slope.

If you look closely though, the lines aren’t perfectly straight – the channels meander around a bit.

You’ll have to excuse the over-enthusiastic Photoshop work – it was tough to bring out the patterns without abusing the source material.

My guess was that the pattern results from one of the angles in the sand grains’ crystalline structure getting somehow amplified up into a visible pattern, in the same way that table salt crystals are nice and regular. Maybe the “heavier” blunt end of a crystal would tend to be deposited downslope after flowing with the water some distance, leaving the “sharper” end up-slope (a little like the way contact lenses for people with astigmatism spin around to orient themselves correctly), and en masse this tendency causes rivulets to be preferentially dug out along certain angles.

Reading up more about what sand’s actually made of (hint: not that much of it is really silica crystals, at least not at this beach), I think I was wrong.

I hunted around a bit to see if anybody’s got any good theories, and it turns out there’s a bit of a literature about the phenomenon, going back at least to 1887. The patterns seem to be called “rhomboid ripple marks”. The first paper I found was behind a paywall, but it gave me a name to latch onto, which helped me find a recent draft paper by “O. Devauchelle, L. Malverti, E. Lajeunesse, C. Josserand, P.-Y. Lagree, F. Metivier”.

Highlights of the paper are (for me, at least):

• You get these patterns even with sorted, uniform sand (i.e. you don’t need any odd obstacles).
• It sounds as though the researchers reproduced the behaviour in the lab with spherical glass beads, so it’s not about the shape of the individual grains in the way I guessed.
• Similar patterns are seen in sedimentary rocks.
• The patterns have been observed up to the 10 metre scale.
• The authors saw the system (basically, a sandbed across which water was pumped) evolve in three different ways as they varied the parameters they could control:
  • Sometimes, the sand remained flat (I’ve seen this!)
  • Often, the sand formed rhomboid patterns (like those I saw yesterday)
  • Sometimes, the sand formed wave-like ripples (like those I’m used to from other beaches).
• There are beautiful images at the bottom of the PDF.
• The 1887 paper where W. C. Williamson described the phenomenon was titled “On Some Undescribed Tracks of Invertebrate Animals from the Yoredale Rocks, and on some Inorganic Phenomena, Produced on Tidal Shores, Simulating Plant Remains”. Awesome use of Intra-Sentence Capitals. I love it.

Motivation: I’m writing some F# code to solve Project Euler problem #14. The problem relates to the Collatz conjecture. It goes like this: start with a number – 3, say. Apply the following rules: if your number is odd, multiply by 3 and add 1. If your number is even, divide it by 2. Keep applying those rules until you end up with 1 or the universe reaches heat death. Tell me: of all the starting numbers from 1 to a million, which number takes the most turns before reaching 1?

Incidentally, this problem is typical of the Project Euler problems in that mathematical insight alone is not going to get you the answer (at least, not the level of mathematical insight of which I’m capable ). Also, in most cases, brute force number crunching won’t get you the answer in a reasonable time; it usually takes both mathematical insight and brute force number crunching to get to the answer.

Here’s my naive first attempt.

let rec CollatzLength n =
    if n = 1 then 1 else if n % 2 = 1 then CollatzLength (3 * n + 1) + 1 else CollatzLength (n / 2) + 1

let highestCollatzLengthUnder n =
    [1..n]
    |> Seq.map (fun x -> (x, CollatzLength x) )

let c = highestCollatzLengthUnder 1000000 |> Seq.max

printfn "%A" c

What’s going on here? All the magic is happening in the first two lines.

Line 1, “let rec CollatzLength n =” tells F# that we’re declaring a function called CollatzLength taking a single parameter named n, and that the function may recurse (“rec”). If we leave out the “rec”, the function body is not allowed to refer to itself by name.

Line 2 is the function body. It tells us that:

• the CollatzLength of 1 is 1 (because by definition, it’s the end of the sequence); and
• the CollatzLength of odd numbers is 1 (for the current number) plus the CollatzLength of 3 times the current number plus 1; and
• the CollatzLength for all other numbers (i.e. even numbers) is one plus the CollatzLength of two times the current number.

So, what happens when I run this code? It’s bad news: I get a StackOverflowException when I try to calculate the Collatz length for 113,383:

Process is terminated due to StackOverflowException.

Why is this happening? I thought that tail-recursion voodoo in F# would protect me in just this situation. Well, actually, no, it turns out.

Tail recursion is an optimisation that the compiler can apply to some, but not all, recursive functions. The optimisation can only be applied when the calling code contains no operations that must be performed after having called itself. Tail recursion avoids allocating a new stack frame for each “nested” recursive call by exploiting (where possible) the fact that the state of the parent is no longer required once it has recursed down another level. In this way, an arbitrary depth of tail recursion can be supported without adding anything to the call stack.

Imagine you’re the compiler, and you’re compiling a method that includes a recursive call. At the point of the recursive call, the normal, non-tail-recursion behaviour is for the original instance of the function’s state to remain on the stack while a new instance is reserved above it and used during the “inner” call. This is the normal behaviour in C# (although even the C# compiler will generate tailcall-friendly code in some cases, apparently, and the various JIT-ers may or may not get in there and play ball), and it is the behaviour in F# when tail recursion cannot be applied. It’s also the behaviour which, in my naive implementation above, is leading to a stack overflow when we nest somewhere between 100,000 and 1,000,000 levels deep.

But when applying the tail-recursion optimisation, the compiler observes that the parent’s state (on the stack) no longer influences the result it returns; there’s no need to keep it around, so the compiler exploits this by re-using the parent’s stack frame when executing the child. This continues on down through the recursive depths; no matter how far you go, you’ll still be executing in the original stack frame.

So, given all that, what’s the problem with my naive implementation? It’s pretty simple.

let rec CollatzLength n =
    if n = 1 then 1 else if n % 2 = 1 then CollatzLength (3 * n + 1) + 1 else CollatzLength (n / 2) + 1

In the recursive cases (i.e. where n != 1), CollatzLength recursively calls itself, and then adds one to the result before returning. Tail recursion cannot be applied, because CollatzLength keeps executing once its recursive call completes; it therefore needs its state to remain on the stack, meaning the tail recursion optimisation of re-using the parent’s stack frame for the child cannot be applied.

So let’s rewrite CollatzLength to permit the compiler to use tail recursion:

let CollatzLength n =
    let rec CollatzLengthInternal n countSoFar =
        if n = 1 then
            countSoFar
        else
            if n % 2 = 1 then
                CollatzLengthInternal (3 * n + 1) (countSoFar + 1)
            else
                CollatzLengthInternal (n / 2) (countSoFar + 1)
    CollatzLengthInternal n 1

What’s happened here?

1. From the first line “let CollatzLength n =”, we’ve dropped the “rec”, meaning that CollatzLength is no longer recursive; it no longer invokes itself.
2. We’ve simplified CollatzLength itself – its body consists of a single line (the last one above): “CollatzLengthInternal n 1”. That is, CollatzLength just evaluates to the result of calling CollatzLengthInternal, passing the number we’re calculating the Collatz length for, and a mysterious “1”.
3. We’ve added a new nested function “CollatzLengthInternal”. It accepts two parameters: the number we’re calculating the Collatz length for, and “countSoFar”, which tracks how many steps into the Collatz sequence we are. Another way of looking at it is that countSoFar always equals the depth of recursion into CollatzLengthInternal.
   1. If n is 1, CollatzLengthInternal just evaluates to countSoFar. From this it’s easy to see that (CollatzLength 1) will be equal to 1.
   2. If n is odd, CollatzLengthInternal evaluates to CollatzLengthInternal of 3n + 1, but with countSoFar increased by 1.
   3. And the same for even n, except that we take n / 2 in this case.

The key change to notice is that in both branches where CollatzLengthInternal calls itself, the result of that call is immediately returned; no further calculation happens with the result, and we immediately bubble back out to our parent.

So now, the compiler is free to apply the tail recursion optimisation. Let’s run the overall program (which calculates the CollatzLength for every number from 1 to 1,000,000), and see what happens.

…

Seems to be taking a while.

…

Bear with me.

…

Okay, attach in the debugger, and see what’s going on…

Well, from the call stack, I can see that highestCollatzLengthUnder is calling CollatzLength, which is calling CollatzLengthInternal, so we do seem to be doing some work. If I make highestCollatzLengthUnder the active stack frame, I can see that x is 113,383. Wha? That’s our nemesis from the non-tail-recursion version, back again! With a bit of thought, you can see what’s going on – for some reason, when calculating the Collatz sequence for 113,383, my code’s recursing arbitrarily deep. When not tail-recursive, that triggered a stack overflow. When tail-recursive, the code will happily run forever, nesting until… the heat death of the universe, I guess.

In the context of CollatzLengthInternal, I can see that countSoFar is currently 506,136,061, which is a fairly heroic level of recursion. In that same context, I can see that n is 0. There’s our problem! If n becomes 0, we’ll run forever, since it’s even, and for even numbers the successor in the sequence is n / 2, which for 0 is… 0 again.

So, somehow, in both implementations, I seem to have a bug which is causing us to get to 0 for sequence 113,383, but not for any earlier sequence.

First, let’s think about whether 0 could legitimately be in the Collatz sequence of an integer greater than 1. I don’t think so, because:

• n / 2 for any positive even number is a positive number.
• n * 3 + 1 for any positive odd number is a positive even number.

So what’s happening?

Ironically, for a non-tail recursive implementation, it’d be trivial to find out what predecessor in the sequence led to the first 0 – I’d just run to stack overflow in the debugger, then binary search through the stack looking for the first level where n was 0, then step back one level to see what its predecessor was. As you can see from the screenshot above, in tail-recursive land, you only see one level of CollatzLengthInternal in the stack, so that approach isn’t available. So let’s switch back to the non-tail recursive implementation and find the predecessor.

Well, that isn’t going to work. As you can see from the screenshot’s call stack, Visual Studio’s telling me “The maximum number of stack frames supported by Visual Studio has been exceeded.”

So, let’s fall back on a breakpoint where n = 0.

Yep, blargh. Immediately before n became 0, it was –1. How did that happen? This is starting to look like an overflow problem. Let’s just dump the whole sequence and have a look:

113383
340150
170075
510226
255113
…
1103160598
551580299
1654740898
827370449
-1812855948
-906427974
-453213987
-226606993
-113303496
-56651748
-28325874
-14162937
-7081468
-3540734
-1770367
-885183
-442591
-221295
-110647
-55323
-27661
-13830
-6915
-3457
-1728
-864
-432
-216
-108
-54
-27
-13
-6
-3
-1
0

Well, there’s the problem. We got as high as 1.6 billion (perilously close to the maximum signed 32-bit int around 2.1 billion), but didn’t actually overflow into negative territory until we landed on 827,370,449, which was odd, causing us to multiply by 3 and add 1, wrapping over into negative numbers.

So let’s switch to 64 bit ints and try again.

let CollatzLength(n) : int =
    let rec CollatzLengthInternal(n, countSoFar) =
        if n < 1L then
            failwith "blargh"
        else
            if n = 1L then
                countSoFar
            else
                let nextNumber = (if n % 2L = 1L then (3L * n + 1L) else (n / 2L))
                CollatzLengthInternal(nextNumber, countSoFar + 1)
    CollatzLengthInternal(n, 1)

let highestCollatzLengthUnder highest =
    [1..highest]
    |> Seq.map (fun x -> (int64)x)
    |> Seq.map (fun x -> (CollatzLength x, x))

let c = highestCollatzLengthUnder 1000000 |> Seq.max

printfn "%A" c 

Just by passing an int64 into CollatzLength, F# propagates that type change nicely. Irritatingly, though, I have to jam an L on the end of every integer literal, or else F# complains that I’m performing operations on a mixture of different integer types. In this case, I’d prefer that it widen the integer literals for me so that the caller can effectively specify the bit-ness based on the type of int it supplies, but it’s not the end of the world.

And there you have it. The answer to the question “which is the longest Collatz sequences starting with an integer betwen 1 and a million” is “the sequence starting with 837,799, which is 525 steps long”.

It would be cooler if…

This is one of those Project Euler problems which can be brute-forced. There’s no real mathematical insight in what I wrote above; it’s not much more than a translation of the problem statement into executable code.

I was hoping that the sequences would be long enough, and converge often enough, that it would be necessary to memoize the result of calling CollatzLengthInternal somehow in order to avoid re-tracing well-worn paths.

Imagine I’m dealing with some rough numbers – I’m in “order of magnitude” mode. Say I’m working out how many customers and orders my archaic DVD rental business needs to store in its customer database:

Customers: 1,000 (rough projected count by the end of the year)

Orders: 3,325 (based on current data which has an average 3.325 orders for each customer)

Say I’m uncomfortable dealing with such a precise number of orders, and I want to get back to a power of 10 while I’m just fooling around with rough volumes. Is 3,325 closer to 10,000 or 1,000?

Well, what’s halfway between 1,000 and 10,000? If you had to “round off” a measurement to the nearest order of magnitude, at what point would you say that the measurement’s now closer to 10,000 than 1,000?

In linear terms, it’s 1,000 + (10,000 – 1,000) / 2 = 5,500. But that’s an unsatisfying approach – intuitively, 5,500 is a lot “closer” to 10,000 than 1,000 if it’s a figure that’s been growing exponentially.

When talking in orders of magnitude, a better threshold between 1,000 and 10,000 is about 3,162.3, since:

10 ^ 3 = 1,000

10 ^ 3.5 ~= 3,162.3

10 ^ 4 = 10,000.

So, if you ever need to remove precision from a number for some reason, to get back to orders of magnitude from an overly precise estimate or measurement, the threshold is about 3.1623 times the next lower order of magnitude.

To calculate 10 ^ 3.5 using the subset of maths I (a) learned and (b) haven’t forgotten yet:

10 ^ 3.5

= 10 ^ (3 + 0.5)

= (10 ^ 3) * (10 ^ 0.5)

= (1,000) * sqrt(10)

~= 1,000 * 3.1623

~= 3,162.3

So in general, the threshold is the lower power of 10 times sqrt(10).