schedlua – refactor compactor

The subject of scheduling and async programming has been a long running theme in my blog.  From the very first entries related to LJIT2Win32, through the creation of TINN, and most recently (within the past year), the creation of schedlua, I have been exploring this subject.  It all kind of started innocently enough.  When node.js was born, and libuv was ultimately released, I thought to myself, ‘what prevents anyone from doing this in LuaJIT without the usage of any external libraries whatsovever?’

It’s been a long road.  There’s really no reason for this code to continue to evolve.  It’s not at the center of some massively distributed system.  These are merely bread crumbs left behind, mainly for myself, as I explore and evolve a system that has proven itself to be useful at least as a teaching aid.

In the most recent incarnation of schedlua kernel, I was able to clean up my act with the realization that you can implement all higher level semantics using a very basic ‘signal’ mechanism within the kernel.  That was pretty good as it allowed me to easily implement the predicate system (when, whenever, waitForTruth, signalOnPredicate).  In addition, it allowed me to reimplement the async io portion with the realization that a task waiting on IO to occur is no different than a task waiting on any other kind of signal, so I could simply build the async io atop the signaling.

schedlua has largely been a Linux based project, until now.  The crux of the difference between Linux and Windows comes down to two things in schedlua.  The first thing is timing operations.  Basically, how do you get a microsecond accurate clock on the system.  On Linux, I use the ‘clock_gettime()’ system call.  On Windows, I use ‘QueryPerformanceCounter, QueryPerformanceFrequency’.  In order to isolate these, I put them into their own platform specific timeticker.lua file, and they both just have to surface a ‘seconds()’ function.  The differences are abstracted away, and the common interface is that of a stopwatch class.

That was good for time, but what about alarms?

The functions in schedlua related to alarms, are: delay, periodic, runnintTime, and sleep.  Together, these allow you to run things based on time, as well as delay the current task as long as you like.  My first implementation of these routines, going all the way back to the TINN implementation, were to run a separate ‘watchdog’ task, which in turn maintained its list of tasks that were waiting, and scheduled them.  Recently, I thought, “why can’t I just use the ‘whenever’ semantics to implement this?”.

Now, the implementation of the alarm routines comes down to this:

 

local function taskReadyToRun()
	local currentTime = SWatch:seconds();

	-- traverse through the fibers that are waiting
	-- on time
	local nAwaiting = #SignalsWaitingForTime;

	for i=1,nAwaiting do
		local task = SignalsWaitingForTime[1];
		if not task then
			return false;
		end

		if task.DueTime <= currentTime then
			return task
		else
			return false
		end
	end

	return false;
end

local function runTask(task)
    signalOne(task.SignalName);
    table.remove(SignalsWaitingForTime, 1);
end

Alarm = whenever(taskReadyToRun, runTask)

The Alarm module still keeps a list of tasks that are waiting for their time to execute, but instead of using a separate watchdog task to keep track of things, I simply use the schedlua built-in ‘whenever’ function. This basically says, “whenever the function ‘taskReadyToRun()’ returns a non-false value, call the function ‘runTask()’ passing the parameter from taskReadyToRun()”. Convenient, end of story, simple logic using words that almost feel like an English sentence to me.

I like this kind of construct for a few reasons. First of all, it reuses code. I don’t have to code up that specialized watchdog task time and time again. Second, it wraps up the async semantics of the thing. I don’t really have to worry about explicitly calling spawn, or anything else related to multi-tasking. It’s just all wrapped up in that one word ‘whenever’. It’s relatively easy for me to explain this code, without mentioning semaphores, threads, conditions, or whatever. I can tell a child “whenever this is true, do that other thing”, and they will understand it.

So, that’s it. First I used signals as the basis to implement higher order functions, such as the predicate based flow control. Now I’m using the predicate based flow control to implement yet other functions such as alarms. Next, I’ll take that final step and do the same to the async IO, and I’ll be back to where I was a few months back, but with a much smaller codebase, and cross platform to boot.


Parallel Computing is Child’s Play

Recently, my wife and I brought a new son into the world!  And that got me to thinking.

Some years back, I did some self study on linguistics and language development.  At the time, I was just doing some thinking on how best to communicate, how to write programs that are composable, just like spoken sentences.  One of things I learned from one of the books had to do with how babies learn language.  As one theory goes, they develop a core internal language first.  These are their early bits of associations and linkages.  Everything they learn after that is expressed using the core primitives they developed early on.

Armed with this knowledge, I went away and taught software engineering for a few years.  One of my core tenets was; software programming is nothing more than a specific conversation.  As software engineers, we are in the business of translating intentions from one domain to the next.  We talk to customers, who speak in their own language, and we have to eventually get that translated down into C, or assembly, or whatever.  The more closely the customer’s language matches the machine’s, the easier the translation, and less margin for error.  But, people don’t speak in machine code.

