Saturday, 3 November 2018

On learning Go and a comparison with Rust

I spoke at the AKL Rust Meetup last month (slides) about my side project doing data mining in Rust. There were a number of engineers from Movio there who use Go, and I've been keen for a while to learn Go and compare it with Rust and Python for my data mining side projects, so that inspired me to knuckle down and learn Go.

Go is super simple. I was able to learn the important points in a couple of evenings by reading GoByExample, and I very quickly had an implementation of the FPGrowth algorithm in Go up and running. For reference, I also have implementations of FPGrowth in Rust, PythonJava and C++

As a language, Go is very simple. The language lacks many of the higher level constructs of other modern languages, but the lack of these make it very easy to learn, straightforward to use, and easy to read and understand. It feels similar to Python. There's little hidden functionality; you can't overload operators for example, and there's no generics or macros, so the implementation for everything has to be rewritten for every type. This gets tedious, but it does at least mean the implementation for everything is simple and explicit, the code right in front of you.

I also really miss the functional constructs that are built into many other languages, like mapping a function over a sequence, filter, any, all, etc. With Go, you need to reimplement these yourself, and because there's no generics (yet), you need to do it for every type you want to use these on. The lack of generics is also painful when writing custom containers.

Not being able to key a map with a struct containing a slice was a nuisance for my problem domain; I ended up having to write a custom tree-set data structure due to this; though it was very easy to write thanks to in built maps. Whereas Rust, or even Java, has traits/functions you can implement to ensure things can be hashed.

The package management for Go feels a bit tacked on; requiring all Go projects to be in a GO_PATH seems a consequence of not having a tool the equal of Rust's Cargo coupled with something like crates.io.

And Go's design decision to use the case of a symbol's first letter to express whether that symbol is public or private is annoying. I have a long standing habit of using foo as the name for a single instance of type Foo, but that pattern doesn't work in Go. The consequence of this design choice is it leads programmers to using lots of non-descriptive names for things. Like single letter variable names. Or the dreaded myFoo.

The memory model of Go is simple, and again I think the simplicity is a strength of the language. Go uses escape analysis to determine whether a value escapes outside of a scope, and moves such values to the heap if so. Go also dynamically grows goroutines' stacks, so there's no stack overflow. Go is garbage collected, so you don't have to worry about deallocating things.

I found that thinking of values as being on the heap or stack wasn't a helpful mental model with Go. Once I started to think of variables as references to values and values being shared when I took the address (via the & operator), the memory model clicked.

I think Go's simple memory model and syntax make it a good candidate as a language to teach to beginner programmers, more so than Rust.

The build times are impressively fast, particularly on an incremental build. After the initial build of my project, I was getting build times to fast to perceive on my 2015 13" MBP, which is impressive. Rust has vastly slower build time.

The error messages produced by the Go compiler were very spartan. The Rust compiler produces very helpful error messages, and in general I think Rust is leading here.

Go has a very easy to use profile package which you can embed in your Go program. Combined with GraphViz, it produces simple CPU utilization graphs like this one:
CPU profile graph produced by Go's "profile" package and GraphViz.

Having an easy to use profiler bundled with your app is a huge plus. As we've seen with Firefox, this makes it easy for your users to send you profiles of their workloads on their own hardware. The graph visualization is also very simple to understand.

The fact that Go lacks the ability to mark variables/parameters as immutable is mind-boggling to me. Given the language designers came from C, I'm surprised by this. I've written enough multi-threaded and large system code to know the value of restricting what can mess with your state.

Goroutines are pretty lightweight and neat. You can also use them to make a simple "generator" object; spawn a goroutine to do your stateful computation, and yield each result by pushing it into a channel. The consumer can block on receiving the next value by receiving on the channel, and the producer will block when it pushes into a channel that's not yet been received on. Note you could do this with Rust too, but you'd have to spawn an OS thread to do this, which is more heavy weight than a goroutine, which are basically userspace threads.

Rust's Rayon parallelism crate is simply awesome, and using that I was able to easily and effectively parallelize my Rust FPGrowth implementation using Rayon's parallel-iterators. As best as I can tell, Go doesn't have anything on par with Rayon for parallelism. Go's goroutines are great for lightweight concurrency, but they don't make it as easy as using's Rayon's par_iter() to trivially parallelize a loop. Note, parallelism is not concurrency.

