Sunday, 23 April 2017

One Does Simply Walk Into Mordor

... on the Tongariro Northern Circuit. This central North Island "Great Walk" is a loop circumnavigating Mount Ngauruhoe (aka "Mount Doom") and much of the Tongariro volcanic complex. The terrain varies but is mostly a mixture of lava fields and somewhat barren alpine plains scoured by old pyroclastic flows (most recently by the "super-colossal" ~1800-year-ago Taupo eruption). It doesn't take much imagination, or sophisticated marketing, to see it as (a peaceful and beautiful version of) Mordor.

We completed the Circuit yesterday, after four days of hiking. It's certainly possible to do it in three or even two days, but we took it easy and had time to do all the side tracks: the Tongariro summit track on day two (Mangatepopo Hut to Oturere Hut), the Ohinepango springs near Waihohonu on day three, and the Upper Tama Lake track on day four (Waihohonu Hut to Whakapapa Village).

Thank God, we had perfect weather. We also had a great time lounging around at the huts talking to other trampers of all ages, and even playing a variety of games. Overall it was another wonderful "Great Walk" experience. The only improvement would have been if one of the volcanoes was erupting, but you can't have everything!

The new Waihohonu Hut was impressive. It's probably the best DoC hut I've yet seen: multiple outdoor decks with picnic tables, well insulated, a very spacious common area with wood-burning stove, eight gas cooking stoves, solar-powered LED lighting, and even solar water heating!

After destroying a couple of cameras by getting them wet while tramping (only cheap point-and-shoots), I bought a waterproof camera. On this trip I took some underwater photos and they turned out quite well!

Wednesday, 5 April 2017

Rust Optimizations That C++ Can't Do (Version 2)

My last post was wrong in the details, so let me show a better example. Rust code:

pub extern fn foo(v: &u64, callback: fn()) -> u64 {
  let mut sum = 0;
  for _ in 0..100 {
    sum += *v;
    callback();
  }
  sum
}
C++ version here.

The inner loop of the Rust version turns into:

.LBB0_1:
        inc     ebx
        call    r14
        add     r12, r15
        cmp     ebx, 100
        jl      .LBB0_1
sum is in r12 and the evaluation of *v has been hoisted out of the loop with the result in r15. In the compiled C++ code the value has not been hoisted:
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        add     rbx, qword ptr [r15]
        call    r14
        dec     ebp
        jne     .LBB0_1

