March 01, 2006

Variables and threads

One thing that always caused me no end of headaches was dealing with data and threads with Parrot. Parrot was designed to be a mostly single-threaded system with the option to spawn off multiple threads, mostly because the languages that parrot was dealing with were, for the most part, single-threaded, and where they were multithreaded they were multithreaded really badly. Tornado's different -- it's supposed to be massively multithreaded, which definitely changes the way you want to look at data.

In a mostly single-threaded case you want mutable data, since that's fastest. Having to create a new X every time you modify the old X gets slow. Lots of time's spent allocating data, copying data, and cleaning up the old copies of data. Bleah. (The Java folks are well aware of this) The downside there is that if you've data that multiple threads share you need to lock that data even if you're not going to modify it, since you can't be sure that another thread's going to modify it.

In the multithreaded case, you want immutable data, at least as much as possible. Multiple threads can access the data safely with no synchronization, since there's no way the data can change, and that's fine.

The choice of mutable vs immutable data really is one of relative threadedness -- the more multithreaded you are, the more the synchronization costs outweigh the copying and GC costs. Basically you've got to take an educated guess about how things are going to work (or trot out your particular dogma) and choose. Then you get to deal with the repercussions of that choice.

For tornado, we're going with basically immutable data. Machine operations generate new data elements, rather than reusing old ones, and variable actions are all explicitly stateless. (That is, you fetch data out of the variable store, but once you do the data you've fetched has no attachment to the variable name any more, and another thread could store something different into that variable and you'd not know, which is different than what Parrot did) That simplifies the engine design a lot, and removes many potential race conditions, which is a Good Thing.

Interestingly, this also means that the engine's pretty inherently SSA, which makes a number of bytecode optimizations possible that weren't with parrot, because parrot had such a massive number of potential side-effects. That's a separate topic, though.

Tornado's also going with a generic by-reference data scheme, that is all data is accessed by reference, and a data element has a type and payload component. That makes things a little simpler, since there's only one 'real' data type, a pointer to a data element. Going for variable-sized data elements (4 byte int, 8 byte int, float, string, whatever) would allow things to be a smidge faster, but we're constrained there by our guarantees of safety as an embedded engine, which means we've got to be a little paranoid for now, since we can't guarantee that a bytecode program is correctly generated, and we don't have the tools we need to allow for unfettered code running that'd allow us to trap illegal operations. (Damn that lack of MMU and kernel mode access!)

That's OK, we can still manage.

Posted by Dan at March 1, 2006 03:27 PM | TrackBack (0)

It seems like you are building exactly the sort of language that I wish I had right now. I'm really looking forward to seeing where your work leads to.

Posted by: Damien Katz at March 1, 2006 11:45 AM

Heh. I'm building the VM to run the sort of language you wish you had. I'm pretty sure the actual language I build to compile to the VM will be a bit of a kludge. (For sufficiently large values of "bit", I expect) That's the joy of a VM, though -- I can build an OK HLL and a good VM, and if it catches someone's fancy they can build a better VM, and I'm cool with that.

This is actually all kind of weird, since most of the design decisions are about as far away from what I'd normally want in a language or VM environment as you can manage. Still, it's special-purpose -- who needs a DSL when you can have a DSVM? :)

Posted by: Dan at March 1, 2006 11:54 AM

Ahh, I see, the VM is the primary goal. I guess you'll be designing for it a IL liked you said wished you'd had for Parrot?

Then maybe someday I'll build the language that I need. Cool!

And as far as a DSVM goes, I think the world needs a variety of VM architectures. One VM just can't be enough to satisfy the demands of all the different useful computation models. And increasingly there is a need for better concurrency models, especially as multi-core chips become commonplace. Maybe Tornado will hit at just the right time, just when the need becomes most obvious, and it becomes the Next Big Thing, ala Java in '95. :)

Posted by: Damien Katz at March 1, 2006 12:35 PM

Yep, the VM's the primary goal -- ultimately I need to run programs that may be untrusted, programs that do massive multithreaded operations on large chunks of data. The language, so far as I'm concerned, is just the means to get those programs in a state I can run 'em. I make no particular claims as a language designer. I do semantics more than syntax.

The increasingly common multicore/SMP systems are part of what's driving this design. Since I have to process potentially chunks of data, and that processing is pretty isolated (that is, each chunk can be processed independent of any other chunk) it makes sense to go as multithreaded as possible, and once you go there it opens up an interesting set of possibilities. Granted, some limitations, but that's cool. I don't need to duplicate C or Smalltalk -- I've already got those languages if I need 'em.

And yeah, I'd be thrilled if you built the language you needed when this is done. Code's under a BSD license, and when it's in a state for people to actually use I'll open up the subversion repository.

Dunno if it'll be the Next Big Thing, but it will map nicely to some of what the PS3 does, these 2/4/6/8 core chips Intel and AMD are pushing, and some distributed work on top of it if we wanted to go that far. Even in a single-core case, some problems are significantly easier to deal with if you've got easy to use multithreading. (Like a lot of game physics and object interaction stuff)

Posted by: Dan at March 1, 2006 12:58 PM

Have you considered using linear objects to help with the allocation of single-threaded objects? It would be especially useful if you could split sequences into smaller, unshared ones (a la displaced arrays in CL) and reassemble them after they've been worked on. That way, you implicitly and securely avoid a lot of gratuitous consing, while still being able to distribute the work around. 1 bit is all it takes to reap most of the benefits.

Posted by: pkhuong at March 1, 2006 09:41 PM

Dan, why make the VM itself use SSA? Why not use SSA in the IL, and just use infinite registers in the IL compiler as well as the VM. The IL compiler reduces the working set down to the minimal needed for the bytecode program with graph coloring, and the VM will expand its register set as needed at runtime.

SSA is the way to go, Parrot is basically limited for no reason. I did some testing in my own VM and an infinite register machine is the way to go, I think.

Posted by: Melvin at March 29, 2006 02:30 AM

Never mind my question, I actually READ your description the second time. Multithreaded is your reason. Cool. Sounds like a lot of potential churn, though. Keep us posted.

Posted by: Melvin at March 29, 2006 02:51 AM