The Birth of Computicles

I have written about the “computicle” concept a couple of times in the past:
Super Computing Simulation Sure is Simple
The Existential Program

The essence of a computicle boils down to the following three attributes.

• Ability to receive input
• Ability to perform some operations
• Ability to communicate with other computicles

I had written about memory sharing and ownership, and what mechanisms might be used to exchange data and whatnot. Now that I’ve done the IO Completion Port thing, I can finally introduce a ‘computicle’.

The idea is fairly straight forward. I would like to be able to write a piece of code that is fairly self sufficient/standalone, and have it run in its own environment without much fuss. In the context of Lua, that means, I want each computicle to have its own LuaState, and to run on its own OS thread. I want to be able to communicate with the thing, using a queue, and allow it to communicate with other computicles using the same mechanism. Of course I want everything seamlessly integrated so the programmer isn’t required to know anything about locking mechanisms, or even the fact that they are in a separate thread, or anything like that. Without further ado, here’s an example:

local Computicle = require("Computicle");

print(Computicle:compute([[print("Hello World!")]]):waitForFinish());

Tada! This little code snippet does all those things I listed above. I’ll present it in another form so it is a little more obvious what’s going on.

local Computicle = require("Computicle");

local comp = Computicle:create([[print("Hello World!")]]);

local status, err = comp:waitForFinish();

print("Finish: ", status, err);

Here, an instance of a computicle is created, and the code chunk that it is to execute is fed to it through the constructor. Of course, that is Lua code, so it could be anything. Another more interesting form might be the following:

local comp = Computicle:create([[require("helloworld.lua")]]);

What’s happening behind the scenese here is that the Computicle is creating a TINNThread to run that bit of code, which in turn is creating a separate LuaState for the same. At the same time, an IOCompletion port is also being created so that communication can occur. The ‘waitForFinish’ is a simple mechanism by which the any computicle can be waited upon. More exotic synchronization mechanisms can be brought into play where necessary, but this works just fine.

The code for the computicle is a test case to be found here.

Here’s an example of how you can spin up multiple computicles at the same time.

local Computicle = require("Computicle");

local comp1 = Computicle:compute([[print("Hello World!");]]);
local comp2 = Computicle:compute([[
for i=1,10 do
print("Counter: ", i);
end
]]);

print("Finish: ", comp1:waitForFinish());
print("Finish: ", comp2:waitForFinish());

If you run this, you see some interleaving of the two threads running at the same time. You wait for completion of both computicles before finally finishing.

How about inter-computicle communications? Well, when you construct a computicle, you can actually give it two bits of information. The first is an absolute must, and that’s the code to be executed. The second is optional, and is the set of parameters that you want to pass to the computicle. I have previously written about the fact that communicating bits of data between threads requires a well thought out strategy with respect to memory ownership, and I showed how the IO Completion Port can be used as a queue to achieve this. Well, computicles just use that mechanism. So, you can do the following:

local Computicle = require("Computicle");

local comp2 = Computicle:create([[
local ffi = require("ffi");

while true do
  local msg = SELFICLE:getMessage();
  msg = ffi.cast("ComputicleMsg *", msg);

  print(msg.Message*10);
  SELFICLE.Heap:free(msg);
end
]]);

local sinkstone = comp2:getStoned();

local comp1 = Computicle:create([[
local ffi = require("ffi");

local stone = _params.sink;
stone = ffi.cast("Computicle_t *", stone);

local sinkComp = Computicle:init(stone.HeapHandle, stone.IOCPHandle, stone.ThreadHandle);

for i = 1, 10 do
  sinkComp:postMessage(i);
end
]], {sink = sinkstone});

print("Finish 1: ", comp1:waitForFinish());
print("Finish 2: ", comp2:waitForFinish());

What’s going on here? Well, the computicle ‘comp2′ is acting as a sink for information. Meaning, it spends its whole time just pulling work data out of its inbuilt queue. But, there’s a bit of trickery here, so a line by line explanation is in order.

  local msg = SELFICLE:getMessage();

What’s a ‘SELFICLE’? That’s the Computicle context within which the code is running. It is a global variable that exists within each and every computicle. This is the way the code within a computicle can get at various functions and variables for the environment. One of the computicle methods is ‘getMessage()’. This is of course how you can get messages out of your Computicle message queue. If you’ve done any Windows programming before, it’s very similar to doing “GetMessage()”, when you’re fiddling about with User32. I suspect the very lowest level mechanisms are probably similar.

  msg = ffi.cast("ComputicleMsg *", msg);

What you get out of ‘getMessage()’ is a pointer (as expected). In order to make any sense of it, you need to cast it to the “ComputicleMsg” type, which looks like this:

typedef struct {
	int32_t		Message;
	UINT_PTR	wParam;
	LONG_PTR	lParam;
} ComputicleMsg;

Again, looks fairly familiar. Basically, any data structure would do, as long as your computicles agree on what it is. This data structure works because it combines a simple “message”, with a couple of pointers, so you can pass pointers to other more elaborate structures.

  print(msg.Message*10);