Of course the performance difference in this case would be negligible, but if *v was replaced with a more complicated expression, the difference would increase. (No, I don't know why the Rust code counts up instead of counting down like C++ to get slightly better code; someone should fix that.)

Here it's really clear that the semantics of Rust are making this optimization possible. In C++ v could be a reference to a global variable which is modified by the callback function, in which case hoisting the load would be incorrect.

Several people pointed out that with LTO/WPO a C++ compiler might be able to determine that such cases don't happen, in this case that no function passed into callback directly or indirectly modifies v. That's what I meant in my previous post by "a C++ compiler could do some analysis to show that can't happen" ... but as I continued, "those analyses don't scale". The larger and more complicated your code gets, the more likely it is that static analysis will fail to prove the invariants you care about. Sometimes, due to dynamic linking or run-time code generation, relevant code just isn't available to be analyzed. In other cases the analysis algorithms aren't sophisticated enough to prove what you care about (often because no such algorithm is known), or adequate algorithms exist but they were too expensive to deploy. Perhaps the worst cases for sophisticated global analysis are when the property you care about isn't even true, because you accidentally violated it in some part of the program, but you'll never know, because the only effect of that accident is that performance got a little bit worse somewhere else. (E.g. with this example if you accidentally change one of the callback functions to indirectly modify v, your hypothetical WPO compiler does a slightly worse job and you won't know why.)

What we need are language-level invariants that apply globally and support aggressive optimization using only local analysis. C++ has some, but Rust's are stronger. We also need those invariants to be checked and enforced, not just "it's undefined behavior if you do this"; (safe) Rust wins again on that.

Rust Optimizations That C++ Can't Do

Update dbaupp on Reddit pointed out that this particular example does not support the point I'm trying to make. I'll explain why below. I followed up with a new post with a better example.


Consider the Rust code

pub struct Foo {
    v1: u64,
    v2: u64,
}
pub fn foo(t: &Foo) -> u64 {
    t.v1 + t.v2
}

The stable Rust compiler, in Release mode, generates

_ZN8rust_out3foo17h154ee47e2fd80a9eE:
 leaq (%rdi,%rsi), %rax
 retq

Hang on! foo is supposed to take a reference, so shouldn't it take a pointer as its parameter and do two loads to get the values of v1 and v2? Instead it receives the values of v1 and v2 in %rdi/%rsi and adds them using leaq as a three-operand "add" instruction. The Rust compiler has decided (correctly) that even though you wrote a reference, in this case it's more efficient to just pass the parameter by value. This is good to know as a Rust developer; I can use references freely without worrying about whether it would be more efficient to pass the value directly.

C++ compilers can't do this optimization, for a couple of reasons. One reason is that C++ has a standard ABI that dictates how parameters are passed; it requires that references are always passed as pointers. A more interesting reason is that in general this optimization is not safe in C++. An immutable Rust reference promises that the referenced value does not change (except for some special cases involving UnsafeCell which are easily detected by the compiler), but not so for C++ const references; a "const" value can be modified through other mutable references, so copies induced by pass-by-value could change program behavior. For a simple case like this a C++ compiler could do some analysis to show that can't happen, but those analyses don't scale (e.g. if foo called, and was called by, unknown code, all bets are off).

Here Rust's strong control over aliasing is enabling improved optimization, not just improved safety. Update Actually as dbaupp points out, this optimization example is not specific to Rust. In fact, LLVM is doing it via local analysis (the sort I mentioned above), and clang++ produces the same results for the equivalent C++ code. In fact Rust in general would need to preserve references because you can convert a reference to a raw pointer and compare them for equality.

It's easy to find other examples, such as improved code motion and common subexpression elimination. I think with more study of large Rust programs, more investment in the Rust compiler, and tighter control over unsafe Rust, we will probably discover that Rust enables many more interesting optimizations.

One of the promises of hair-shirt functional languages was that referential transparency and other strong semantic guarantees would enable extremely aggressive optimizations, which would recover the performance lost by moving away from the stateful semantics of hardware. That didn't really work out, but with Rust we might get the aggressive optimizations on top of semantics that are already very efficient.

Sunday, 2 April 2017

Pararaha Valley

This weekend my son and I went out to camp overnight at Pararaha Valley in the Waitakere Ranges west of Auckland. We got dropped off on Piha Road at the north end of the Upper Huia Dam track, near the centre of the Ranges, and I planned to walk from there for 5-6 hours to reach the campsite near the west coast. After one and a half hours we reached the dam, and unfortunately discovered that the next section, Nugget Track, was closed to protect against kauri die-back. We had no choice but to retrace our steps for another hour and half. The Upper Huia track is pretty rough so at 2pm we were back where we started having used up a lot of energy :-(. (The trailhead has a map showing track closures but Nugget Track was not clearly marked as closed, so I'll contact the council about that.)

I wasn't sure what to do but decided we could probably reach the campsite before dark by following roads instead. So we walked west along Piha Road, south along Lone Kauri Rd towards Karekare, then crossed over into Pararaha Valley via the Buck Taylor Track. We got to the campsite around 6pm, having walked for about 7.5 hours at a fairly quick pace, so I was pretty tired. My son was fine :-).

The Pararaha Valley campsite is a lovely spot. I thought the swamp, er I mean wetland, at the bottom of the valley would mean a lot of mosquitoes but that wasn't a problem. The site documentation says that site has only stream water that needs to be treated, but there's a cooking shelter with roof runoff into a tank, and we drank the tank water untreated with no problems. (One of the other people at the campsite told me he'd drunk it two weeks ago while running the Hillary Trail (67km!).)

This morning we had a short two hour walk from the campsite up the coast along the beach to Karekare to get picked up. We got back to the city in time for church :-).

Let's Make NZ More Expensive For Tourists

I agree with Labour leader Andrew Little on this. Tourist numbers are growing, and making NZ a more expensive destination is a perfectly fair and rational alternative to fast-growing tourist numbers. NZ is never going to be a budget destination; better to be a high-price luxury destination with money reinvested to maintain and improve our facilities and environment, than a low-price destination with an environment degraded by too many tourists. I don't think we're anywhere close to being seen as a "rip-off".

FWIW many backpackers I meet while tramping are here for months; for these people the impact of a border-crossing tax would amortized. Fewer people making longer trips is also more climate-friendly.