A Cooperative Job System

This section assumes you are familiar with the difference between Multi Threading and Multi Processing.

Today’s computers have multiple processor cores, this can go into large numbers. With multi processor boards this can be as high as 64 cores on a single board at the time of this writing. It is clear that speed advancement can only be reached in today’s software by utilizing parallel processing. It is equally clear that powerful multi threading and multi processing elements must be part of any new language.

Today’s languages leave this mostly to external libraries, like C++ 11 delegates this to the STL. The only language I know of which has multi threading as part of the language is Ada. Ada does it pretty good but still on a low level which exists so that programmers can build their own multi threading universe on top of these elemental building blocks. They are better than what C++ offers but still relatively primitive.

What I’m proposing instead is a high level system based on our practical experience in a huge server application over the past years. This system has evolved over several stages until it reached today’s form and by doing so, we had to learn the hard way what does and doesn’t work with multithreading. In it’s latest stage it still has room for improvements, but it is already so powerful and practical that it has allowed us to rewrite our server system in a “building block” kind of way where the utilization of any number of processor cores is really easy.

Such a system should be part of the language itself, not an external library so that the compiler has control over all aspects especially when it comes to pointers (a topic for later). Having this all under the direct control of the language would eliminate the need for some OO stretches we had to make in order to implement this system in C++.

First, what does NOT work:

A) Having a HUGE number of Operating System Threads. Each thread uses up a lot of resources, mainly a pre-allocated stack of several MB (2MB in the Window standard setup), so that restricts the number of threads already. Now you can create several 100 Threads with that, but there are two problems: First if you have a server that must handle thousands and thousands of user requests like a game server, you still need more parallel entities than you can create even with the largest memory area and second, switching between these threads is very expensive. You create 100 threads and check the simple Windows performance tool in the Task Manager, you see the red line go up and up, which represents the system time your CPU spends or, in other words, time needed to switch between threads. Not to mention a 2MB stack per thread that is hardly used wastes most your memory for nothing in return. So this is not the answer

B) Creating threads as needed and destroying them when the task is finished. This is even worse, because you don’t know how many might be created at peak times, you may run out of memory plus creating and destroying an OS thread is EXTREMELY expensive. This this does not work at all.

What is the solution then?

Create a number of worker threads in relation with the number of processor cores and keep them alive. Then assign code to be executed to these threads. When one section of code finishes, another one is assigned (with the respective data).

In our lingo, these code/data objects are called a “Job”. A Job is basically a class derived from a baseclass that provides the functionality needed to carry out operations in parallel.

Here is where it gets interesting: Each code will eventually have to perform blocking operations, like sending a request to another thread or process and waiting for an answer. Doing this the naive way by blocking the whole thread, would lead to the problems described under A and B above. So the solution is, that the thread system (in the language) must “send data as a message” and then the code that called this “send” functionality must return control to the threading system. It must then be prepared to be called again in another state with the answer to it’s request.

This is a “cooperative Job system” because it’s the user code that relinquishes control when it realizes that it can not proceed without receiving more data from other sources. It is then prepared to react to this answer and proceed processing at another location in the code. There is no other way of doing this. Any non cooperative way would require the OS to move switch stack to the one of another function that should resume. With stacks being one cohesive area of data, this is basically not possible.

The simplest way to do this (and the way we do it) is by having an overloaded “int Run( int State)” function. The code in the Run() function consists of one big switch() statement. Each case terminates with a “return X” line where X is the state with which it wants the Run() function to be called when the answer arrives. The switch statement will then continue at “case X” when the answer arrives and voila, we have a cooperative Job system.

Of course there are many more intricate details which I won’t elaborate here and now, but suffice it to say that this system works beautifully and, when checking the processor load, we can see that all processor cores can be stretched to the full load with only very minimal calling of system code since there are no context switches necessary. All threads run constantly. A true time sharing system.

This is only half the system though. Our Job system is divided into two (actually now three) basic types of Jobs. One is called a “Server Job” and the other “Client Job”.

A server Job is a job that defines service requests and can be called from client Jobs. The server then wakes up when a request arrives, carries it out and returns to sleep. Server Job’s don’t have states in the above sense, because that would be detrimental to their responsibility of servicing many client Jobs with little wait time. Their task must be finished within one wake-up call, including sending an answer.

There are only few server Jobs and they are all what’s called a singleton. They exist only once in the system. A good example is a database Job that provides access to database entries and performs transactions on them to alter entries.

Client Jobs on the other hand are a dime a dozen. Whenever a user sends a request to our game server for instance, we create a Client Job that handles this request. The Client Job may even call other client Jobs to handle different aspects of the user request in parallel. These Child Jobs can be fire and forget or synchronized with the calling Client Job who then waits for the child Job to finish.

Finally we have recently been adding a type of “Hybrid Job” which is a Server Job that can run it’s own local Client Jobs, in case that a Server Job needs to call other Jobs and wait for an answer. It can’t really do that in the main loop, but uses it’s own local Client Jobs to do that.

All in all this system has been stress tested with 10s of thousands of Jobs in parallel. As long as one state of a Job does not occupy it’s thread for a lengthy period of time but rather performs short bursts of computation and then waits for an answer or new data, the reaction time is spectacular. We are using this system in our new game server now with great success. Not only does it allow us to use Multi Threading efficiently but it also makes it EASY to use since the programmer does not need to deal with low end constructs like signals and mutexes anymore. By creating our own database service based with this system we have also solved the problem of deadlocks when altering game objects.

Of course this system is currently Object Oriented and would have to be rewritten in order to work with a procedural programming paradigm but that should be easily possible.

In my opinion, any new language that is designed to use multi tasking must incorporate a system like this.

Advertisements

No Global Variables

WHAT? Yes that’s what I thought too when I came up with that idea. How am I supposed to implement a service code, like a memory database that holds objects to be fetched by other program parts? Yes at first glance it seems weird, but it can be done.

Think about it: Everywhere we hear the mantra “don’t create functions with side effects!” – And what better side effect is there than a function that modifies a global variable which in turn is used in a lot of other locations? Besides, if you want to use Unit Tests, how do you test this scenario?

So I agree completely with this axiom, that side effects are bad. And the availability of global variables invites the programmer to use them. “Oh just this once, since it’s easier than to redesign this code”. Yes and once more and again and again and before you know it, it’s a common practice.

My solution to this problem is NO GLOBAL VARIABLES PERIOD!

By eliminating them, the language will enforce clean coding by leaving the designer no choice but to have clearly defined Module interfaces.

Variables can only be declared inside a module and are available only inside the module in which they were declared. The can then be passed as actual parameters in a module call and thus be made available to a module, but they don’t outlive the lifetime of the module itself, or in other words, they exist only for as long as the module is running.

This makes Unit Testing a breeze. There are no global variables, there are no C++ objects with state variables, the Module is COMPLETELY defined by it’s actual parameters, NO SIDE EFFECTS AT ALL.

Imagine there is a huge hierarchy of modules which solve a complex problem. There will certainly be the need for something like “permanent variables” for instance a file could be permanently open as a log output. The file handle will then have to be created on the top level of the hierarchy and passed to the lower modules through the parameter interface.

Will this make the interface larger? No doubt. There are ways to keep interfaces neat and clean for instance by creating a data type that combines this handle with other commonly needed data in a record so that the parameter count can be minimized, but these are stylistic questions. I have heard some people argue that a function should never have more than one or two parameters. Obviously that will not be the case here, especially not at higher levels. Lower level Modules will tend to have fewer parameters than higher level ones, but there is nothing wrong with that. It’s just the way things are. If data are needed, they have to be brought to the location where they are needed somehow. Either through the parameter interface or through global variables or object state variables. And since we eliminate the latter two, there is only the Module interface.

I believe this will eliminate a lot of common problems and causes for hard to find bugs.

Forced Modularization

I assume you are familiar with the vague term “module” from Structured Design. This is not to be confused with the module from Modula-2. Our modules are basically small functions or procedures from other languages. Everything that would be “put in a box” in a Structure Chart would be a module.

There are generally two types of modules: Control Modules and Work Modules, both subsumed under the term “Module”.

A Control Module should only be able to call other modules and perform comparisons, for instance “if a=2 then call module X else call module Y” but should not be able to perform actual program modifications or calculations in itself.

A Work Module on the other hand has the complete feature set of the language available in order to perform all sorts of calculations or operations, but it is NOT allowed to call other Modules.

This may look strange at first glance. For instance, if a module processes a number of records from a datafile, say to print out a list of records which are due for payments, shouldn’t it be able to open the datafile, read one record after the other and close the file? Surely, the OpenFile or ReadRecord functionality are pretty complex and need to be encoded with a hierarchy of “modules” themselves?

Well that is true but in this case, perhaps the complete “module” that does the printing should itself be split up in a hierarchy of Control Modules and Work Modules in the first place with only small functionality like “Check if this record needs to be printed” or “Calculate number of days before due date” and so on. When you believe, that your Work Module should be able to call other modules in order to perform it’s duty, chances are, you have not dissected the problem well enough and that your “Module” is really a Frankenstein module that should be split up into a hierarchy of modules.

Clearly, I advertise for very small Work Modules and the reason is, the smaller a module is, the easier it is to test.

What about Functions? As in “a := root( 10,2)”? Functions should be just a specialized form of a Work Module which happens to return a value. Other than that, they should obey the same rules as Work Modules, with the exception that they can call other functions as well, since especially mathematical functions often need to use other mathematical functions. Furthermore, Work Modules can call Functions, but the return value of a function can not be tossed as in C where a function can be called without using the return value. And yes, this softens up the rule the Work Modules must not call other modules, but I believe this is necessary for mathematical or other expressions to be coded in a reasonable manner.

The syntax for modules should be created in such a way, that these rules can be enforced by the compiler easily. Furthermore it should be made thus, that multiple modules can be placed in one source file in order to make writing the program, or coding, easier. I would advise against this though and place each module into it’s own sourcefile, but I realize that many programmers would take this as too great a restriction. However, should there ever be an IDE that supports this type of workflow, it would also be prudent to enforce each module to have it’s own sourcefile.

It may not be necessary to split modules into two files, like a Definition and an Implementation file as in Modula-2 or .H and .CPP files as in C++ since the compiler can extract the calling convention from the module and store them into a binary file which will later be imported by those modules that use the called module.

This also implies, that binding of modules is done with a binary interface, not with an include system like in C++ where each definition part of a function is compiled whenever the .H file is included

A hierarchy of Control and Work Modules with one Control Module at the top, a tree of Modules, can be combined into a form of package called a “Subprogram”. This Subprogram can thus be compiled and linked into one binary or rather two binary files (the OBJ file for the linker and one with the binary link information for the compiler) and then handed out to other programmers or put into a library of Subprograms.

Coherence of Data and Code. Is it a mistake?

Just a brief reflection on something that has puzzled me for quite a while now.

I learned programming the old way, Basic, Assembler, Pascal, Modula-2, C and then C++ that’s my path. Except for C++ (with which I have been stuck for 20 years or so) the principle of keeping data and code together wasn’t really a topic. In fact, there was little that forced you to keep them together until C++ became popular.

Today, it’s a religious dogma. You must keep the data and the code together in a class. Don’t make your data elements public, then anybody can access them! Implement accessor functions instead. Nobody doubt’s this these days, but I have run into situations where this dogma is literally holding me back. Let me explain.