All of my attempts to parallelize my Go FPGrowth implementation as naively as I'd parallelized my Rust+Rayon implementation resulted in a slower Go program. In order to parallelize FPGrowth in Go, I'd have to do something complicated, though I'm sure channels and goroutines would make that easier than in a traditional language like Java or C++.

Go would really benefit from something like Rayon, but unfortunately due to Go's lack of immutability and a borrow checker, it's not safe to naively parallelize arbitrary loops like it is in Rust. So Rust wins on parallelism. Both languages are strong on concurrency, but Rust pulls ahead due to its safety features and Rayon.

Comparing Rust to Go is inevitable... Go to me feels like the spiritual successor to C, whereas Rust is the successor to C++.

I feel that Rust has a learning curve, and before you're over the hump, it can be hard to appreciate the benefits of the constraints Rust enforces. For Go, you get over that hump a lot sooner. Whereas with Rust, you get over that hump a lot later, but the heights you reach after are much higher.

Overall, I think Rust is superior, but if I'd learned Go first I'd probably be quite happy with Go.

Thursday, 1 March 2018

Firefox Media Playback Team Review Policy

Reviews form a central part of how we at Mozilla ensure engineering diligence. Prompt, yet thorough, reviews are also a critical component in maintaining team velocity and productivity. Reviews are also one of the primary ways that a distributed organization like Mozilla does its mentoring and development of team members.

So given how important reviews are, it pays to be deliberate about what you're aiming for.

The senior members of the Firefox Media Playback team met in Auckland in August 2016 to codify the roadmap, vision, and policy for the team, and and one of the things we agreed upon was our review policy.

The policy has served us well, as I think we've demonstrated with all we've achieved, so I'm sharing it here in the hope that it inspires others.
  • Having fast reviews is a core value of the media team.
  • Review should be complete by end of next business day.
  • One patch for one logical scope or change. Don't cram everything into one patch!
  • Do not fix a problem, fix the cause. Workarounds are typically bad. Look at the big picture and find the cause.
  • We should strive for a review to be clear. In all cases it should be clear what the next course of action is.
  • Reviews are there to keep bad code out of the tree.
  • Bad code tends to bring out bad reviews.
  • Commit message should describe what the commit does and why. It should describe the old bad behaviour, and the new good behaviour, and why the change needs to be made.
  • R+ means I don’t want to see it again. Maybe with comments that must be addressed before landing.
  • R- means I do want to see it again, with a list of things to fix.
  • R canceled means we’re not going to review this.
  • Anyone on the media team should be expected to complete a follow up bug.
  • It’s not OK for a reviewer to ask a test to be split out from a changeset, provided the test is related to the commit. By the time a patch gets to review, splitting the test out doesn’t create value, just stop-energy.
  • Review request. If response is slow, ping or email for a reminder, otherwise find another reviewer.
  • Don’t be afraid to ask when the review will come. The reply to “when” can be “is it urgent?”
  • Everyone should feel comfortable pointing out flaws/bugs as a “drive by”.
  • Give people as much responsibility as they can handle.
  • Reviewers should make it clear what they haven’t reviewed.
  • American English spelling, for comments and code.
  • Enforce Mozilla coding style, and encourage auto formatters, like `./mach clang-format`.
  • Use reviewboard. Except when you can’t, like security patches.

Friday, 12 January 2018

Not every bit of code you write needs to be optimal

It's easy to fall into the trap of obsessing about performance and try to micro-optimize every little detail in the code you're writing. Or reviewing for that matter. Most of the time, this just adds complexity and is a waste of effort.

If a piece of code only runs a few (or even a few hundred) times a second, a few nanoseconds per invocation won't make a significant difference. Chances are the performance wins you'll gain by micro optimizing such code won't show up on a profile.

Given that, what should you do instead? Code is read and edited much more than it is written, so optimize for readability, and maintainability.

If you find yourself wondering whether a piece of code is making your program slow, one of the first things you should do is fire up a profiler, and measure it. Or add telemetry to report how long your function takes in the wild. Then you can stop guessing, and start doing science.

If data shows that your code is slow, by all means optimize it. But if not, you can get more impact out of your time by directing your efforts elsewhere.


Sunday, 23 July 2017

How to install Ubuntu 17.04 on Dell XPS 15 9550

I had some trouble installing Ubuntu 17.04 to dual-boot with Windows 10 on my Dell XPS 15 9550, so documenting here in case it helps others...

