Wednesday, 31 August 2016

Avoiding Cache Writebacks For Freed Memory

I wonder how much memory traffic is generated by the CPU writing out evicted cache lines for memory locations the application knows are dead because they belong to freed memory. This would be interesting to measure. If it's significant, then perhaps the application (or some lower level of the software stack) should be trying more aggressively to reuse freed memory, or perhaps it would be valuable to have hardware support for invalidating cache lines without writing them back. Though I suppose the latter case is problematic since it would make buggy software nondeterministic. At the OS level Linux has madvise(..., MADV_DONTNEED) to clear unwanted pages, but I'm not aware of anything analogous for the CPU cache.

Update Xi Yang pointed me at a paper on exactly this topic: Cooperative Cache Scrubbing.

For modern Java programs, 10 to 60% of DRAM writes are useless, because the data on these lines are dead - the program is guaranteed to never read them again.
That's a lot more than I expected! It would be very interesting to know what these numbers are for C++ or Rust programs. If the numbers hold up, it sounds like it would be worth adding some kind of hardware support to quash these writes. It would be nice to avoid the problem of nondeterministic behavior for buggy software; I wonder if you could have a "zero cache line" instruction that sets the cache line to zero at each level of cache, marks the lines as clean, and writes zeroes to RAM, all more efficiently than a set of non-temporal writes of zero. Actually you might want to be able to do this for a large range of virtual addresses all at once, since programs often free large chunks of memory.

Wednesday, 24 August 2016

Random Thoughts On Rust: And IDEs

I've always liked the idea of Rust, but to tell the truth until recently I hadn't written much Rust code. Now I've written several thousand lines of Rust code and I have some more informed comments :-). In summary: Rust delivers, with no major surprises, but of course some aspects of Rust are better than I expected, and others worse.

cargo and

cargo and are awesome. They're probably no big deal if you've already worked with a platform that has similar infrastructure for distributing and building libraries, but I'm mainly a systems programmer which until now meant C and C++. (This is one note in a Rust theme: systems programmers can have nice things.) Easy packaging and version management encourages modularising and publishing code. Knowing that publishing to gives you some protection against language/compiler breakage is also a good incentive.

There's been some debate about whether Rust should have a larger standard library ("batteries included"). IMHO that's unnecessary; my main issue with is discovery. Anyone can claim any unclaimed name and it's sometimes not obvious what the "best" library is for any given task. An "official" directory matching common tasks to blessed libraries would go a very long way. I know from browser development that an ever-growing centrally-supported API surface is a huge burden, so I like the idea of keeping the standard library small and keeping library development decentralised and reasonably independent of language/compiler updates. It's really important to be able to stop supporting an unwanted library, letting its existing users carry on using it without imposing a burden on anyone else. However, it seems likely that in the long term will accumulate a lot of these orphaned crates, which will make searches increasingly difficult until the discovery problem is addressed.


So far I've been using Eclipse RustDT. It's better than nothing, and good enough to get my work done, but unfortunately not all that good. I've heard that others are better but none are fantastic yet. It's a bit frustrating because in principle Rust's design enables the creation of extraordinarily good IDE support! Unlike C/C++, Rust projects have a standard, sane build system and module structure. Rust is relatively easy to parse and is a lot simpler than C++. Strong static typing means you can do code completion without arcane heuristics. A Rust IDE could generate code for you in many situations, e.g.: generate a skeleton match body covering all cases of a sum type; generate a skeleton trait implementation; one-click #[derive] annotation; automatically add use statements and update Cargo.toml; automatically insert conversion trait calls and type coercions; etc. Rust has quite comprehensive style and naming guidelines that an IDE can enforce and assist with. (I don't like a couple of the standard style decisions --- the way rustfmt sometimes breaks very().long().method().call().chains() into one call per line is galling --- but it's much better to have them than a free-for-all.) Rust is really good at warning about unused cruft up to crate boundaries --- a sane module system at work! --- and one-click support for deleting it all would be great. IDEs should assist with semantic versioning --- letting you know if you've changed stable API but haven't revved the major version. All the usual refactorings are possible, but unlike mainstream languages you can potentially do aggressive code motion without breaking semantics, by leveraging Rust's tight grip on side effects. (More about this in another blog post.)

