Death of the Thread Model

You haven’t really had the fear of Turing struck into you until you’ve tried concurrent programming. Any lofty visions you’ve had of a normal, happy life as a programmer won’t survive your first pthread or Thread.run() call.

My most recent non-trivial attempt at threads was way back when in college. The course was “TCP/IP Programming.” It was the kind of course that didn’t interest me just from its title and description. Really, I signed up for it because the best professor in the entire school was delivering it, Dan Duchamp, and this was my last semester. In the end, it actually wound up being an informative course, because networking is not my strong point.

We were warned that the assignments would be in C and would be back-breakers. This almost turned out to be true. I had Duchamp in three other courses, and sometimes he would overstate the scope of a project.

Our projects were:

  • a DNS resolver that sent UDP to DNS and relayed the result via TCP back to whomever requested it
  • a simulation of ICMP and IP; this is one of the courses that I look back on and think “I can’t believe I pulled that off”
  • a link-state and distance vector routing simulation
  • a simulation of TCP
  • port the first assignment to the TCP simulation

Somehow, someway, I had no problem with the first three. Then I read the description of the TCP simulation, and I shuddered when I saw that three threads were required.

I pretty much knew right then that it was over.

In fact, after getting extra help from Duchamp, it became apparent that I needed to use pthread_cond_wait, pthread_cond_timedwait, pthread_mutex_t, and pthread_cond_signal to name a few. These were system calls and types that I had never used before.

Duchamp, bless his heart, claimed that he covered them in the OS course, which I also took with him. While he covered mutexes and locking, we did not make use of condition variables in assignments. So on top of the intellectual burden of dealing with my half-finished attempt at multi-threading, which was already based on a bad thread design (and it was too late to start over), I had to learn and use new system calls correctly.

My point is my last semester of senior year could’ve been much less stressful if programming with threads wasn’t a death trap. At work, I asked our technical lead if they made use of multi-threading in the code, and the answer was a resounding “No, it becomes too ugly too quickly.”

What’s odd is that in most CRUD apps, concurrency is transparent and under the hood. Most RDBM systems give you this for free in the form of transactional processing.

So something can’t be right. It can’t be such a nightmare to do something like three threads, one for each layer boundary, plus another to do the real work, but so effortlessly achieve concurrent data access and processing. Why do I have to suffer through concurrency if it is not DB-related?

Then, once upon a time, I was listening to Dot Net Rocks show #269. The guest was Larry O’Brien, who was arguing that the thread-and-lock model is garbage:

Larry O’Brien: Oh, absolutely, but even if you get it and even if you think it’s fun, there’s a thing about that thread and process model that we have in the CLR today, which I would argue makes it fundamentally broken for business programming. So, check out this scenario. You have a library and it has some publicly available method by which it acquires a lock, right?

Carl Franklin: Yeah.

Larry O’Brien: And holds that lock and returns to you and you go about and do your other thing. If you have another method that calls that library on which that library performs a callback and by a callback I mean all sorts of important things. I’m talking about virtual method calls in a world of object orientation. I’m talking about delegates and events central to graphics programming and I’m talking about lambda expressions, which are coming out in C# 3.0 and they’re very important for LINQ. You can never safely have a library that simultaneously has a publicly triggerable lock that executes a callback to client code because it’s perfectly legal for the client code to start up a new thread…

Carl Franklin: Yeah.

Larry O’Brien: And within that new thread, call that method attempts to get the lock which is already held by the previous thread and the end result of that is deadlock.

I’d take this even a step further: the thread-and-lock model of concurrency is broken because it is too low-level. Why, in this age of garbage collection, managed code, and workflow engines, hasn’t the abstraction level been raised on concurrency as well?

The itching issue that needs scratching is that it has been for quite some time, but only in the niche of databases. Memory management used to be a pest; now there is platform support for garbage collection. We need similar support for concurrency. It was just then that the guys on the show discuss Software Transactional Memory:

Larry O’Brien: Okay. Software Transactional Memory is essentially optimistic locking for memory.

Carl Franklin: Yeah.

Larry O’Brien: You wrap a call or a block in what’s essentially a transaction. You say “Atomic, start block” and then you finish the block and it runs at full speed and then you have a follow-along processor that goes through it and it looks for that one in a thousand, one in a million memory collision. If a memory collision has occurred, it retries it.

Carl Franklin: Yeah.

Larry O’Brien: Yeah. It’s not at all a bad model.

