The State of State

Tagged as Erlang, Programming Languages, Reddit

Written on 2007-08-29 13:20:44

So, I've been having and alluding to discussions with Tim Sweeney of late. I sent him an e-mail a little over two weeks back and I received word back from him about a week ago. It's taken a while for me to digest it a little and ask his permission to post it here but he has been kind enough to grant said permission. So, without further ado, the transcript:

Me:

Tim,


My name is Brit Butler. I'm a college student in Atlanta, GA and an admirer of your work. I was very taken with your POPL talk on The Concurrency Problem but curious as to why you mentioned both the message passing model and referentially transparent functions but then went on to mostly talk about the latter with Haskell. I'm certain that you've used and read about Erlang and other message-passing systems and was wondering if you could explain your position on them to me, vis-a-vis Transactional Memory or some other method. I'm assuming you wouldn't be in support of STM because it's ultimately still about sharing state. Thanks so much for your time.

Regards,
Brit Butler
http://www.redlinernotes.com/


Tim:
Hi,

Lots of applications and reasonable programming styles rely on large amounts of mutable state. A game is a great example – there are 1000’s of objects moving around and interacting in the world, changing each frame at 60 frames per second. We need to be able to scale code involving that kind of mutable state to threads, without introducing significant new programming burdens. Transactional memory is the least invasive solution, as it allows writing pieces of code which are guaranteed to execute atomically (thus being guaranteed of not seeing inconsistencies in state), using a fairly traditional style, and it scales well to lots of threads in the case where transactions seldom overlap and touch the same state.

Message-passing concurrency isn’t a very good paradigm for problems like this, because we often need to update a group of objects simultaneously, preserving atomicity. For example, within one transaction, the player object might decide to shoot, issue a command to his weapon, check an ammunition object, remove ammunition from it, and spawn a new bullet that’s now flying through the world. And the sets of objects which may need to atomically interact isn’t statically known – any objects that come into contact, or communicate, or are visible to each other, may potentially interact.

When implementing that kind of code on top of a message-passing concurrency layer, you tend to get bogged down writing numerous message interchanges which really just turn out to be ad-hoc transaction protocols. That’s quite error-prone. Better to just use transactions in that case.

This argument for transactional memory is limited in scope:

For algorithms which can be made free of side effects, pure functional programming (or “nearly pure functional programming” as in Haskell+ST) is cleaner and allows more automatic scaling to lots of threads, without committing to a particular granularity as with message-passing.

For algorithms that need to scale to multiple PCs, run across the Internet, etc, transactions seem unlikely to be practical. For in-memory transactions on a single CPU, the overhead of transactions can be brought down to <2X in reasonable cases. Across the network, where latencies are 1,000,000 times higher, message passing seem like the only plausible approach. This constrains algorithms a lot more than transactions, but, hey, those kinds of latencies are way too high to “abstract away”.

The existing Unreal engine actually uses a network-based message passing concurrency model for coordinating objects between clients and servers in multiplayer gameplay. It even has a nifty data-replication model on top, to keep objects in sync on both sides, with distributed control over their actions. It’s quite cool, but it’s inherently tricky and would add an awful lot of complexity if we used that for coordinating multiple threads on a single PC.

-Tim


So, there you have it. More on all this later. I've got to go play around with Erlang a bit more. I'm hoping Andre Pang and Patrick Logan will help me dig into this a bit deeper in days to come. Who else wants in on the conversation? Comment below.
comments powered by Disqus

Unless otherwise credited all material Creative Commons License by Brit Butler