I guess one Rust feature that makes an IDE's job difficult is type inference. For C and C++ an IDE can get adequate information for code-completion etc by just parsing up to the user's cursor and ignoring the rest of the containing scope (which will often be invalid or non-existent). That approach would not work so well in Rust, because in many cases the types of variables depend on code later in the same function. The IDE will need to deal with partially-known types and try very hard to quickly recover from parse errors so later code in the same function can be parsed. It might be a good idea to track text changes and reuse previous parses of unchanged text instead of trying to reparse it with invalid context. On the other hand, IDEs and type inference have some synergy because the IDE can display inferred types.

Saga Of The Exiles

When I was younger I was a huge fan of Julian May's sci-fi/fantasy Saga Of The Exiles. I've re-read some of it recently to see if it's really all that good. It is, and I highly recommend it. The setting is strong: in the not-far future, humans develop magical psychic powers and join the Milieu, a society of similarly-psychic alien races. This society's misfits are sent through a one-way time portal six million years into Earth's past --- where it turns out to be already occupied by warring alien races with similar powers. May places some deeply interesting characters into this setup, then charts their adventures over the course of the four main books and introduces more major elements. Another book, Intervention, explores the events leading from our present (well, 1980's present) to joining the Milieu, and caps off the Exiles story arc with a truly epic twist.

In my opinion, it's all very well done. May seems to be a polymath; according to Wikipedia she wrote thousands of encyclopedia articles about science, and also helped write a Catholic catechism. Along with swords, psycho-sorcery and sci-fi trappings, her stories are full of convincing geology, flora, and fauna, and she pulls in some theology too.

In addition to the books mentioned above, she wrote a "Milieu trilogy" set after the Intervention. I found these disappointing and would recommend not reading them. The main problem is that the key events in that period have already been outlined in the other books; to give the Milieu trilogy some suspense, she adds new plot elements that don't seem to fit, and then the really important events are given short shrift.

For some reason these books seem to be less well known than contemporaneous opuses such as The Belgariad or The Chronicles of Thomas Covenant. That's a shame. I think they'd be great material for a TV series. You'd need an enormous special-effects budget, but there's lots of material to enthrall audiences (and yes, plenty of sex and violence), and more big and original ideas than the usual "Tolkien with the serial numbers filed off".

Tuesday, 16 August 2016

False Accusations

One of the problems with false or hyperbolic accusations is that they encourage your target to do the very thing you falsely accuse them of doing. E.g., if the company isn't collecting private data but you make people believe they are, then perhaps they might as well collect it. If you actually care about the issue in question, this is likely to be counterproductive to your cause.

I understand the urge to lacerate an opponent and I've been guilty of it myself, but I'll try to keep the above in mind.

Another reason to restrain oneself is given by C. S. Lewis:

“Suppose one reads a story of filthy atrocities in the paper. Then suppose that something turns up suggesting that the story might not be quite true, or not quite so bad as it was made out. Is one's first feeling, 'Thank God, even they aren't quite so bad as that,' or is it a feeling of disappointment, and even a determination to cling to the first story for the sheer pleasure of thinking your enemies are as bad as possible? If it is the second then it is, I am afraid, the first step in a process which, if followed to the end, will make us into devils. You see, one is beginning to wish that black was a little blacker. If we give that wish its head, later on we shall wish to see grey as black, and then to see white itself as black. Finally we shall insist on seeing everything -- God and our friends and ourselves included -- as bad, and not be able to stop doing it: we shall be fixed for ever in a universe of pure hatred.”

Sunday, 7 August 2016

Why I Don't Watch "Game Of Thrones"

(A bit of a followup on my last post...) On Friday night someone was talking about Game Of Thrones and, seeing as I'm a D&D fan and generally enthusiastic about faux-medieval fantasy, I felt obliged to explain why I don't watch it. Not wanting to sound sanctimonious or self-righteous, I explained "I've heard it has more sex and violence than I can handle" ... an answer hopefully winsome but quite true!

