Friday, 24 June 2016

Democracy Is Impressive

Two very surprising things happened in the last few months: US Republicans nominated Donald Trump as their candidate for President, and Britons voted to leave the EU. These events surprised me because they were fiercely opposed by the wealthy, politically powerful elites that are normally portrayed as running the world. I think it's amazing and inspiring that popular uprisings were able to overcome those forces. That fact should be celebrated, and recalled to refute defeatist rhetoric.

Unfortunately I can't celebrate the actual decisions themselves. I think that in the former case the people made a disastrous mistake, and in the latter case that remains to be seen. But the possibility that people will misuse their power is the price of democracy and all human freedom. I think it's a price worth paying.

Thursday, 23 June 2016

PlayCanvas Is Impressive

I've been experimenting on my children with different ways to introduce them to programming. We've tried Stencyl, Scratch, JS/HTML, Python, and CodeAcademy with varying degrees of success. It's difficult because, unlike when I learned to program 30 years ago, it's hard to quickly get results that compare favourably with a vast universe of apps and content they've already been exposed to. Frameworks and engines face a tradeoff between power, flexibility and ease-of-use; if it's too simple then it's impossible to do what you want to do and you may not learn "real programming", but if it's too complex then it may just be too hard to do what you want to do or you won't get results quickly.

Recently I discovered PlayCanvas and so far it looks like the best approach I've seen. It's a Web-based 3D engine containing the ammo.js (Bullet) physics engine, a WebGL renderer, a WYSIWYG editor, and a lot more. It does a lot of things right:

  • Building in a physics engine, renderer and visual editor gives a very high level of abstraction that lets people get impressive results quickly while still being easy to understand (unlike, say, providing an API with 5000 interfaces, one of which does what you want). Stencyl does this, but the other environments I mentioned don't. But Stencyl is only 2D; supporting 3D adds significant power without, apparently, increasing the user burden all that much.
  • Being Web-based is great. There's no installation step, it works on all platforms (I guess), and the docs, tutorials, assets, forkable projects, editor and deployed content are all together on the Web. I suspect having the development platform be the same as the deployment platform helps. (The Stencyl editor is Java but its deployed games are not, so WYS is not always WYG.)
  • Performance is good. The development environment works well on a mid-range Chromebook. Deployed games work on a new-ish Android phone.
  • So far the implementation seems robust. This is really important; system quirks and bugs make learning a lot harder, because novices can't distinguish their own bugs from system bugs.
  • The edit-compile-run cycle is reasonably quick, at least for small projects. Slow edit-compile-run cycles are especially bad for novices who'll be making a lot of mistakes.
  • PlayCanvas is programmable via a JS component model. You write JS components that get imported into the editor and are then attached to scene-graph entities. Components can have typed parameters that appear in the editor, so it's pretty easy to create components reusable by non-programmers. However, for many behaviors (e.g. autonomously-moving objects) you probably need to write code --- which is a good thing. It's a bit harder than Scratch/Stencyl but since you're using JS you have more power and develop more reusable skills, and cargo-culting and tweaking scripts works well. You actually have access to the DOM if you want although mostly you'd stick to the PlayCanvas APIs. It looks like you could ultimately do almost anything you want, e.g. add multiplayer support and voice chat via WebRTC.
  • PlayCanvas has WebVR support though I haven't tried it.
  • It's developed on github and MIT licensed so if something's broken or missing, someone can step in and fix it.

So far I'm very impressed and my child is getting into it.

Friday, 17 June 2016

Managing Vast, Sparse Memory On Linux

For a problem I'm working on, an efficient solution is to use a 32GB array, most of whose entries are unused. Fortunately this is no problem at all on 64-bit Linux using a couple of simple tricks.

The first trick is to allocate the array using the little-known (to me) MAP_NORESERVE option:

p = mmap(nullptr, 32 * 1024 * 1024 * 1024, PROT_READ | PROT_WRITE,
              MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0));
(I thought this was the default on Linux, so I'm not sure why it's needed, but it is with 4.5.5-201.fc23.x86_64 at least. Oddly enough, if I omit that flag and just do two 16GB mmaps, that works too.) Now you can write to that region and only the pages you write to will actually be allocated. Good times.

Now, once in a while I want to clear that memory or just some subsections of it. memset(array, 0, size) is out of the question since it would take a very long time and would also probably cause all those pages to be allocated, killing my process if I'm lucky and the entire system if I'm less lucky.