So what then?  Well, then comes the task of the various frameworks and language tools that we use as software engineers to translate from the high level human language to the very narrow and specific machine language.  At the lowest level, we might use C, or Javascript, or C#, or Lua.  Then on top of that there are innevitably various frameworks which help us express ideas in a more meaningful way, without having to work purely with the lower level primitives.  And so on and so forth.

What I’ve been exploring recently is how best to do parallel programming.  At the very core, my machine has a multi-core processor.  There is an OS, and I have a bunch of C based APIs to get various things done.  In the Lua language I have co-routines, which help in making tasks ‘parallel’, or at least cooperative.

Atop this core, I have built a scheduler in the form of the TINN environment, and thus far I can achieve quite a lot of apparent parallelism with the core primitives such as timer, waitFor, sleep, and the like.  Now I want to add some more higher level primitives.

There are two cases I want to cover.  The first is ‘when’.  That is, when some condition is met, I want to perform some action.  This is a natural part of English at least.  I can easily imagine having a conversation with someone where they’re trying to tell me what they need some machine to do, let’s say scheduling some event to occur:

“When ‘the first person comes into the factory’ ‘turn on all the machines'”

The first part of this sentence establishes the condition.  The second part specifies the action that is to occur once the condition is met.

Easy enough.  If I were to write it in code, it might look like:

waitFor(firstPersonArrives);
turnOnAllMachines();

That’s great, and you could already do this in TINN. But, the language doesn’t quite match the words that came out of my mouth. What I really want to write is the following:

when(firstPersonArrives, turnOnAllMachines)

Or even better, with some syntactic sugar

when firstPersonArrives do
  turnOnAllMachines()
end

I need a primitive ‘when’ which will take a predicate as its first argument, and an action as its second. Perhaps something like this:

local Task = require("IOProcessor")

local when = function(pred, func)
  local watchit = function()
    Task:yieldUntilPredicate(pred)
    func()
  end

  Task:spawn(watchit)
end

That will do the trick, and give me the function I need. What’s happening? Well, the when() function takes the predicate and the function, and spawns a task with a ‘waitFor()’ in it already. It’s the combination of the spawn() and waitFor() which essentially creates a parallel task, without the programmer having to deal with the very specifics of parallelism. All the programmer has to focus on is the cause and effect. Code that up, and let it go.

Having the ‘when’ in my vocabulary as a programmer is great. It enables a much easier conversation when I’m talking with someone. Whereas ‘when’ is great for covering a single event, the word “whenever” is great at covering multiple occurences. For example, a natural conversation might go like this:

Water the grass every tuesday

In code, it might be:

whenever(itIsTuesday, waterTheGrass)

Well, this is just a slight modification of the ‘when’ primitive. Basically, after the trigger event, spawn another task to wait on the exact same thing again.

local whenever = function(pred, func)
  local watchit = nil;
  watchit = function()
    Task:yieldUntilPredicate(pred)
    func()
    Task:spawn(watchit)
  end

  Task:spawn(watchit)
end

I think this is pretty nifty myself. Here is one contrived example of using these primitives. The English explanation would be:

Every 5 clock ticks, say “Halleluja!”
After the end of 25 clock ticks, stop.

That’s pretty easy to understand. How hard is it to code?

-- test_when.lua

local Task = require("IOProcessor")
local Timer = require("Timer")
local parallel = require("parallel")()


local counter = 0;

local function incrementCounter()
	counter = counter + 1;

	print("Counter: ", counter)
end

local function timeRunsOut()
	if counter >= 25 then
		return true;
	end

	return false;
end

local function stopWorld()
  print("Goodbye World!")
  Task:stop();
end


local lasttrigger = 0;
local function counterHits5()

  if counter % 5 == 0 then
    if counter ~= lasttrigger then
      lasttrigger = counter
      return true;
    end
  end

  return false;
end

local function sayHalleluja()
  print("Halleluja!")
end


local function main()
  -- Create a timer with the task of incrementing
  -- the counter every few milliseconds
  local t1 = Timer({Period=500, OnTime=incrementCounter})
	
  -- start the task to sing whenever we hit 5 ticks
  whenever(counterHits5, sayHalleluja);

  -- start the task to stop after so many ticks
  when(timeRunsOut, stopWorld);
end

run(main)

I find the ‘when’ and ‘whenever’ constructs to be fairly useful when trying to create code that I intend to run in ‘parallel’. By ‘parallel’ here, I mean they are fairly self contained units which may or may not actually run on multiple cores, but at the very least, I can think of them conceptually as independent actions.

Thus far in my programming career, I’ve made fairly good usage of the ‘for’, ‘do-while’, ‘while’, and various other control structures. Now that I’m doing more parallel and async programming, I find the addition of the ‘when’ and ‘whenever’ primitives to be a fairly useful construct for describing how things should work in a parallel universe. I can think of my atomic parallel nuggets, and then just code those nuggets serially. Then, I can use the when, whenever, and spawn constructs to stitch together an entire system.

So, there you have it. As children build up their language skills based on an internal dialog, so too must my programming language skills be built. The ‘when’, ‘whenever’ and ‘spawn’ are the core primitives of my parallel programming inner dialog.