8 ms·

Carmack: Parallel Implementations

218 points by swah 15y ago

deleted 15y ago
[deleted]
gravitronic 15y ago
I love reading Carmack's writing. I find it is always intelligent a great combination of interesting anecdote and generalized advice, making it both interesting and educational to read. 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.
dwhitty 15y ago
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 http://twitter.com/#!/ID_AA_Carmack/status/53512300451201024 Not "sometimes", "mosttimes"!
- Periodic 15y ago
  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.
- bad_user 15y ago
  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 http://prog21.dadgum.com/23.html
  - pjscott 15y ago
    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 http://lambda-the-ultimate.org/node/1277 Definitely one of the most interesting things I've seen in a while.
  - dwhitty 15y ago
    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.
lurker17 15y ago
John Carmack recently discovered that source control systems support code trees can be branched?
- lukesandberg 15y ago
  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.
michaelbuckbee 15y ago
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/ http://code.flickr.com/blog/2009/12/02/flipping-out/
iamwil 15y ago
" 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.
- pavpanchekha 15y ago
  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.
- tobiasu 15y ago
  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.
  - VladRussian 15y ago
    >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!
olliesaunders 15y ago
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.
- agumonkey 15y ago
  This one ? http://www.infoq.com/interviews/beck-implementation-patterns http://www.infoq.com/interviews/beck-implementation-patterns
6ren 15y ago
> "Branch by Abstraction (instead of Branch by Source Control)" (http://paulhammant.com/ 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.
malkia 15y ago
Let's raise some #ifdef from HELL (Sorry joking here, but working on such code base).
- malkia 15y ago
  And then sometimes, it's the only choice, especially if you are going on small devices - http://ecos.sourceware.org/ http://ecos.sourceware.org/
jorangreef 15y ago
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.
InclinedPlane 15y ago
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.

218 points by swah 15y ago

deleted 15y ago

[deleted]

I love reading Carmack's writing. I find it is always intelligent a great combination of interesting anecdote and generalized advice, making it both interesting and educational to read. 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.

dwhitty 15y ago

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 http://twitter.com/#!/ID_AA_Carmack/status/53512300451201024 Not "sometimes", "mosttimes"!

Periodic 15y ago
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.
bad_user 15y ago
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 http://prog21.dadgum.com/23.html
- pjscott 15y ago
  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 http://lambda-the-ultimate.org/node/1277 Definitely one of the most interesting things I've seen in a while.
- dwhitty 15y ago
  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.

lurker17 15y ago

John Carmack recently discovered that source control systems support code trees can be branched?

lukesandberg 15y ago
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.

michaelbuckbee 15y ago

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/ http://code.flickr.com/blog/2009/12/02/flipping-out/

iamwil 15y ago

" 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.

pavpanchekha 15y ago
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.
tobiasu 15y ago
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.
- VladRussian 15y ago
  >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!

olliesaunders 15y ago

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.

agumonkey 15y ago
This one ? http://www.infoq.com/interviews/beck-implementation-patterns http://www.infoq.com/interviews/beck-implementation-patterns

6ren 15y ago

> "Branch by Abstraction (instead of Branch by Source Control)" (http://paulhammant.com/ 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.

malkia 15y ago

Let's raise some #ifdef from HELL (Sorry joking here, but working on such code base).

malkia 15y ago
And then sometimes, it's the only choice, especially if you are going on small devices - http://ecos.sourceware.org/ http://ecos.sourceware.org/

jorangreef 15y ago

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.

InclinedPlane 15y ago

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.