Carmack: Parallel Implementations(altdevblogaday.com)
altdevblogaday.com
Carmack: Parallel Implementations
http://altdevblogaday.com/2011/11/22/parallel-implementations/
11 comments
The methodology espoused in this article presents a good case for composing programs from discrete pieces of behavior with referential transparency (pure, or at least deterministic functions).
"Sometimes, the elegant implementation is just a function. Not a method. Not a class. Not a framework. Just a function."
- John Carmack (Twitter) http://twitter.com/#!/ID_AA_Carmack/status/53512300451201024
Not "sometimes", "mosttimes"!
"Sometimes, the elegant implementation is just a function. Not a method. Not a class. Not a framework. Just a function."
- John Carmack (Twitter) http://twitter.com/#!/ID_AA_Carmack/status/53512300451201024
Not "sometimes", "mosttimes"!
Carmack works on game engines and a game environment is by definition an environment in which objects have side effects and keep a lot of state. Referential transparency is nice and all, but developing games in this style (while doable with functional reactive programming) is a pain in the ass.
Here's a good series of articles about it: http://prog21.dadgum.com/23.html
Here's a good series of articles about it: http://prog21.dadgum.com/23.html
According to Tim Sweeney, the lead developer at Epic Games, there are three types of code in a modern first-person shooter: gameplay simulation, numeric computation, and shading. You've described gameplay simulation. Shading is very data-parallel. And the numeric code is essentially functional.
Even for gameplay code, it could be nice to have explicit tracking of what the mutable state is, to prevent bugs. He has some fascinating slides about this, if you google for "The Next Mainstream Programming Language". Extensive discussion on Lambda the Ultimate here:
http://lambda-the-ultimate.org/node/1277
Definitely one of the most interesting things I've seen in a while.
Even for gameplay code, it could be nice to have explicit tracking of what the mutable state is, to prevent bugs. He has some fascinating slides about this, if you google for "The Next Mainstream Programming Language". Extensive discussion on Lambda the Ultimate here:
http://lambda-the-ultimate.org/node/1277
Definitely one of the most interesting things I've seen in a while.
It is a perfectly defensible goal to have some or many pure functions within an imperative programming environment where state is persisted in variables outside of the library of pure functions. I don't think it is fair to equate pure functions with pure functional programming.
In a mixed model, you can have a mutable state but still have a large bank of trustable, testable, parallelizable behaviors defined in pure or deterministic functions with well defined contracts of input and output states.
In a mixed model, you can have a mutable state but still have a large bank of trustable, testable, parallelizable behaviors defined in pure or deterministic functions with well defined contracts of input and output states.
I think you could go a little further and say that it implies dependency injection. You want to be able to declaratively tell the program which implementation to use in difference places. This would be a little more familiar to the OO paradigms than pure/deterministic functions. However, I still argue that pure and deterministic functions have many desirable properties.
Flickr does something similar with their feature rollouts, instead of branching code they define "flags and flippers" to implement it alongside the existing code.
This lets them gradually test it at scale (expose the new feature to x% of their users and slowly grow x).
More details on their dev blog: http://code.flickr.com/blog/2009/12/02/flipping-out/
This lets them gradually test it at scale (expose the new feature to x% of their users and slowly grow x).
More details on their dev blog: http://code.flickr.com/blog/2009/12/02/flipping-out/
> "Branch by Abstraction (instead of Branch by Source Control)" (http://paulhammant.com/)
In the beginning, we avoided copying when we experimented by using flags; then we used source control branches to make diff "copies". In the end, we just copied.
In the beginning, we avoided copying when we experimented by using flags; then we used source control branches to make diff "copies". In the end, we just copied.
There are two powerful techniques here.
One is basic refactoring purity. The idea is that you progress in steps such that at every step the program still works as expected and passes unit tests, implementing the classic "build replacement, switch client code, deprecate old code, remove old code" cycle.
The other is the idea of feature flags, which allow you to turn on or off various experimental code paths configurationally. This technique is especially powerful when used on high-traffic web sites (google, amazon, and facebook use it extensively). You can basically roll out new features or even backend changes slowly to a percentage of your users at a time, with the ability to roll back as necessary. It's a very powerful risk mediation tool.
One is basic refactoring purity. The idea is that you progress in steps such that at every step the program still works as expected and passes unit tests, implementing the classic "build replacement, switch client code, deprecate old code, remove old code" cycle.
The other is the idea of feature flags, which allow you to turn on or off various experimental code paths configurationally. This technique is especially powerful when used on high-traffic web sites (google, amazon, and facebook use it extensively). You can basically roll out new features or even backend changes slowly to a percentage of your users at a time, with the ability to roll back as necessary. It's a very powerful risk mediation tool.
" It is often tempting to shortcut this by passing in some kind of option flag to existing code, rather than enabling a full parallel implementation. It is a grey area, but I have been tending to find the extra path complexity with the flag approach often leads to messing up both versions as you work, and you usually compromise both implementations to some degree."
I don't get this particular implementation detail. If it's not a flag, how would it be implemented?
It's not like you're coding it on two separate branches, since it needs to switched at runtime. It looks like the plea is for it to be pure functional, to make it easier to switch it in and out. But I can't quite picture how he's implementing this.
I don't get this particular implementation detail. If it's not a flag, how would it be implemented?
It's not like you're coding it on two separate branches, since it needs to switched at runtime. It looks like the plea is for it to be pure functional, to make it easier to switch it in and out. But I can't quite picture how he's implementing this.
He means having both implementations use the same infrastructure. This is like taking your Raytracer class, and modify its Trace() method to check some global flag to determine which algorithm to use, shunting both into the Raytracer. Instead, he argues for making two totally separate implementations: a RaytracerKD and a RaytracerBST (say), each of which have identical interfaces and which you switch between at a higher level. This way your level of coupling is lower and you hopefully have fewer problems, even though it may also be more complex.
As I read it, the alternative implementation should branch of at a single point in the code. The alternative path usually requires modifications in the functions and data it's calling and using. But instead of going through the code adding flags everywhere, the idea is to make a source code copy and modify that. It duplicates source code, but keeps the original implementation untouched.
I can imagine that it allows more freedom re-working the code. You don't have to worry about breaking the original implementation this way, freeing up mental capacity.
I can imagine that it allows more freedom re-working the code. You don't have to worry about breaking the original implementation this way, freeing up mental capacity.
>freeing up mental capacity.
another way he seems to have found to free mental capacity - his text is suspiciously lacking mentioning of abstractions and design patterns. Switching between implementations? There is a pattern for that!
another way he seems to have found to free mental capacity - his text is suspiciously lacking mentioning of abstractions and design patterns. Switching between implementations? There is a pattern for that!
Yeah - if only Carmack had read the Gang of Four on http://en.wikipedia.org/wiki/Design_Patterns - imagine how much more he would have accomplished! He could have used the Flyweight pattern for texels, since the same color is used many times - and that's just one example! :)
I just started doing this a few days ago. I was rewriting major parts of a key value store on a separate branch in git. Then I realized it would be simpler to just stay on the master branch and duplicate the existing code with a new class name, so I could skip the mental overhead of branching and compare performance before and after easily.
I heard Kent Beck talk about this technique in an InfoQ video years ago. Not to belittle it though; it’s a good technique, I’ve used it a few times.
[deleted]
Let's raise some #ifdef from HELL (Sorry joking here, but working on such code base).
And then sometimes, it's the only choice, especially if you are going on small devices - http://ecos.sourceware.org/
John Carmack recently discovered that source control systems support code trees can be branched?
Read the article. He was talking about how you need to be able to instantly switch between implementations in the same code base. Sometimes even at run time.
One could tangentally conclude from reading this post that a well designed architecture would easily support a second parallel implementation, whereas a heavily-coupled, poorly designed architecture would make the parallel implementation hard to pull off. Neat.