Monday, 20 December 2010

Iterated Prisoner's Dilemma

Last Sunday we had a sort of workshop on "negotiation" for some of the Mozilla managers. Part of this workshop was an exercise amounting to playing Iterated Prisoner's Dilemma, with some twists which aren't relevant here. There were three independent games, each with two players, each player being a team of three or four people. We were instructed to maximise our own score without regard to the other player's score.

My approach was to observe that if both teams behave perfectly rationally, they will use the same strategy. Then the optimal strategy is obviously to always cooperate. If the other team defects then you know the rationality assumption doesn't hold, so the game gets more difficult (probably devolving to the game-theoretic equilibrium of always defecting, but then asymptotically it doesn't matter what you did before detecting defection). Fortunately for us the other team was in fact rational enough to always cooperate and we played a perfect game. (If the number of iterations is known in advance, defecting on or before the last round might make sense, but we couldn't be sure how many rounds there were going to be so this didn't matter.) This approach is known as superrationality although I wasn't aware of that at the time...

One surprise for me was that at least three of the six teams did not always cooperate. I was a bit disappointed to find that not all my colleagues think like me :-). I don't think that was supposed to be the lesson of this exercise, though :-).

Another surprise was that some people expected me to play the game according to "Christian principles". In fact, I was purely trying to optimize the objective function we were given, regardless of what God would want. This raises a very interesting question: is it OK to disobey God's commands within the framework of an artificial game? In many games, especially games with more than two players that involve alliances, lies and betrayal are an essential part of the game. Is it OK for a Christian to lie and betray in such games?

I think the answer depends on the context. If everyone understand it's "just a game", the diabolical behaviour is demanded by the framework of the game, and there are absolutely no hard feelings about such behaviour, it seems harmless. But in any context where others might expect you to be obeying God even within the framework of the game, I think we have to follow Paul and play it safe so we do not "cause others to stumble". So I think in hindsight I was wrong to ignore Christian considerations in our negotiation exercise, although I think they lead to the same results anyway.

So what would Jesus do in a real-life Iterated Prisoner's Dilemma? It seems obvious: "do to others what you would have them do to you", which leads to the same analysis as I had before --- cooperate. If the other player defects, the Sermon on the Mount still applies --- "turn the other cheek --- and also "forgive seventy times seven times": we are asked to cooperate in the face of repeated defection.

Interestingly, in this game, belief in the trustworthiness of the other player --- or even belief in divine justice --- lead to superior joint outcomes on average even if the belief is false. Most people think it's obvious we should believe only what is true, but I don't think that principle is obvious at all in (for example) materialist utilitarian frameworks. It should be obvious to Christians.



Friday, 3 December 2010

GPU-Accelerated Video Playback In Firefox 4

Now that accelerated layers have been turned on for a while in Firefox 4 betas, I want to explain what this means for HTML5 <video> playback in Firefox and how it compares with what Adobe is doing in Flash 10.2.

I've already written about our layers framework and how that contributes to GPU-accelerated rendering. For each frame, our video decoder libraries (libvp8, libtheora) produce a YCbCr (aka YUV) image in their output buffer in system memory. This is usually, but not always, in 4:2:0 format. In the video decode thread we wrap this buffer up into a YCbCrImage object, which makes a copy. (We have to copy here because the decoder libraries overwrite their output buffer for every frame, and we're decoding a bit ahead of the current frame to avoid jitter.) Exactly how that copy is made depends on the layers backend:


  • For GPU backends that support multithreaded access to GPU resources (currently our D3D10 backend), the video decoder thread copies the output buffer directly into VRAM. This is the most efficient approach.
  • For GPU backends that don't support multithreaded access, we copy the output buffer in system memory. The buffer is uploaded to VRAM later when we paint on the main thread.
  • For CPU-only rendering, we convert the output buffer from YUV to RGB (while also scaling it to the expected output size) on the video decoder thread.

Actual rendering happens on the main thread. When we composite an ImageLayer containing a YCbCrImage into the window, the GPU converts to RGB at draw time using a shader program (and also handles scaling). When we're not using the GPU, we just draw the pre-converted image (possibly with some rescaling if the output size has changed since we did the convert-and-scale step).

This architecture seems optimal given the constraints we're currently working with, although it will need to evolve in a few directions. Other than being fast, it works well for Web authors. Unlike Adobe's "stage video", it just works without authors having to do anything. You can overlay and underlay content around the video without losing acceleration. You can wrap it in a container with CSS opacity and 2D transforms, scroll it and clip it, without losing acceleration. (Currently a few effects will cause us to deaccelerate --- if the video has an ancestor element with 'border-radius' and non-visible 'overflow', an ancestor with CSS mask, filter or clip-path, or an SVG ancestor. We'll fix those cases post-FF4 by accelerating them.)

This design will need to evolve in a few directions. We currently don't have hardware decoders for our video formats, but that will change as hardware support for VP8 spreads, and we'll need to take advantage of it. We may need to introduce a new Image type or even a new Layer type to encapsulate hardware decoding. I hope that there will be an efficient way to get decoded video data into textures, otherwise we'll have to limit the use of hardware decoders to whatever special cases their APIs support.

Some devices have GPUs with bad enough shader performance that doing YUV conversion with shaders is a noticeable performance hit. But some of them have native support for YUV-format textures or surfaces with dedicated hardware for YUV conversion. We should use those features. This won't require any architectural changes.

In Fennec, we composite the layer tree in a different process to the content process that actually does the video decoding. This will later be true for desktop Firefox too. This requires us to ship our YCbCr frames through shared memory or shared VRAM buffers, but we should be able to keep the same basic architecture.

The separate compositor process gives us one extra advantage. If the main thread of the content process is busy (e.g., running some in-page Javascript), we'll be able to deliver decoded video frames directly from the video decoder thread to the compositor process and render them on the screen. This means we'll be able to maintain smooth video playback no matter what else the browser is doing. (At least until the demands of video decoding and GPU compositing completely overwhelm your system...)