Fortunately we have madvise(array, size, MADV_DONTNEED)! For a MAP_ANONYMOUS mapping like ours, this delightful system call simply frees all the pages in the range and instructs the kernel to use fresh zero pages next time the memory is read or written. Not only is it theoretically efficient, it's fast in practice. I can touch 10,000 scattered pages in my 32GB array and then zero the entire array with one MADV_DONTNEED in 12ms total.

It would be nice if tricks like these worked for pages with values other than just zeroes. For example, Firefox sometimes needs large allocations filled with 0xFF000000 for graphics buffers, or special bit patterns representing "poisoned" memory for security purposes. I think you could implement something like that using userfaultfd or mapping a file from a custom FUSE filesystem, but they would probably be significantly slower.

Wednesday, 15 June 2016

Nastiness Works

One thing I experienced many times at Mozilla was users pressuring developers with nastiness --- ranging from subtle digs to vitriolic abuse, trying to make you feel guilty and/or trigger an "I'll show you! (by fixing the bug)" response. I know it happens in most open-source projects; I've been guilty of using it myself.

I particularly dislike this tactic because it works on me. It really makes me want to fix bugs. But I also know one shouldn't reward bad behavior, so I feel bad fixing those bugs. Maybe the best I can do is call out the bad behavior, fix the bug, and avoid letting that same person use that tactic again.

Perhaps you're wondering "what's wrong with that tactic if it gets bugs fixed?" Development resources are finite so every bug or feature is competing with others. When you use nastiness to manipulate developers into favouring your bug, you're not improving quality generally, you're stealing attention away from other issues whose proponents didn't stoop to that tactic and making developers a little bit miserable in the process. In fact by undermining rational triage you're probably making quality worse overall.

Monday, 13 June 2016

"Safe C++ Subset" Is Vapourware

In almost every discussion of Rust vs C++, someone makes a comment like:

the subset of C++14 that most people will want to use and the guidelines for its safe use are already well on their way to being defined ... By following the guidelines, which can be verified statically at compile time, the same kind of safeties provided by Rust can be had from C++, and with less annotation effort.
This promise is vapourware. In fact, it's classic vapourware in the sense of "wildly optimistic claim about a future product made to counter a competitor". (Herb Sutter says in comments that this wasn't designed with the goal of "countering a competitor" so I'll take him at his word (though it's used that way by others). Sorry Herb!)

(FWIW the claim quoted above is actually an overstatement of the goals of the C++ Core Guidelines to which it refers, which say "our design is a simpler feature focused on eliminating leaks and dangling only"; Rust provides important additional safety properties such as data-race freedom. But even just the memory safety claim is vapourware.)

To satisfy this claim, we need to see a complete set of statically checkable rules and a plausible argument that a program adhering to these rules cannot exhibit memory safety bugs. Notably, languages that offer memory safety are not just claiming you can write safe programs in the language, nor that there is a static checker that finds most memory safety bugs; they are claiming that code written in that language (or the safe subset thereof) cannot exhibit memory safety bugs.

AFAIK the closest to this C++ gets is the Core Guidelines Lifetimes I and II document, last updated December 2015. It contains only an "informal overview and rationale"; it refers to "Section III, analysis rules (forthcoming this winter)", which apparently has not yet come forth. (I'm pretty sure they didn't mean the New Zealand winter.) The informal overview shows a heavy dependence on alias analysis, which does not inspire confidence because alias analysis is always fragile. The overview leaves open critical questions about even trivial examples. Consider:

unique_ptr<int> p;
void foo(const int& v) {
  p = nullptr;
  cout << v;
}
void bar() {
  p = make_unique(7);
  foo(*p);
}
Obviously this program is unsafe and must be forbidden, but what rule would reject it? The document says
  • In the function body, by default a Pointer parameter param is assumed to be valid for the duration of the function call and not depend on any other parameter, so at the start of the function lset(param) = param (its own lifetime) only.
  • At a call site, by default passing a Pointer to a function requires that the argument’s lset not include anything that could be invalidated by the function.
Clearly the body of foo is OK by those rules. For the call to foo from bar, it depends on what is meant by "anything that could be invalidated by the function". Does that include anything reachable via global variables? Because if it does, then you can't pass anything reachable from a global variable to any function by reference, which is crippling. But if it doesn't, then what rejects this code?

Update Herb points out that example 7.1 covers a similar situation with raw pointers. That example indicates that anything reachable through a global variable cannot be passed by to a function by raw-pointer or reference. That still seems like a crippling limitation to me. You can't, for example, copy-construct anything (indirectly) reachable through a global variable:

unique_ptr<Foo> p;
void bar() {
  p = make_unique<Foo>(...);
  Foo xyz(*p); // Forbidden!
}