This would be a giant step forward. It does have its problems, namely that it still requires the programmer to be aware and predict what blocks of code are critical sections in order to mark them off as transactions.

To take it a step higher, using Futures, this sort of demarcation can be delegated to the compiler and/or runtime environment entirely:

Larry O’Brien: Instead of trying to second guess the creation of thread, what you do is you say, “Well, I want this value” you know this value being returned from a function, “but I can either have the value or I can have” what Sutter calls “a Future.”

A Future is basically an IOU. Okay, so you have this reference to a Future and when you need it, when you say, “Okay, I want to cash in this IOU” at that point, the system will block and guarantee that the value becomes concrete. So, just by sort of flipping things around from “Okay, let’s create processes and kind of second guess how many cores I have” and those sorts of approaches.

This approach says, okay by simply having a whole bunch of IOUs floating around then it becomes possible for the compiler on the runtime to do a lot of really clever reasoning about “Oh hey, look. Here’s this IOU, but I know that this IOU won’t be required for several hundred milliseconds and so, therefore, I have enough information to distribute that to another core.”

The only drawback here is again another programmer-dependent pitfall. Functions that return Futures work best, if at all, when they are pure functions with no side effects. This is a throwback to functional programming, and my personal least-favorite Scheme.

I still favor these methods to the rather Draconian no-shared-mutable-state edict of Erlang:

Carl Franklin: There’s no shared memory, right?

Larry O’Brien: Oh, that’s huge.

Carl Franklin: Between processes?

Larry O’Brien: That’s a huge thing. Really to make Concurrency work at the language level, the number one thing that you want to get rid of is shared mutable state.

Carl Franklin: Yup.

Larry O’Brien: Erlang is single assignment to variables…

This is why I think Polyphonic C# is a nice try but gives me some of the same headaches I felt at the start of this post.

It is ultimately a trade-off between shared mutable state (and thus performance) a la Futures and functional programming, and clarity (and thus less performance) a la STM. I think this trade-off is a familiar one to most people in this field. Moreover, I’ll say that this trade-off is as innate to our field as Brooks’ Law.

I maintain that abstractions like STM and Futures are going to be very important for us software developers in the coming decade if we are to make affordable full use of the next wave of hardware.

About these ads

6 Responses to “Death of the Thread Model”

  1. I’ve been reading your blog for a while (well, skimming is a better term. I don’t get time to read things in-depth while at work), and I noticed your reference to Dan Duchamp. This piqued my interest, as I’m currently going into my second year as a Computer Science major at Stevens.

    It made me happy to see (or at least infer) that you’re a Stevens grad, as there are far too many graduates of far too many CS curricula that don’t really know what they’re doing when faced with real programming issues. Even better, you give me hope that my chosen program will leave me well-prepared for facing such programs.

  2. Hey Andy. Thanks for the comment. Good to know I have a few readers.

    Yes, I did graduate from Stevens, this May actually. I’ve been trying to hide that fact since I still think I didn’t get my money’s worth (but it is possible that I had big expectations). But thanks for the vote of confidence; hopefully I can reverse my own bias against the CS program there.

    One interesting thing I’ve discovered is that the CS program might actually be of better-than-average quality. At my new job, I’ve been swapping war stories with fellow CS degree-holders, and my stories are consistently the most horrific (“we never had to implement a compiler!”)

    I actually dropped another hint about Stevens in this post that references Linda Laird. She is a professor that teaches software engineering courses. As one Duck to another, I really recommend you try to take the graduate-level SE courses. They will make your transition into “the industry” much more smooth.

    For that matter, I also recommend Co-op. It really greases the wheels of your employment search. If you stick with it through your junior and senior years, along with those software engineering courses, you might actually be able to apply some of those classroom techniques on the job. It’s like catching lightning in a bottle, but it can happen.

    And finally: take courses that Duchamp teaches, whether the course interests you or not, whether it is required or an elective. The man’s lectures are two and a half hours of unique word choice, riotous dry sarcasm, and giggle-worthy exaggerations.

    Feel free to pick my brain about any Stevens-related stuff you wanna dish about.

  3. Sorry. Does somebody realize how to define true EA from bad and a real trading signals from fake? thank you

  4. wevewharord Says:

    Guy .. Excellent .. Wonderful .. I’ll bookmark your blog and take the feeds alsoI am satisfied to seek out so many helpful information here in the publish, we’d like develop more techniques on this regard, thanks for sharing. . . . . .

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: