Sunday, July 8, 2012

Golang: The Mach programming model in Go

Last week's post was only a prelude to what I really wanted to show you is possible using Go. Something that I call the Mach programming model.

In the Mach microkernel, core operating system functions such as memory management, disk management, file system handling, device management, and the like run as separate tasks. These tasks communicate with each other by sending messages to ports. The Go programming language uses a similar concept, and allows goroutines to communicate through channels. This allows you to write programs that work much alike the Mach microkernel.

The basic idea is that you break your program up into services. A service manages a resource. The service is being run by a manager. You can get service by issuing a request. The request is communicated through a port, or in the case of Go, a channel.
const (
    DoSomething = iota
    DoSomethingElse
    DoSomethingNice
    DoSomethingCool
)

type Message struct {
    Code  int
    Args  []interface{}
    Reply chan *Message
}

func DoRequest(manager chan *Message, code int, args ...interface{}) (reply *Message) {
    reqArgs := make([]interface{}, 0)
    for _, a := range args {
        reqArgs = append(reqArgs, a)
    }
    replyChan := make(chan *Message)
    manager <- &Message{code, reqArgs, replyChan}
    reply := <-replyChan
    return
}

func ManagerGoRoutine(in chan *Message) {
    for {
        req := <-in

        switch req.Code {
            // handle request
            // ...
        }

        req.Reply <- &answer
    }
}
So, what is going on here? A request is a message that has a request code, which is a constant (that is easily enumerated using iota). Additionally, the request may have a variable number of arguments. Arguments can be of any type you like. The request also includes a reply channel, on which the requestor will receive an answer. The request is written to the service manager's channel.
All the manager does is sit in an infinite loop in its main goroutine answering requests. It sends the answer to the Reply channel that is in the request. The reply is also of type Message, so that it can have all kinds of replies through the Args field.

Try doing this in plain C — it's hard. In Go, you practically get everything for free. In good old C you can do this using pthreads and pipes. Pipes aren't nearly as easy to use as channels. And that trick we pulled with the request's arguments, that's near impossible to do in C. Sure there is va_list but it's limited; you can't make an array with varying typed elements in C.
As a solution in C you might pass the address of the va_list through a pipe, which is scary because the va_list points into the stack memory of the requesting thread. It's a recipe for stack corruption. Now, because the requesting thread immediately blocks and waits for a reply, this just might work, but it's hackish. In Go however, the code is easy and clean, and note that all of this is possible even though it's a strictly typed language.

In the above code, the manager switches on a request code. You might as well include a function pointer in the request and call that. Now the question rises, why not call the function directly anyway? You would have to use resource locking, and things would work the ‘traditional’ way.
The answer is that the Mach programming model evades the traditional approach on purpose. It is another way of looking at large codes in which a variety of resources are managed. It's a microkernel design rather than a monolithic one. It models the program flow as an information flow.
This different way of thinking gives a level of abstraction that leads to easier to understand code, better code maintainability, and (hopefully) fewer bugs.

Ultimately, the Mach kernel for operating systems was considered a failure because it yields lower performance than its monolithic counterpart. Nevertheless it remains an interesting concept and you might as well use it in places where you don't need that ultra-high performance. You can couple this model with asynchronous networking code and then it really starts to shine.
What used to be hard in C, in Go you get for free.

Sunday, July 1, 2012

Golang: Master/Worker in Go

The master/worker pattern is used to get an amount of work done by a number of workers. Each worker grabs an item from a work queue and does the work on that item. When the worker is done, it will grab the next item from the work queue, and so on until all the work has been done. 
The cool thing is that all the work can be done in parallel 
(if the work items have no dependencies on each other). 
The speedup practically scales linearly with respect to the number of CPU cores used to run the workers. The master/worker pattern can be implemented on a distributed/cluster computer using message passing or on a shared memory computer using threads and mutexes.

Implementing master/worker for a shared memory system in Go is a doddle because of goroutines and channels. Yet I dedicate this post to it because it's easy to implement it in a suboptimal way. If you care about efficiency, take this to heart:
  • Spawn a worker per CPU core beforehand. If you spawn a worker per item, you are spawning too many threads. No matter how cheap spawning a thread may be, spawning fewer threads is cheaper.
  • It's a shared memory model. So pass pointers rather than full objects.
  • The workers never signal when they're done. They don't have to. Instead, the master signals he is out of work when all work has been done.
Lastly, there is no point in making the master a goroutine by itself. The master does fine running from the main thread.

So, let's code. The function WorkParallel processes all the work in parallel. Capital Work is a struct that represents a single work item, lowercase work is an array (slice) that holds all the work to be done. The work queue is implemented using a channel.

func WorkParallel(work []Work) {
    queue := make(chan *Work)

    ncpu := runtime.NumCPU()
    if len(work) < ncpu {
        ncpu = len(work)
    }
    runtime.GOMAXPROCS(ncpu)

    // spawn workers
    for i := 0; i < ncpu; i++ {
        go Worker(i, queue)
    }

    // master: give work
    for i, item := range(work) {
        fmt.Printf("master: give work %v\n", item)
        queue <- &work[i]  // be sure not to pass &item !!!
    }

    // all work is done
    // signal workers there is no more work
    for n := 0; n < ncpu; n++ {
        queue <- nil
    }
}

func Worker(id int, queue chan *Work) {
    var wp *Work
    for {
        // get work item (pointer) from the queue
        wp = <-queue
        if wp == nil {
            break
        }
        fmt.Printf("worker #%d: item %v\n", id, *wp)

        handleWorkItem(wp)
    }
}

There is more than one way to do it, and I can imagine you wanting to rewrite this code to not use any pointers in order to increase readability. Personally I like it with pointers though because of the higher performance. Whether you actually need this performance is another question. Often it is largely a matter of opinion, even taste. In fact, Go itself isn't all that high performing. But if you want to push it to the max, then by definition, the pointer-based code will outperform the code without pointers.

Sunday, June 3, 2012

OS X Game Development Using Cocoa NSOpenGLView

Every once in a year or so I get an uncontrollable urge to write a game. I like classic arcade games, the kind where you have a spaceship and zap alien monsters. Traditionally you could draw sprites by copying tiles of pixels to screen memory, nowadays we use OpenGL. If you want to do this on the Mac, use Cocoa and its NSOpenGLView class.

Coming from the Linux world, I became somewhat attached to the SDL library. SDL is great but under OS X, it doesn't feel native and the end product isn't as good. The differences are in little things like the application menu, app icon, and support for different keyboard layouts. So let's just use OS X's native Cocoa layer and make a great game.

First off, Cocoa is an API for the Objective-C programming language. Since Objective-C can be mixed with plain good old C, we can write the entire game in C and have the display be a front end written in Objective-C and using NSOpenGLView.
If you google around for "NSOpenGLView tutorial" or "mac opengl" you'll find a lot of old code and horror stories. Using OpenGL on the Mac used to be much harder than it is today. Let's get started.

Making an OpenGL capable view
Like always in Cocoa, create your own new view class derived from an already existing view class:
@interface GameView : NSOpenGLView

@end
In Interface Builder (IB) draw an NSOpenGLView into the main window and change its class to the GameView class that we just made. Be sure to enable double buffering in the Attributes Inspector.
In GameView.m, implement this stretch of code (see below for explanation):
@implementation GameView

- (void)prepareOpenGL {
    init_gl();

    // this sets swap interval for double buffering
    GLint swapInt = 1;
    [[self openGLContext] setValues:&swapInt forParameter:NSOpenGLCPSwapInterval];
   
    // this enables alpha in the frame buffer (commented now)
//  GLint opaque = 0;
//  [[self openGLContext] setValues:&opaque forParameter:NSOpenGLCPSurfaceOpacity];
}

- (void)drawRect:(NSRect)dirtyRect {
    glClear(GL_COLOR_BUFFER_BIT);   
    glLoadIdentity();
  
    draw_screen();
   
//  glFlush();
// the correct way to do double buffering on Mac is this:
    [[self openGLContext] flushBuffer];
   
    int err;
    if ((err = glGetError()) != 0)
        NSLog(@"glGetError(): %d", err);
}

- (void)reshape {
//  NSLog(@"view reshape {%.02f %.02f}", [self frame].size.width, [self frame].size.height);
   
    // window resize; width and height are in pixel coordinates
    // but they are floats
    float screen_w = [self frame].size.width;
    float screen_h = [self frame].size.height;

    // here I cast floats to ints; most systems use integer coordinate systems
    screen_resize((int)screen_w, (int)screen_h);
}

- (BOOL)acceptsFirstResponder {
    return YES;
}

- (void)keyDown:(NSEvent *)theEvent {
    if ([theEvent isARepeat])
        return;
   
    NSString *str = [theEvent charactersIgnoringModifiers];
    unichar c = [str characterAtIndex:0];
   
    if (c < ' ' || c > '~')     // only ASCII please
        c = 0;
   
    key_down([theEvent keyCode], c);
}

- (void)keyUp:(NSEvent *)theEvent {
    key_up([theEvent keyCode]);
}

@end
This code unites the Objective-C API with the standard C code. The pure C init_gl() function should set up the projection and modelview matrices and other OpenGL parameters just like before with SDL, GLUT, GLFW or any other library. Likewise, screen_resize() should call glViewport() to update OpenGL's viewport.

As you can see, some things are a little different on the Mac, like having to enable swapping for double buffering. If you don't do this, you won't see anything being displayed.
Also note the keyUp and keyDown event handlers. Remember the SDL event loop? This is hidden in Cocoa, already built-in. All you do is write the event handlers. You might also add mouse event handlers.

Frame rates and timings
Frankly, the way that screen redraws work under Cocoa was a little mind-bending for me in the beginning. With SDL you just set up a main loop, redraw the screen, do game mechanics, and call SDL_Delay() to sleep some milliseconds for getting the frame rate right. In Cocoa, you can not have a main loop because it would interfere with the invisible (it's hidden!) main event loop. So to get a frame rate going you have to set up a timer that periodically updates the screen. But rather than just that, the frame rate timer has to drive the entire game: do animations, do game mechanics, and finally tell Cocoa to redraw the screen.

To get a super consistent frame rate in SDL I would actually take into account the time passed since the last loop. In Cocoa, the timer fires just like you specified (its accuracy is good enough) but rather than having a frame rate, it's the rate at which you drive the game. The end result is practically the same. You can't really control the frame rate anyway because OS X decides what happens on the display — and it does a nice job too, no need to worry about flicker or tearing whatsoever.

Setting up a timer sounds easy enough, but there is more to it. When the window is minimized or goes out of focus, you will want to stop the timer to freeze the game. In Cocoa you can catch these window events by implementing the NSWindowDelegate protocol. So by adding the timer and the protocol to the GameView class, we get exactly what we want.

In GameView.h change the class declaration to:
@interface GameView : NSOpenGLView<NSWindowDelegate>
In GameView.m add this code:
static NSTimer *timer = nil;

- (void)windowDidResignMain:(NSNotification *)notification {
//    NSLog(@"window did resign main");
    [timer invalidate];
   
    game_deactivate();      // freeze, pause
    [self setNeedsDisplay:YES];
}

- (void)windowDidBecomeMain:(NSNotification *)notification {
//    NSLog(@"window did become main");
   
    game_activate();
    [self setNeedsDisplay:YES];
   
    timer = [NSTimer timerWithTimeInterval:FRAME_INTERVAL
               target:self
               selector:@selector(timerEvent:)
               userInfo:nil
               repeats:YES];
   
    [[NSRunLoop mainRunLoop] addTimer:timer forMode:NSDefaultRunLoopMode];
}

- (void)timerEvent:(NSTimer *)t {
    run_game();
    [self setNeedsDisplay:YES];
}
This code ties an NSTimer to a pure C function run_game()that will do a single run of the game "loop". Next we ask Cocoa to redisplay the view by issuing setNeedsDisplay:YES. Cocoa will pick this up and send a -drawRect: message, which will call draw_screen(). Realize that this code redraws the screen on every frame, which is good for arcade action games.
When the window is minimized or goes out of focus, the game is put into a paused state and the timer is stopped. We ask for one more redraw so that we can show a nice pause screen.

To be able to detect when the window goes out of focus, we need to tell Cocoa that the GameView should receive windowing events, otherwise it doesn't see them. Put this in AppDelegate.h:
#import "GameView.h"

@property (assign) IBOutlet GameView *gameview;
Put this in AppDelegate.m:
@synthesize gameview;

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification
{
    // Insert code here to initialize your application

    [[self window] setDelegate:[self gameview]];
}
In IB, connect the GameView to the gameview outlet we created. (Or use the Assistent Editor). Now when the window goes out of focus, the application will send that event to the view, and our timer will stop and the game will enter paused state.

One more thing
I like it when games can toggle between windowed and full screen mode. Especially for small, simple arcade games it adds to the experience. In code, toggling screen mode is always a bit of a hassle. Well, it was until OS X Lion added support for full screen apps. In XCode 4 you can select the application window in IB and select "Primary Window" for Full Screen in the Attributes Inspector — and that is all. If your screen_resize() function is working properly, it just works.

Concluding
As always, it takes some effort to get Cocoa going. But when it does, you get some really nice things in return. Having the game integrate with OS X adds so much value. It's simple things like having a decent About dialog, properly supporting the native keyboard layout, having the standard full screen apps button in the window title bar. Suddenly the game looks and feels like a native OS X app.
This concludes this tutorial on OpenGL under OS X. Read on for two more musings in case you haven't had enough yet.

Notes on portability
Cocoa is OS X-only so we break portability with other platforms by choosing NSOpenGLView. However, since the entire game is written in C and only the front end is "Mac native" you only have to port the front end to other platforms.
You might also choose to write the entire game in Objective-C. It's a nice language for developing games, but do note that today Apple's Objective-C 2.0 does not port nicely to other platforms — other than iOS (and even Cocoa apps do not port nicely to iOS). Sticking with C or C++ ensures your core game code is easily ported.

Why OpenGL?
In the earlier days of computing, there was no such thing as a graphics processor. There was a video chip that put a region of memory (the screen pixel buffer) onto the monitor display at the right refresh rate. Drawing sprites was done by copying tiles of pixels into the screen memory region. That was OK with screen resolutions like 320x200 or 320x240, but on today's screen resolutions you would run the CPU hot just by copying pixels. So nowadays we have hardware accelerated graphics and we use OpenGL to tell the video hardware what to display. The OpenGL library is like the standard C library for displaying graphics. Moreover, it's tailored to the graphics processing pipeline that is built into the hardware. So even if you're just doing 2D graphics, please use OpenGL. It's hardware accelerated and your games won't melt the CPU because it's the video hardware that is doing the hard work.

Monday, May 14, 2012

Hypothetical Machine Language

Last September, I wrote about virtual machines and CPU emulators, and described a virtual machine, or simulator for a non-existing CPU. It was a bit whacky, but then in April there suddenly was the Notch DCPU-16 specification. Many people jumped on it and the first implementations have already sprung up at GitHub. It inspired me to go back to my own virtual machine and completely redesign its instruction set.

Notch's DCPU-16 is a fascinatingly simple (and therefore easily implemented in a simulator) and I'm somewhat surprised that it works at all. For example, there is not even a carry flag. A lot of instructions appear to be missing [but it turns out you can do without them ... with some trickery]. There are instructions for conditional execution rather than the usual compare and branch. Push and pop are not instructions, but some kind of operator.
The registers are named A, B, I, X, Y, which sounds a lot like an 8-bit Z80 so I guess that's where he got his inspiration from. If you think about CISC or RISC then DCPU-16 is a MISC (minimal instruction set computer). Anyway, Notch is writing a game which could be a reason for keeping things simple.

The master, the teacher
Purely coincidentally, Donald Knuth updated his webpage last September with a message that after about 12 years of work his hypothetical machine language MMIX had finally reached the frozen state. MMIX defines a 64-bits RISC machine with a massive amount of 256 general purpose registers. His register naming $0-$255 looks a bit odd, but he was inspired by MIPS and SPARC.
Knuth goes far enough so that this machine could probably actually be built, I mean in hardware. There is floating point support and even register banking, virtual memory and page tables are described. Virtual memory is important if you want to be able to run any modern operating system on the CPU. Think booting Linux in the simulator. MMIX is fascinating stuff although still hugely simplified for educational reasons.
A real-world CPU does not have 256 general purpose registers like MMIX has, it's more likely to be something like 16 or 32. Modern CPUs may have hundreds of registers but they are not general purpose registers in the sense that a programmer can access them freely. The registers are dynamically renamed (mapped) to other registers to aid parallelism that arises from out-of-order execution.

Designing your own
When you design your own system, you will find that a lot of time has to be put into designing the instruction set and its instruction encoding. In theory, you can think up whatever set of instructions you like. But then comes the hard part; all these instruction have to be encoded in a sensible way. Simply numbering down opcodes (like in MMIX and DCPU-16) is extremely wasteful and you'll likely run out of available bits in the opcode space when you do. If you want to have a lot of addressing modes and a lot of registers, you will again run out of bits to store all this information in [unless, of course, you are using really long instruction codes]. The game is to come up with an encoding scheme that works nicely and yet provides a versatile instruction set for the programmer to work with.

The three machines
My own design uses a happy mix of the x86, 68000 and ARM instruction sets. Actually, I made several designs, aptly named machine #1, #2 and #3 (just working titles). Machine #1 is a 32-bit computer with 16-bit instruction words. It has load/store architecture but arguably it is not a true RISC system because immediate moves are encoded in three words. Its successor, machine #2, is a 64-bit computer with instructions encoded in still only 16 bit words, but immediate moves may take up to five words. And finally, machine #3 is a 64-bit RISC system in which all instructions have an equal length of 32 bits.

The first two machines each have 16 general purpose registers (named r0-r15) plus a program counter (pc), stack pointer (sp), and status register (sr).  The instructions are encoded in 16-bit words. Most instructions have an encoding that looks like this: oooooaaarrrrRRRR (o = opcode bit, a = addressing mode bit, r = source register bit, R = destination register bit, with MSB on the left side).
The addressing mode says whether to address a single byte, a word, or a 32-bit long word. The 64-bit machine has an additional mode for addressing 64 bits. There are no indirect addressing modes like exist on CISC systems, it's all register-to-register or register-immediate. In immediate mode the source register bits are unused and the value is stored in additional words.

Since sp is not a general purpose register in this design, I added a special code for instructions that manipulate sp. This way, you can still work with sp like you normally would, but the sp register can not be used for every operation. For example, it generally makes no sense to do bitwise operations on sp or to multiply sp with some value. On the other hand, you will want to be able to do adds and subtracts on sp. So there are opcodes that provide this functionality.

Machine #3, the 64-bit RISC system, is totally different from the other two. It has 32 registers where pc is equal to r31 and sp is r30. All instructions are encoded in 32-bit words. Here, most instructions can have three operands (three registers or two registers and an immediate). The instruction encoding uses this property to group many different operations together under a single base opcode. The result is that there is lots of room left for future extensions. This instruction encoding scheme is much like how PowerPC and MIPS work. On the MIPS, the types of instruction encoding have cool names like R-type (three registers), I-type (with immediate), J-type (jump). I must say, the MIPS encoding scheme is near perfect; simple, yet elegant and everything fits.

If you want to know more details on the instruction sets of these three machines, see the references below for a link to the design document.

From completion to perfection
Unless you are designing a minimalistic computer, you have to define an instruction set that is complete, something you can work with.
Operations that are easily forgotten are add-with-carry, sign extending, signed and unsigned multiply and division, and how to enable and disable interrupts. Maybe you want to have something like rdtsc to do high profile timings, or a cpuid instruction that tells what kind of CPU it is. MMIX has a register that holds the serial number.
Modern CPUs all do floating point arithmetic.Then there are things like SIMD instructions, processor virtualization support, enhanced security like trusted execution, and possibly GPU integration. But these are advanced topics that I haven't bothered with.

CPU simulators are fun. Although DCPU-16 and my own work are just toys, it's educational to tinker with what goes on inside a CPU. Other than emulating existing processors, you can even simulate the CPU of the next decade today.

Refs
Donald Knuth's MMIX: a RISC computer for the third millenium
Notch's DCPU-16 specification
My three designs with working title SYSTEM
ARM and Thumb-2 Instruction Set Quick Reference Card
PowerPC User Instruction Set Architecture Book I
MIPS Instruction Coding