A few clarifications for the record... Most of my Christian friends watch it and I don't judge them over it. I know my favourite pastor watches it! It may be fine for them. In this matter I'm probably the weaker brother that Paul talks about in Romans 14.

One thing that turned me off it was an on-set report I read, where the director made it clear the sex was aimed to titillate. I fear I'd end up watching it for the wrong reasons.

If I really cared to participate in the pop-culture phenomenon, I'd read the books. Turns out I don't. (Yes, I know the books are full of sex and violence too, but to some extent they're limited by one's own imagination.) I probably will read the books anyway, because I've heard they're good, but I have a long reading list. Also I prefer to invest my time in long sagas only if I'm confident they end satisfactorily (X-Files, I'm looking at you!) so I should probably hold out until George R. R. Martin gets it done.

Changing Attitudes To Pornography

For most of my life, mainstream culture in the English-speaking West has been highly accepting of pornography. Mass media near-universally portrays its production and consumption as benign, even positive. I read a respectable parenting book advocating that parents deliberately introduce pornography to their sons in a controlled manner. Those of us who label pornography as unhealthy have been marginalised as anti-sex, anti-joy prudes who seek control over others for envious or selfish reasons. Even just avoiding it oneself is viewed as slightly pathological.

Things seem to be changing, in some parts of NZ culture. Over the years the NZ Herald news site has run quite a few stories, on and off, on the damage done by addiction to online porn. It seems to me that these stories have been increasing in frequency. More interestingly, in the old days almost every author felt required to include some disclaimer along the lines of "I'm no prude, but ---". (No-one wants to appear guilty of that greatest of sins!) Now I often don't even see those disclaimers anymore.

I hope we reach the point soon where most of the culture can take the online porn problem seriously. It's difficult to tackle for so many reasons :-(. Technological development is rapidly outpacing the culture's and our brains' ability to adjust; we're still coming to grips with the effects of ubiquitous access to images and video, but VR porn is just around the corner. Some of the groups most opposed to porn --- the traditionally religious, and some decidedly anti-religious feminist groups --- find it difficult to cooperate. (On the flip side, porn proponents contain an unholy alliance of "boys will be boys" conservatism with anything-goes modern libertinism, who have no trouble at all cooperating!) A lot of the opposition to porn has been crippled by an attraction to blanket censorship that is ineffective and has dangers of its own.

I'd like to see more client-side tools to help people control their exposure to pornography. That includes hiding clickbait links to temptation as well as actual pornographic content. I'd like to see better education from parents and in schools about the harmful effects of pornography. I'd like to see, across the cultural spectrum, recognition that the way some men view women as primarily sex objects is a huge problem, and pornography is partly to blame. I think we may be slowly moving in the right direction, at least in some places.

Monday, 1 August 2016

The True Story Of "Amazing Grace"

"Amazing Grace" is a great hymn. We sang it at my wedding, because it's distinctively Christian but non-Christians are still comfortable singing it. The story behind is is also great, and I've heard preachers summarize it a few times: slave trader John Newton converts to Christianity, repudiates slavery, and writes "Amazing Grace" to express his remorse and celebrate God's grace. That summary is technically true, but it doesn't do justice to the story.

Most importantly, that summary obscures the fact that John Newton remained involved in the slave trade for many years after his apparent conversion. It wasn't immediately obvious to him that his occupation was incompatible with his Christian commitments --- no doubt partly because his livelihood depended on it not being obvious. Clearly, though, over time he came to completely repudiate slavery and see his former career as a dire sin. His wretched personal history made him acutely aware of God's grace and made him an influential advocate for abolition.

There are many other interesting details. As a young seaman he was so ill-disciplined he was, incredibly, punished for excessive profanity. For eighteen months he was practically enslaved himself in West Africa. He went through several cycles of drawing near to God and relapsing into terrible sins. It's a long story of a great sinner gradually becoming a great saint.