Once we have the message cast to our message type, we can do some work. In this case, just get the ‘Message’ field, multiply it, and print it out. This is the working end of the computicle. You can put any code in here for the “work”. I can call out to other bits of code, fire of network requests, launch more computicles, whatever. It’s just Lua code running in a thread with its own LuaState, so the sky’s the limit!

  SELFICLE.Heap:free(msg);

And finally, you have to manage the bit of memory that you were handed. These computicles are simple, they are sharing a common heap across all of them, so I know the bit of memory was allocated from one heap, so I can just free it.

So, that’s the consuming side. What about the sending side?

local sinkstone = comp2:getStoned();

I need to tell the second computicle about the first one. There are only two communications mechanisms available. The first is to pass whatever I want as a list of parameters when I construct the computicle. The second is to use the computicle’s queue. In this particular case, I’ll use the former method and pass the computicle as a startup parameter. In order to do that though, I can only communicate cdata. I can not pass any LuaState based bits of information, because it becomes ambiguous as to who owns the chunk of memory used, and what’s the lifetime of that chunk.

The ‘getStoned()’ function takes a computicle and creates a heap based representation of it which is appropriate for sending to another computicle. The data structure that is created looks like this:

typedef struct {
	HANDLE HeapHandle;
	HANDLE IOCPHandle;
	HANDLE ThreadHandle;
} Computicle_t;

local comp1 = Computicle:create([[
local ffi = require("ffi");

The source Computicle is created. Keep in mind that a Computicle is an almost, but not quite, empty container waiting for you to fill with code. There are a couple of things, like the SELFICLE, that are already available, but things like other modules must be pulled in just like any other code you might write. The only modules already in place, besides standard libraries, are the TINNThread, and Computicle.

local stone = _params.sink;
stone = ffi.cast("Computicle_t *", stone);

local sinkComp = Computicle:init(stone.HeapHandle, stone.IOCPHandle, stone.ThreadHandle);

The other global variable besides 'SELFICLE' is the '_params' table. This table contains a list of parameters that you might have passed into the constructor. Some manipulation has occured to these items though. They do not contain type information, they are just raw 'void *', so you have to turn them back into whatever they were supposed to be by doing the 'ffi.cast'. Once you do that, you can use them. In this particular case, we passed the stoned state of the sink Computicle as the 'sink' paramter when the source computicle was constructed, so the code can just access that parameter and be on its way. It's easiest to think of the '_params' table as being the same as the 'arg' table that Lua has in general. I didn't reuse the 'arg' concept though for a couple of reasons. First of all, 'arg' is a simple array, not a dictionary. So, you access things using index numbers. I wanted to support named values because that's more useful in this particular usage. Second, since I'm not using it as a simple array, I didn't want to confuse matters by naming it the same thing as 'arg', so thus, '_params'.

In the above code, a computicle is being initiated using the value passed in from the sink stone. This is a common pattern. When it is desirable to construct a Computicle from scratch, the 'Computicle:create()' function is used. In this case, I don't want to create a new computicle, but rather an alias to an existing computicle. This is why I need to know its state, so that I can create this alias, and ultimately communicate with it.

Lastly, after everything is setup:

for i = 1, 10 do
	sinkComp:postMessage(i);
end

What's going on here? Well, here's what the postMessage() function looks like:

Computicle.postMessage = function(self, msg, wParam, lParam)
  -- Create a message object to send to the thread
  local msgSize = ffi.sizeof("ComputicleMsg");
  local newWork = self.Heap:alloc(msgSize);
  newWork = ffi.cast("ComputicleMsg *", newWork);
  newWork.Message = msg;
  newWork.wParam = wParam or 0;
  newWork.lParam = lParam or 0;

  -- post it to the thread's queue
  self.IOCP:enqueue(newWork);

  return true;
end

Remember, the only way to communicate to a computicle is to send it a bit of shared memory by placing it into its queue. So, postMessage just takes the few parameters that you pass it, and packages them up into a chunk of memory which is ready to be sent across via that queue. On this case, we have the alias to the Computicle we want to talk to, so the message does in fact land in the proper queue.

]], {sink = sinkstone});

This final part is just how we pass the ‘sink’ stone as a parameter to the constructor.

So, there you have it. In full detail. I can construct Computicles. I can write bits of script code that run completely independently. I can communicate between Computicles in a relatively easy manner.

As a lazy programmer, I’m loving this. It allows me to conceptualize my code at a different level. I don’t have to be so much concerned with the mechanics of making low level system calls, which is typically an error prone process for me. That’s all been wrapped up and taken care of. One of the hardest aspects of multi-threaded programming (locking), is completely eliminated because of using the IO Completion Port as a simple thread-safe queue. Simple synchronization is achieved either through queued messages, or through waiting on a particular Computicle to finish its job.

This construct reminds me of DirectShow and filter graphs. Very similar in concept, but Computicles generalize the concept, and make it brain dead simple to pull off with scrict rather than ‘C’ code.

I’m also loving this because now I can go more easily from ‘boxes and arrows’ to actual working system. The ‘boxes’ are instances of computicles, and the arrows are the ‘postMessage/getMessage’ calls between them. This is a fairly under stated, but extremely powerful mechanism.

Next time around, I’ll go through the actual Computicle code itself to shed light on the mystery therein.