This is not one rogue example that is easily addressed. This example cuts to the heart of the problem, which is that understanding aliasing in the face of functions with potentially unbounded side effects is notoriously difficult. I myself wrote a PhD thesis on the subject, one among hundreds, if not thousands. Designing your language and its libraries from the ground up to deal with these issues has been shown to work, in Rust at least, but I'm deeply skeptical it can be bolted onto C++.

Q&A

Aren't clang and MSVC already shipping previews of this safe subset? They're implementing static checking rules that no doubt will catch many bugs, which is great. They're nowhere near demonstrating they can catch every memory safety bug.

Aren't you always vulnerable to bugs in the compiler, foreign code, or mistakes in the safety proofs, so you can never reach 100% safety anyway? Yes, but it is important to reduce the amount of trusted code to the minimum. There are ways to use machine-checked proofs to verify that compilation and proof steps do not introduce safety bugs.

Won't you look stupid when Section III is released? Occupational hazard, but that leads me to one more point: even if and when a statically checked, plausibly safe subset is produced, it will take significant experience working with that subset to determine whether it's viable. A subset that rejects core C++ features such as references, or otherwise excludes most existing C++ code, will not be very compelling (as acknowledged in the Lifetimes document: "Our goal is that the false positive rate should be kept at under 10% on average over a large body of code").

Sunday, 12 June 2016

Mt Pirongia

At the end of April we did an overnight tramp up Mt Pirongia. Mt Pirongia is an old volcano southwest of Hamilton, not far from Kawhia on the west coast of the North Island. Its summit is 959m above sea level, most of the mountain is covered in thick bush, and there's a nice new DoC hut near the summit. It's only about two hours drive from Auckland so it's one of the closest hut tramps; I'd been thinking about doing it for years but had heard it was "hard core", and so put it off until my children were older.

On the Saturday we had pretty good weather the whole way. Up to about 700m it was pretty easy going but the central part of the mountain comprises several independent peaks, so there are numerous very steep up-and-down sections, some more climbing than walking, some with chains to help. It's tiring but there's not too much of it. It took us about five hours to get all the way to the hut. The views were spectacular; you can see out to the ocean to the west, and across the Waikato and King Country to the east. Supposedly on a clear day you can see Mt Taranaki and the central volcanic plateau, but it was too hazy for us.

The new hut is good, though it doesn't have the solar-powered LED lighting that many other new huts have. It was lovely to watch the evening descend. Because it was a one-night-only tramp, we brought better food than normal --- steaks, puddings, and bacon and eggs for breakfast. My children introduced the rest of our party to Bang! and everyone had a great time.

On Sunday we were in cloud most of the way down, but it was still lovely and took us about four hours. Overall it was, as I'd heard before, a little "hard core" and probably not the best first-time overnight tramp (the Pinnacles in Coromandel is still the best first-time overnight hut tramp from Auckland, IMHO), but well worth doing.

Whanganui River Journey

Back in April I did the Whanganui River Journey with some friends and family. This is branded as one of New Zealand's "Great Walks", but it's actually five days of canoeing from Taumarunui in the central North Island to Pipiriki, covering 145km. We stayed at campsites for three nights and at the John Coull Hut along the way.

I hadn't done a river trip like this before but I really enjoyed it. Like pretty much everyone else on the river (apart from a few jetboats) we were using open-top Canadian canoes. We were able to carry more gear than we would have while tramping. It's less tiring overall but my arms seldom get such a workout. The scenery is quite different; no vistas from mountain-tops, but seeing gorges and river valleys from the river has its own charm. The river gives you regular challenges as you shoot rapids and risk capsizing. Three of our four canoes had a capsize during the trip, which is actually no big deal, and in retrospect was an experience worth having :-). I discovered that there's a big difference between "container waterproof enough to keep rain out" and "container waterproof while submerged in a fast-flowing river".

Along the way we stopped for a walk to the "Bridge To Nowhere", a big concrete bridge across a valley in the middle of the bush. A road was built to it to support settlement in the area, but was too difficult to maintain so eventually was abandoned and the settlers moved out. Apparently exactly one car ever drove over the bridge. It was unfortunate for the settlers, many of whom were World War I veterans, but Whanganui National Park is a real treasure now.

Our canoe rental company (Blazing Paddles) was good. They picked us up at Pipiriki and drove us and our gear back to base at Taumarunui. That road trip took a couple of hours and was a lot of fun; I talked extensively to the driver, whose family has been in the central North Island area (one of my favourite places) for a hundred years. There are also some spectacular views of the volcanic plateau and the mighty three volcanoes Tongariro, Ngauruhoe and Ruapehu.

The photos here were taken by my friends after my own camera got wet on the first day...