Once I got Ubuntu installed, it runs well. I'm using the NVIDIA proprietary driver, and I've had no major issues with hardware yet so far.

Most of the installation hurdles for me were caused by Ubuntu not being able to see the disk drive while it was operating in Raid mode, and UEFI/Secure Boot seemed to block the install somehow.

The trick to getting past these hurdles was to set Windows to boot into Safe Mode and then switch the disk drive to AHCI and disable UEFI in the BIOS before booting back into Windows in Safe Mode, and then switching Windows back to non-Safe Mode.

I found rcasero's notes on installing Ubuntu on Dell XPS 15 9560 useful.

Detailed steps to install...
  1. (If your Windows partition is encrypted, print out a copy of your BitLocker key. You'll need to enter this on boot after changing anything in your BIOS.
  2. Boot into Windows 10.
  3. I also needed to resize my main Windows partition from inside Windows; the Ubuntu installer seemed unable to cope with resizing my encrypted Windows partition for some reason. You can resize your main Windows partition using Windows' "Create or edit Disk Partitions" tool.
  4. Configure Windows to boot into safe mode: Press Win+R and run msconfig.exe > Boot > Safe Mode. Reboot.
  5. Press the F12 key while the BIOS splash screen comes up. Just repeatedly pressing it while the machine is booting seems to be the most reliable tactic.
  6. In the BIOS menu, BIOS Setup > System Configuration > SATA Operation, change "RAID On" to "AHCI".
  7. In the BIOS menu, disable Secure Boot.
  8. Reboot into Windows. You'll need to enter your BitLocker key to unlock the drive since the BIOS changed. Windows will boot into Safe Mode. If you don't have your Windows install set to boot into Safe Mode, you'll get a BSOD.
  9. Once you've booted into Windows Safe Mode, you can configure Windows to boot in normal (non-Safe Mode) with msconfig.exe > Boot > Safe Mode again.
  10. Reboot with your Ubuntu USB Live Disk inserted, and press F12 while booting to select to boot from the Live USB disk.
  11. The rest of the install Just Worked.
  12. Once you've installed Ubuntu, for better reliability and performance, enable the proprietary GPU drivers, in System Settings > Software and Updates > Additional Drivers. I enabled the NVIDIA and Intel drivers.
  13. I've found the touchpad often registers clicks while I'm typing. Turning off System Settings > Mouse and Touchpad > "Tap to click" fixed this and gives pretty good touchpad behaviour.
  14. Firefox by default has its hardware accelerated layers disabled, but force-enabling it seems to work fine. Open "about:config" in Firefox, and toggle "layers.acceleration.force-enabled" to true. Restart Firefox.

Saturday, 20 December 2014

Firefox video playback's skip-to-next-keyframe behavior

One of the quirks of Firefox's video playback stack is our skip-to-next-keyframe behavior. The purpose of this blog post is to document the tradeoffs skip-to-next-keyframe makes.

The fundamental question that skip-to-next-keyframe answers is, "what do we do when the video stream decode can't keep up with the playback speed?

Video playback is a classic producer/consumer problem. You need to ensure that your audio and video stream decoders produce decoded samples at a rate no less that the rate at which the audio/video streams need to be rendered. You also don't want to produce decoded samples at a rate too much greater than the consumption rate, else you'll waste memory.

For example, if we're running on a low end PC, playing a 30 frames per second video, and the CPU is so slow that it can only decode an average of 10 frames per second, we're not going to be able to display all video frames.

This is also complicated by our video stack's legacy threading model. Our first video decoding implementation did the decoding of video and audio streams in the same thread. We assumed that we were using software decoding, because we were supporting Ogg/Theora/Vorbis, and later WebM/VP8/Vorbis, which are only commonly available in software.

The pseudo code for our "decode thread" used to go something like this:
 
while (!AudioDecodeFinished() || !VideoDecodeFinished()) {
  if (!HaveEnoughAudioDecoded()) {
    DecodeSomeAudio();
  }
  if (!HaveEnoughVideoDecoded()) {
    DecodeSomeVideo();
  }
  if (HaveLotsOfAudioDecoded() && HaveLotsOfVideoDecoded()) {
    SleepUntilRunningLowOnDecodedData();
  }
}

 
This was an unfortunate design, but it certainly made some parts of our code much simpler and easier to write.

We've recently refactored our code, so it no longer looks like this, but for some of the older backends that we support (Ogg, WebM, and MP4 using GStreamer on Linux), the pseudocode is still effectively (but not explicitly or obviously) this. MP4 on Windows, MacOSX, and Android in Firefox 36 and later now decode asynchronously, so we are not limited to decoding only on one thread.

The consequence of decoding audio and video on the same thread only really bites on low end hardware. I have an old Lenovo x131e netbook, which on some videos can take 400ms to decode a Theora keyframe. Since we use the same thread to decode audio as video, if we don't have at least 400ms of audio already decoded while we're decoding such a frame, we'll get an "audio underrun". This is where we don't have enough audio decoded to keep up with playback, and so we end up glitching the audio stream. This sounds is very jarring to the listener.

Humans are very sensitive to sound; the audio stream glitching is much more jarring to a human observer than dropping a few video frames. The tradeoff we made was to sacrifice the video stream playback in order to not glitch the audio stream playback. This is where skip-to-next-keyframe comes in.

With skip-to-next-keyframe, our pseudo code becomes:

while (!AudioDecodeFinished() || !VideoDecodeFinished()) {
  if (!HaveEnoughAudioDecoded()) {
    DecodeSomeAudio();
  }
  if (!HaveEnoughVideoDecoded()) {
    bool skipToNextKeyframe =
      (AmountOfDecodedAudio < LowAudioThreshold()) ||

       HaveRunOutOfDecodedVideoFrames();
    DecodeSomeVideo(skipToNextKeyframe);
  }
  if (HaveLotsOfAudioDecoded() && HaveLotsOfVideoDecoded()) {
    SleepUntilRunningLowOnDecodedData();
  }
}


We also monitor how long a video frame decode takes, and if a decode takes longer than the low-audio-threshold, we increase the low-audio-threshold.

If we pass a true value for skipToNextKeyframe to the decoder, it is supposed to give up and skip its decode up to the next keyframe. That is, don't try to decode anything between now and the next keyframe.

Video frames are typically encoded as a sequence of full images (called "key frames", "reference frames", or  I-frames in H.264) and then some number of frames which are "diffs" from the key frame (P-Frames in H.264 speak). (H.264 also has B-frames which are a combination of diffs of frames frames both before and after the current frame, which can lead the encoded stream to be muxed out-of-order).

The idea here is that we deliberately drop video frames in the hope that we give time back to the audio decode, so we are less likely to get audio glitches.

Our implementation of this idea is not particularly good.

Often on low end Windows machines playing HD videos without hardware accelerated video decoding, you'll get a run of say half a second of video decoded, and then we'll skip everything up to the next keyframe (a couple of seconds), before playing another half a second, and then skipping again, ad nasuem, giving a slightly weird experience. Or in the extreme, you can end up with only getting the keyframes decoded, or even no frames if we can't get the keyframes decoded in time. Or if it works well enough, you can still get a couple of audio glitches at the start of playback until the low-audio-threshold adapts to a large enough value, and then playback is smooth.

The FirefoxOS MediaOmxReader also never implemented skip-to-next-keyframe correctly, our behavior there is particularly bad. This is compounded by the fact that FirefoxOS typically runs on lower end hardware anyway. The MediaOmxReader doesn't actually skip decode to the next keyframe, it decodes to the next keyframe. This will cause the video decode to hog the decode thread for even longer; this will give the audio decode even less time, which is the exact opposite of what you want to do. What they should do is skip the demux of video up to the next keyframe, but if I recall correctly there was bugs in the Android platform's video decoder library that FirefoxOS is based on that caused this to be unreliable.

All these issues occur because we share the same thread for audio and video decoding. This year we invested some time refactoring our video playback stack to be asynchronous. This enables backends that support it to do their decoding asynchronously, on another own thread. So since audio decodes on a separate thread to video, we should have glitch-free audio even when the video decode can't keep up, even without engaging skip-to-next-keyframe. We still need to do something like skipping the video decode when the video decode is falling behind, but it can probably engage less aggressively.

I did a quick test the other day on a low end Windows 8.0 tablet with an Atom Z2760 CPU with skip-to-next-keyframe disabled and async decoding enabled, and although the video decode falls behind and gets out of sync with audio (frames are rendered late) we never glitched audio.

So I think it's time to revisit our skip-to-next-keyframe logic, since we don't need to sacrifice video decode to ensure that audio playback doesn't glitch.

When using async decoding we still need some mechanism like skip-to-next-keyframe to ensure that when the video decode falls behind it can catch up. The existing logic to engage skip-to-next-keyframe also performs that role, but often we enter skip-to-next-keyframe and start dropping frames when video decode actually could keep up if we just gave it a chance. This often happens when switching streams during MSE playback.

Now that we have async decoding, we should experiment with modifying the HaveRunOutOfDecodedVideoFrames() logic to be more lenient, to avoid unnecessary frame drops during MSE playback. One idea would be to only engage skip-to-next-keyframe if we've missed several frames. We need to experiment on low end hardware.

Wednesday, 19 February 2014

How to prefetch video/audio files for uninterrupted playback in HTML5 video/audio

Sometimes when you're playing a media file using an HTML5 <video> or <audio> element, or with WebAudio, you really want to be sure that the whole audio/video file is totally downloaded before you start playing it. For example, you may be writing a game, and you want to be sure all your sound effects are preloaded, so there's no delay between your animations and your sound effects while the network downloads the remainder of the file.

So how can you be sure a media resource is fully downloaded before beginning playing it? You could wait for the "canplaythrough" event to fire on all your media elements, but that event is not fired correctly by Chrome.

A more reliable solution is to prefetch the video/audio file using XHR/AJAX requests, and play the video/audio from a Blob URI.

Here's a simple snippet of a JS file that downloads a file using XHR. The function accepts callbacks to return results.

function prefetch_file(url,
                       fetched_callback,
                       progress_callback,
                       error_callback) {
  var xhr = new XMLHttpRequest();
  xhr.open("GET", url, true);
  xhr.responseType = "blob";

  xhr.addEventListener("load", function () {
    if (xhr.status === 200) {
      var URL = window.URL || window.webkitURL;
      var blob_url = URL.createObjectURL(xhr.response);
      fetched_callback(blob_url);
    } else {
      error_callback();
    }
  }, false);

  var prev_pc = 0;
  xhr.addEventListener("progress", function(event) {
    if (event.lengthComputable) {
      var pc = Math.round((event.loaded / event.total) * 100);
      if (pc != prev_pc) {
        prev_pc = pc;
        progress_callback(pc);
      }
    }
  });
  xhr.send();
}

When the file is successfully downloaded, the fetched_callback is called with an argument which is the blob URI. You can simply set this as the src of an audio or video element and can then play the fully-downloaded resource. You can also set the same blob URI as the src of multiple audio/video elements, and the downloaded data won't be re-downloaded or duplicated/copied in memory.

There's also a progress_callback that's called with a percentage complete parameter as the file is downloaded, and an error_callback that's called when the download fails.

For a working demo: prefetching a video file before playback using HTML5 demo

Tuesday, 3 December 2013

Why does the HTML fullscreen API ask for approval after entering fullscreen, rather than before?

The HTML fullscreen API is a little different from other JS APIs that require permission, in that it doesn't ask permission before entering fullscreen, it asks forgiveness *after* entering fullscreen.

Firefox's fullscreen approval dialog, which asks "forgiveness" rather than permission.
The rationale for having our fullscreen API implementation ask forgiveness rather than request permission is to make it easier on script authors.

When the original API was designed, we had a number of HTML/JS APIs like the geolocation API that would ask permission. The user was prompted to approve, deny, or ignore the request, though they could re-retrieve the request later from an icon in the URL bar to approve the request at a later time.

Geolocation approval dialog, from Dive Into HTML's geolocation example.
The problem with this design for script authors is that they can't tell if the user has ignored the approval request, or is just about to go back and approve it by bringing up the geolocation door-hanger again.

This model of requesting permission has been seen to cause problems for web apps in the wild using the geolocation API. Often if a user ignores the geolocation permission request, the web app doesn't work right, and if you approve the request some time later, the site often doesn't start working correctly. The app just doesn't know if it should throw up a warning, or if it's about to be granted permission.

So the original developers of the fullscreen spec (Robert O'Callahan, and later I and others were involved), opted to solve this problem by having our implementation ask forgiveness. Once you've entered fullscreen, the user is asked to confirm the action.

This forces the user to approve or deny the request immediately, and this means that script will immediately know whether fullscreen was engaged, so script will know whether it needs to take its fallback path or not.

Note that the specification for requestFullscreen() defines that most of the requestFullscreen() algorithm should run asynchronously, so there is scope to change the fullscreen approval dialog to being a permission request before entering fullscreen instead if future maintainers, or other implementors/browser, wish to do so.