Making client server games the old fashioned way (meaning with a dedicated client application, not a web browser) provides you with the following challenge: Oftentimes you have to define data that is to be used on the client and the server. But of course, the code won’t fit. the code that access the data on the server often has references to other objects or code that only exists on the server and therefore can not be compiled or linked with the client, and vice versa.

So in my previous game I used the #ifdef statement extensively to make those classes compile one way on the server and another way on the client. This is of course a terrible crutch.

In my current game I came up with the solution to have a shared link library that holds the data. Then I add classes on the client and the server which have this data structure as a private member and then provide the separate access and computation routines for the client and the server.

But this simply tells me that the dogmatic “unity of code and data” is nothing that is natural. I am sure there are other example where code and data should be separate.

Currently there is no good solution, but I just want to submit as a suggestion that the religious view that code and data are inseparable may be false.

Another Example Of Bad Technology

Take a look at this article. It takes about the bugs that still plague today’s browser version. And is it a miracle? These browsers not only have to incorporate code to make different versions of Html render correctly, but also ActiveX components, run java, and a whole host of other crap I don’t even know about. Browsers are one of the biggest monstrosity in Software. That’s why I use Firefox. Although it may not be much better in that regard, at least it is Open Source so people can check (although few do I imagine 😀 ) that there is no spyware in it.

My main point is however that today’s software development is so terribly complicated due to the requirement for interconnection of different software, different device types, different problem domains, different networks, that it gets slower and slower and more and more vulnerable. Did you know that the DOW (or DOD as it is officially called these days) considers cyber attack the number one thread to the safety of the USA? What does it say about the quality of today’s software when we have to be more afraid of a hacker than we were of the Soviet Union?

And if you don’t agree, check out this article here before you fly again.

 

The Compiler Builder Toolkit

There is an Open Source project out there that aspires to replace GCC as the predominant Open Source compiler system. And while that is still along way down the road, their C++ compiler Clang is already very good and the whole toolkit is used extensively i Apple system software.

What’s good about this is that the Intermediate Represenatino (IR) a sort of virtual RISC processor, is well documented and allows even people with little experience to build their own compiler. Although it will probably not be competing with Visual C++ anytime soon, it’s a good way to learn about compilers.

If you’re into this sort of stuff, check it out.

 

Another Fatality

I just came across this article here: http://www.drdobbs.com/architecture-and-design/farewell-dr-dobbs/240169421

This was kind of a shock to me but it fits right into the tenor of my last post. Although in Germany we did not read Dr.Dobb’s Journal alot, the fate of many German IT journals was the same, even before the advent of the internet to the level we have now. Magazines became nothing but test publications with the eternal repetition of “the 10 best printers” etc. They adjusted earlier to a shifting demand I believe. the kind of people who dealt with computers in the 80’s and 90’s were more the active type, partly because there wasn’t much software and people had to program in order to do anything with their machines.

With the advent of more software came the decline in user qualification. More and more people used computers who didn’t even know how such a machine wors and consequently the IT magazines catered to this clientele. So there are a bunch of those magazines still out there, but they are all of flat content. Nothing of the like of Dr.Dobb’s Journal or, in Germany, c’t Magazine. Which is still out there but has turned in one of those simplified magazines.

Times change and not for the better, that’s for sure. When I hear programmers talk these days, I have the feeling they live in a different world. It’s all about abstract concepts, meta language features, internet connectivity, and yes “the cloud” (whatever that is). It’s all hot air. Do applications get better in these days of “esoteric IT specialists”? Not that I see it. There is nothing I would do in the latest version of MS Office that I could not do in Office 2003.

When you read about the latest features of the C++ programming language it sounds like Jean Paul Sartre discussing french expressionism in french. I have no idea who even needs all this. And yet it is so complicated that it has the potential to break applications by means of subtle programming mistakes that may take forever to fix. That’s why I stay away from most of this stuff and only use a few of the new features.

Well, whatever, time moves on, but to me it looks more and more like a “The Emperor Has No cloths” effect.