Monday, May 03, 2010

New blog, hacking, cache influence on performance, iPad etc

I noticed I have a bunch of followers here. I don't know how much you guys follow up on my posts, but if you are still interested in reading about the stuff I write about I recommend you check out my new blog athttp://assoc.tumblr.com/. It is basically the same topics as this blog. I am not completely convinced yet, but I might discontinue using blogger and start with tumblr instead. Seems easier and prettier. Still haven't found any bloggging service well suited for writing about programming (syntax coloring of code snippets etc). The last topics has been about what is in the headline. In particular I recommend reading about how the cache affects the performance of your program. It really changes how you write and think about code. When calculating a*(b+345)+(d/89)*c+4... and it is faster than reading a value from memory it really changes your ideas about how to code. People are still too stuck in the idea that CPU's are slow and memory fast. In fact memory is so dam slow that calculating something and storing the result for later retrieval is usually considerably slower than just redoing the calculation. Ok, it is a bit more complicated than that. It all depends on what is in the cache and what isn't. But you can read that on tumblr.

Sunday, January 17, 2010

C/C++ Quiz: the comma operator

I never cease to amaze me how I am always learning new things when programming C/C++ even after this many years. However I thought that mostly related to quirks in C++ and C++ template stuff. Yesterday I discovered something in C, which I kind of think I should have known. Especially since I have used it countless times without really knowing it. Why not make this a little quiz, to see if you really thought about it too.

You have probably written code like this before int x = 2, y = 3 or for (i = 0, j = 1; i < size; ++i, ++j). So here is the quiz. Without looking up in a reference or googling. What does this do, and print out?


int i = 5, size = 5;
i < size || (i = -1), ++i;
printf("%d\n", i); 
 

Answer: It increments i but wraps when becomes size or bigger. Meaning incrementing i when it is size or larger sets it to zero. So 0 is printed out. How is how it works:

  1. The || operator will only evaluate the right expression if the left one was false. Because the right expression does not need to be evaluated to determine that the whole expression is true when left is true.
  2. So when i is 5 the left expression is false and i is thus set to -1.
  3. The comma operator is an expression operator. a, b makes sure b is evaluated after a. Meaning ++i will always be evaluated, but after all the other expressions that needs to be evaluated to find the value of the expression.
So it could have been written as:

int i = 5, size = 5;
if (i >= size)
  i = 0;
++i;
printf("%d\n", i); 
 

What got me into this was trying to understand this macro found in the source code of the lua script language:


#define luaL_addchar(B,c) \
  ((void)((B)->p < ((B)->buffer+LUAL_BUFFERSIZE) || luaL_prepbuffer(B)), \
   (*(B)->p++ = (char)(c)))
 

It is basically used to copy characters into a buffer. B->p is current position in buffer. The code makes sure that luaL_prepbuffer is called if the size of the buffer is exceeded. That function will empty the current buffer (passing on the contents) and making it ready to receive more characters. So the current pointer is reset to the start.

The question is of course why do this? Probably because it makes it possible to treat the macro more like a function. An expression can be placed most places a function call can be placed. However multiple statement, even if they are enclosed by {} can not.

This is legal after current definition

for (i < 0; i < size; luaL_addchar(B,c))
 
But needles to say it would not have been legal if luaL_addchar(B,c) had expanded to something like this in the for statement:

for (i < 0; i < size; {if (B->p >= B->buffer+LUAL_BUFFERSIZE) 
                         luaL_prepbuffer(B); 
                       *B->p++ = c;})
 

Wednesday, January 13, 2010

Interpreter pattern in Go using closures

I recently had to create some code using the interpreter pattern from GoF. However I didn't have my Design Pattern by the Gang of Four ready so I had to look it up at wikipedia. That got me looking at example implementations in C# and Java. Being all about Go for the time being it got me thinking what the same code would look like in Go using closures instead of classes. Just like I demonstrated with other patterns in previous posts.

The code below demonstrates the interpreter pattern by implementing an interpreter of Reverse Polish notation as described on the wiki page. The wiki example uses a class to implement each grammar rule. Here we use a closure. A higher order function will return a function which when run will evaluate the grammar in given context.


import "fmt"
import . "container/vector"
import . "strings"

type Expression func(variables map[string]int) int

func Number(number int) Expression {
  return func(variables map[string]int) int {
    return number
  }
}

func Plus(left, right Expression) Expression {
  return func(variables map[string]int) int {
    return left(variables) + right(variables)
  }
}

func Minus(left, right Expression) Expression {
  return func(variables map[string]int) int {
    return left(variables) - right(variables)
  }
}

func Variable(name string) Expression {
  return func(variables map[string]int) int {
    return variables[name]
  }
}

What is interesting to notice is that the Java version using classes to define grammars takes up 43 lines, while the Go version takes 25 lines. The C# version takes even more lines: 63. However that is in large part because the approach is a bit different. The Evaluator takes about the same number of lines.


func Evaluator(expression string) Expression {
  var expStack Vector
  for _, token := range Split(expression, " ", 0) {
    switch {
    case token == "+": 
      subExpression := Plus(expStack().(Expression), 
                            expStack().(Expression))
      expressionStack.Push(subExpression)
    case token == "-": 
      subExpression := Minus(expStack().(Expression), 
                             expStack().(Expression))
      expressionStack.Push(subExpression)
    default:
      expressionStack.Push(Variable(token))
    }    
  }
  syntaxTree := expStack().(Expression)
  
  return func(context map[string]int) int {
    return  syntaxTree(context)
  }
}

The test code saves some lines on having map as a builtin type.

func main() {
  expression := "w x z - +"
  sentence   := Evaluator(expression)
  variables  := map[string]int {"w" : 5, "x" : 10, "z" : 42}
  result     := sentence(variables)
  fmt.Println(result) 
}

One could change the code to have the + and - operator share some more code. But it wouldn't increase the code size as in the C# example.

func plus(a, b int)  int { return a + b }
func minus(a, b int) int{ return a - b }

func BinOp(left, right Expression, op func(a, b int) int) Expression {
  return func(variables map[string]int) int {
    return op(left(variables), right(variables))
  }
}

Thursday, December 31, 2009

Design patterns in Go programming language

It has been said that design patterns is a symptom of language deficiency. If you need a pattern that indicated a language feature should have existed instead.

Here I'd like to show how many class design patterns can be simplified in the Go programming language to look less like patterns and more like language features. This post was inspired by previous discussions online (Joe Gregorio) about how design patterns were rarely talked about in the Python community, due to the simple fact that in dynamic languages, the need for specific patterns isn't really there. The language often supports directly what you simulate with a pattern. The examples I will use will mostly be related to computer games. Meaning examples will be about classes and objects you typically find in a game engine

Command Pattern

Let's say we have a game editor which lets us place sprites in a game world.

The code below shows how we might imagine this could be done in C++. When the user click on a position, that position pos is given to a function along with the sprite which will be placed there.


class Command {
 virtual void Do() = 0;
 virtual void Undo() = 0;
};

class PlaceSpriteCmd : public Command {
 Sprite* _sprite;
 Point _oldpos, _newpos;
 
public:
 PlaceSpriteCmd(Sprite* sprite, Point pos) : 
  _sprite(sprite), _newpos(pos) 
 {
  _oldpos = sprite->position();
  
 }
 
 void Do() {
  sprite->setPosition(_newpos);
 }
 
 void Undo() {
  sprite->setPosition(_oldpos);
 }
 
};

static CommandStack _undoStack, _redoStack;

void PerformUndoableCmd(Command *cmd) {
 cmd->Do();
 _undoStack.push(cmd);
}

void UndoLastCmd() {
 Command* cmd = _undoStack.pop();
 cmd->Undo();
 _redoStack.push(cmd); 
}

void onPlaceSprite(Sprite* sprite, Point pos) {
 Command *cmd = new PlaceSpriteCmd(sprite, pos);
 PerformUndoableCmd(cmd);
}

The code is written with clarity in mind, so it is not meant to compile. It has no error checking, would probably leak memory etc.

It should thus be clear that supporting Undo in C++ require us to:
  1. Create a Command base interface.
  2. For each command we need a concrete subclass of this interface.
  3. Three methods have to be implemented at least in these subclasses: Constructor, Do and Undo.
  4. We need to define some member variables in concrete subclass to store enough information to be able to perform the undo. E.g. in the case above we store the both current and new position to support undo and redo.

Since Go supports closures, functions are essentially first class objects which is in many ways what we simulate with Command subclasses, this becomes a lot simpler:


func MakePlaceSpriteCmd(sprite *Sprite, newpos Point) (undo, redo func()) {
 oldpos := sprite.Position()
 undo = func() { 
  sprite.SetPosition(oldpos) 
 }
 
 redo = func() { 
  sprite.SetPosition(newpos) 
 }
 
 return
}

type Command struct {
 undo, redo func()
}

var undoStack, redoStack CommandStack

func PerformUndoableCmd(undo, redo func()) {
 redo()
 undoStack.push(Command{undo, redo})
}

func UndoLastCmd() {
 cmd := undoStack.pop()
 cmd.undo()
 redoStack.push(cmd); 
}

func onPlaceSprite(sprite *Sprite, pos Point) {
 undo, redo := MakePlaceSpriteCmd(sprite, pos)
 PerformUndoableCmd(undo, redo);
}

It might not look a lot simpler, but that is mainly because of a certain fixed amount of code that has to be both places. What should hopefully be clear from the example however is that the difference becomes more noticeable as one starts adding commands. In the C++ case that involves creating a whole class.

Strategy Pattern

The main motivation behind the strategy pattern is to avoid an explosion in number of subclasses and code duplication. E.g. consider a real time strategy game with sprites for Allied tanks, Axis tanks and Soviet tanks. All the sprites are rendered differently, and might have different amounts of armor, gas tank volume etc. The tanks might have different behavior like cautious, aggressive, sneaky etc. The naive approach would be to create a subclass of the allied tank for each of those behaviors. However we would have to do this for each tank type even though the behavior code might be exactly the same. This leads to an explosion in subclasses.

Hence the use of the strategy pattern, which involves encapsulating the behavior into a separate objects and assign different behavior objects to tank objects at runtime. The previous post on Go vs Java touches upon this with the discussion of steering behaviors. Essentially steering behaviors could be thought of as the same as behaviors for sprites. The Go vs Java example shows how a language like Go with first class functions simplifies greatly the creation of strategy objects, in much the same way as we demonstrated in the Command pattern section above.

In Java and C++ we would have needed to create subclasses such as Agressive, Sneaky and Cautious of an interface, say Behavior. Go gets away with defining closures.

We could even apply the strategy pattern to how sprites are drawn:
type Sprite struct {
 pos Point
 draw func(pos Point)
}

func (sprite *Sprite) Draw() {
 sprite.draw(sprite.pos)
}

Factory Pattern

In the Design Patterns book by the Gang of Four, different construction patterns are demonstrated using the example of a maze. The idea is that a maze consists of a number of connected rooms of different types. The reason for using some kind of factory is that we might want to change the types of rooms used but we don't want to have to change the code that creates the maze by instantiating room objects and connecting them. Here is an example of what the maze construction code might look like in C++:


void BuildMaze(RoomFactory* factory) {
 Room* a = factory->CreateRoom("Prison");
 Room* b = factory->CreateRoom("GuardRoom");
 Connect(a, b); 
}

In Go we don't need to use an instance of a class at all. It is more convenient to simply use a function object:


func BuildMaze(createRoom func(roomType string) Room) {
 a := createRoom("Prison");
 b := createRoom("GuardRoom");
 Connect(a, b); 
}

But in practice it goes beyond this. Those familiar with more dynamic OOP languages like Smalltalk and Objective-C know that classes are objects and can thus be passed around in the code. In languages like C++ and Java we usually simulate this by creating a factory class for each class we want to be able to pass around as if the class was an object.

In Go we can achieve much the same without extra code. The idiomatic way of creating an instance of a struct is to call a free function. This is because Go does not support constructors. So instead of coding constructors to instantiate structs you code free functions. The beneficial side effect of this is that because functions are first class objects, these creation functions can be passed around in similar fashion as Objective-C class objects. Constructors are not regular functions and can thus not be passed around in this fashion. Thus separate factory functions or classes needs to be created in languages like Java and C++.

Conclusion

While writing this blog entry, I tried to compare Go with Python. It became apparent that while Go can achieve a lot of the same simplicity as Python, it still can't do all patterns as simple as in Python. The most problematic pattern I noticed was subject-observer. In Joe Gregorio's presentation on the lack of design patterns in Python, it is written as this:

class Point(object): 
    def __init__(self, x, y): 
        self.x = x 
        self.y = y 

    def scale(self, n): 
        self.x = n * self.x 
        self.y = n * self.y 
def notify(f): 
    def g(self, n): 
        print n 
        return f(self, n) 
    return g 
Point.scale = notify(Point.scale) 

p = Point(2.0, 3.0) 

p.scale(2.5) 

Which can't be easily reproduced in Go. However the other patterns mentioned by Joe Gregorio: Iterator, Factory and Strategy should be just as easy as I hope I demonstrated clearly here. Another aspect which I haven't seen anybody write about in detail is lack of refactoring in Python and Ruby code bases. I am not saying it doesn't happen but I notice a couple developers who develop in both C++, Java and Ruby point out that they almost never refactor their Ruby code, while it is frequent occurrence in Java and C++. The reason being given that the need seldom seem to arise. I think it would be interesting to see in the future when more experience is gained from using Go, what the experience will be for Go. Will there be a lot of design patterns and refactoring or will the experiences be more similar to that of Python and Ruby developers?

Wednesday, December 02, 2009

Go vs Java

On the surface Go and Java might seem to have a lot in common. They are both modern C/C++ like languages with garbage collection, supporting object oriented programming.

But beyond that there are quite a lot of differences. I will not highlight so much of Java's strengths compared to Go, as Java has been around for a long time. What is more interesting is why a developer should want to choose Go over Java, given Java's ubiquity, large number of frameworks, tools etc.

First issue is efficiency both with respect to memory usage and performance. Go allows much more low level tuning similar to C. A problem in Java is that all types except primitive types are reference types. That means related data can't be stored in one location. E.g. say we have a Car object with 1 Engine object, 4 Wheel objects etc. All those objects are stored in different locations in memory. While in C or Go you could store all the Car related data as one continuous block of memory. Why is that important? In modern computers CPU's can process data a lot faster than it can be feed to it by regular RAM memory. Due to this frequently used parts of the main RAM memory are stored in a super fast memory called cache. For caches to be efficient related data needs to be close in address space. That is hard to achieve in Java.

An example of this in practice is the distributed version control system git. It is known to be very fast. It is written in C. A Java version JGit was made. It was considerably slower. Handling of memory and lack of unsigned types was some of the important reasons.

Shawn O. Pearce wrote on the git mailinglist:
JGit struggles with not having an efficient way to represent a SHA-1. C can just say "unsigned char[20]" and have it inline into the container's memory allocation. A byte[20] in Java will cost an *additional* 16 bytes of memory, and be slower to access because the bytes themselves are in a different area of memory from the container object. We try to work around it by converting from a byte[20] to 5 ints, but that costs us machine instructions

Like C, Go does allow unsigned types and defining data structures containing other data structures as continuos blocks of memory

Method calls

Before reading this it might be good to read Scott Stanchfield's article on why all java method calls use pass-by-value, and that there is no such thing as pass-by-reference in Java. However as mentioned Java does not support value types for other than primitive types. This causes problems for method calls. One problem is that small objects like a Point might often be faster to copy in a method call, rather than copy their reference which is what Java does. More importantly perhaps is that value semantics is often easier understood. E.g. it would be natural to assume that Point would be a value type. If I pass a Point object to a function I don't expect my point to be modified by called function. And yet that can easily happen in Java.

Too strong focus on OOP

Since the decision was made that Java would have no free functions (even though static methods in a way is free functions) this has caused the Java designer to come up with very cumbersome syntax to deal with problem that would have been best handled with free functions. Instead of closures Java got nested classes:

 myButton.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            frame.toFront();
        }
    });
The same thing is achieved a lot less verbosely in Go using closures:
 myButton.addActionListener(func(e ActionEvent) {
  frame.toFront();
 });

Actually the Java version requires even more code, because the ActionListener class needs to be defined somewhere. The function object passed in the Go example is defined right were it is used.

Why Java code end up being considerably more verbose than Go code

When you start building more complicated things this problem starts adding up, causing excessive amounts of code to be needed in Java, while short readable code can be used in Go for the same thing. Consider this example. For a game engine I was writing I used Lua as a script language. Algorithms for planning movement of Non player characters was based on combining different functions describing different behavior. Without a lot of background information the code below is not easy to follow. But bare with me:

local flank = Geometry.makeFlank(player, 10)
local seek = Geometry.makeSeek(player:position())
local combo = Geometry.combineBehavior({0.001,seek}, {1,flank})

flank, seek and combo are functions created by other functions makeFlank, makeSeek etc. The combo function is created by combining the flank and seek functions. Basically each function takes two arguments referred to as s0 and s1, which denotes a orientation and position in space. Below is the code that creates the seek function:

function Geometry.makeSeek(target)
  -- Goodness of trajectory from state 's0' to 's1'
  function seek(s0, s1)
    local p0 = s0:position()
    local p1 = s1:position()
    local d1 = s1:direction()
    
    -- direction to target
    local dir_target = (target-p1):unit()  
    
    -- direction of from current point to next on path
    local dir_path = (p1-p0):unit()   
    return 0.25*(1 + d1*dir_target)*(1 + dir_path * dir_target)
  end
  return seek
end

The details of the code is not important. It is mainly vector operations used to calculate how desirable s1 is with respect to getting the non player character to the goal position target. The candidate s1 position and orientations are produced elsewhere by considering places in space which does not cause collision with other objects etc. The code below shows how we would do this in Java. Since Java does not have closures we have to use classes:

interface Behavior {
  public float goodness(State s0, State s1);
  public void  add(Behavior b, float weight);  
}

class Seek implements Behavior {
  Vec2 target;
  
  public Seek(Vec2 target) {
    this.target = target;
  }
  
  public float goodness(State s0, State s1) {
    Vec2 p0 = s0.position();
    Vec2 p1 = s1.position();
    Vec2 d1 = s1.direction();
        
    // direction to target   
    Vec2 dir_target = (target.minus(p1)).unit();

    // direction of from current point to next on path
    Vec2 dir_path = (p1.minus(p0)).unit();
    return 0.25*(1.0 + d1.dot(dir_target))*(1.0 + dir_path.dot(dir_target));    
  }  
}

The different behaviors will then be combined as follows:

Behavior flank = new Flank(player, 10);
Behavior seek  = new Seek(target);
Behavior combo = new Combo();
combo.add(flank, 1.0);
combo.add(seek, 0.001);

With Go we can write the code more like we did in the dynamic script language Lua.

func makeSeek(target Vec2) func(s0, s1 State) float {
  func seek(s0, s1 State) float {
   p0 := s0.position();
   p1 := s1.position(); 
   d1 := s1.direction(); 

   // direction to target   
   dir_target := (target.minus(p1)).unit();

   // direction of from current point to next on path
   dir_path := (p1.minus(p0)).unit();
   return 0.25*(1.0 + d1.dot(dir_target))*(1.0 + dir_path.dot(dir_target));    
  }
  return seek; 
}

The the different behavior can be combined in much the same way as it was combined in Lua. The last statement can be done in many ways. The code below is valid since Go supports functions with arbitrary number of arguments, but it can't be properly type checked at compile time.

flank := makeFlank(player, 10);
seek  := makeSeek(target);
combo := makeCombo(flank, 1.0, seek, 0.001);

For stronger type checking one might want to do something like the code below, which requires defining a struct Elem with a function pointer and float member.

combo := makeCombo(List{Elem{flank, 1.0}, Elem{seek, 0.001}});

Doing something similar to the Java way is also possible:

var funcs FuncList;
funcs.Add(flank, 1.0);
funcs.Add(seek, 0.001);
combo := makeCombo(&funcs);

What should be apparent is how much boilerplate code one has to write when making Java programs:

  1. Every method needs public in front
  2. Type has to be repeated for every argument in method definition.
  3. An interface has to be defined every time we want to simulare combining two functions.
  4. The type of a variable has to be specified every time even though the compiler should be able to figure it out based on assignment

The lua code goes on to create new functions:

local eval = Geometry.makeEval(combo, 0.5, 0)
local larger = makeBinary(eval, greaterThan)

Since eval and larger have different function signatures, we would need to create two new interfaces in Java and two class implementing them. Each class will have two methods and some member variables. In contrast the Go solution would only require a total of 4 new functions. No classes or interfaces needs to be created.

Conclusion

As stated earlier the aim of this article was to make the case for Go over Java, so you have to excuse my bias. Java has improved a lot over the years. It used to be extremely verbose for simple things like reading and writing to console. Java 5 improved upon that a great deal. But as these examples show, Java still requires a lot of boilerplate code that doesn't add anything to readability and ability to abstract or reason about the problem you are trying to solve.

I have not touched upon other clear Go advantages like compile time, channels for easing concurrency programming etc. I wanted to show that even without Go's most touted features here is a lot to gain. As new versions of Java comes out new features are added which addresses deficiencies in the language. However the problem is that gradually Java loses some of its original appeal which was that it was a very simple language. Go starts with a small feature set than present Java, perhaps more comparable to the original Java. However the features are better selected so similar kind of expressive power as todays Java can be expressed with far fewer features. I think that is worth somthing

Sunday, November 22, 2009

How does Go fit in with the C-family of languages

The C-family of languages is a pretty large group. It could be discussed which language is fit and which don't but I think it's worthwhile including the languages: C, C++, Objective-C, Java, D, C#.

First we got C++ which is trying to extend C into an object oriented language by taking inspiration from Simula. And then came Objective-C which took a more dynamic approach to object oriented programming and tried essentially to embed smalltalk in to C.

Years later we got Java which try to retain the simplicity of Objective-C compare to C++ but give it a more C++ looking syntax. C# tried to create better Java by using the basic ideas of Java but allow more the power of C++.

And right in the middle there comes D and tries to be what C++ should have been, or rather could have been if we could throw the nasty bits out.

A lot has been centered around C++, and I feel Go is about going back to the roots. Go feels a lot more like C:

  • Fairly simple and clean language. Compared to C++ with its huge feature list
  • No inheritance
  • No classes
  • No constructors and destructors. No RAII
  • You just allocate structs. No code is run like on C++. Like C you have to create separate initialization functions
  • The standard library is very similar to the C standard library. The way you deal with IO, strings etc, feel much more like C than C++
  • In C++ structs are not just simple structs. They can contain invisible fields you didn't explicitly put there like a vtable. In Go structs are just like C structs. There is no vtable

Unlike Java and C# there is no virtual machine. However like those and unlike C++ if a crash happens you are not left in the cold. You get a stack backtrace on the console. In this respect Go is more in the C++ and D camp than in the Java and C# camp. While Java, C# and D have been about trying to keep the basic ideas from C++ and fix them, Go seems to be more about getting duck typing like found in languages like Python, Ruby into the C-family. Or perhaps one could say the designer skipped the whole class and inheritance thing and looked at all the great stuff done with C++ templates which essentially gives compile time duck typing and decided that was a model on to witch Go's dynamic dispatch should be built on

Benefits of Go's interface type

Go doesn't use inheritance but achieve much the same through interfaces. However interfaces have some benefits over the traditional approach I'd like to highlight. Below I am showing two code examples illustrating a struct or class B with a corresponding interface name A.
 struct A {
   virtual int alfa(int a) = 0;
   virtual int beta(int b) = 0;  
 };

 struct B : public A {
   int alfa(int a);  
   int beta(int b);  
   int d;
 };

 int B::alfa(int a) {
  return d + a;
 }

 int B::beta(int b) {
  return d + b + 3;
 }
Below is the Go version of the code above:
 type A interface {
  alfa(a int) int;
  beta(b int) int;
 }

 type B struct {
  d int;
 }

 func (m B) alfa(a int) int {
  return m.d + a;
 }

 func (m B) beta(b int) int {
  return m.d + b + 3;
 }
In C++ we can call the methods defined on the struct B through its interface A like this:
 int x, y;
 B b;
 b.d = 3;
 A *a = &b;

 x = a->alfa(1);
 y = a->beta(2);
Likewise in Go:
 var x, y int;
 b := B{3};
 var a A = b;
 x = a.alfa(1);
 y = a.beta(2);
On the surface this looks very similar but there are some notable differences. In C++ the inheritance hierarchy can be arbitrarily deep and so dynamic dispatch is dependent on traversing a vtable on a class to its superclass on so on until the correct implementation is found. In Go there is no inheritance tree, so each method will be accessed as if a single function pointer. In this way Go is more similar to how you typically create some kind of polymorphism in C. In C it is common to define structs with lists of function pointers, which are changed depending on type etc. The other difference is that if you change the code on Go to this:
 var x, y int;
 b := B{3};
 x = b.alfa(1);
 y = b.beta(2);
Then the calls are resolved statically. There is no function pointer lookup, simply because there are no virtual functions in Go. If you call a method on a struct in Go, the compiler knows exactly what method you are calling. However if you change the code in C++ likewise, you are still making a virtual method call. To be fair in some cases the compiler can figure out the right method call. But the bp pointer could have been passed around and you can't know if it points to a subclass of B or not. With Go, this problem doesn't exist since structs don't have subclasses, making the job much easier for the compiler.
 int x, y;
 B b;
 b.d = 3;
 B *bp = &b;

 x = bp->alfa(1);
 y = bp->beta(2);

Better consistency in type system

Having methods on structs be statically resolved also makes it trivial to support methods on basic types like ints and floats. Something which isn't possible in C++ or Java. The reason that isn't possible is because ints and floats don't have vtables. While in Go you don't need a vtable to have methods, so it is not a problem. In my view this blurs the distinction between basic types like ints and objects which are e.g. in Java two clearly different things. That is a good thing since it creates better consistency. There are less special cases.

How to deal with missing features in Go

A lot of people will probably complain about all those C++ not found in Go. E.g. without constructors and destructors how does one handle resources safely through RAII? Go doesn't really need RAII because it has closures. That is used extensively in e.g. Ruby to get the same benefits. E.g. here is some code I wrote that opens a file, reads one line at a time and closes the file.
 ReadLines("struct-template.h", func(line string) {
  fmt.Printf(doStuffWithLine(line));
 })
The ReadLines function was implemented like this:
 func ReadLines(file_name string, fn func(line string)) {
  file, err := os.Open(file_name, os.O_RDONLY, 0);
  defer file.Close();
     if file == nil {
      fmt.Printf("can't open file; err=%s\n",  err.String());
      os.Exit(1);
     }

  in := bufio.NewReader(file);
  for s, err := in.ReadString('\n'); err != os.EOF; s, err = in.ReadString('\n') {
   fn(s)
  }  
 }
Which shows another way to deal with RAII. One can use defer which will call method after defer when function goes out of scope. Exceptions are not present in Go either but you can mimic the kind of error handling you do with exceptions by using multiple return values were one signals error and use the named return value feature.
 func ProcessFile(file_name string) (err os.Error) {
  file, err := os.Open(file_name, os.O_RDONLY, 0);
  // ...
  return;
 }
In the simple example above err will automatically be bound to the return value. So if the function didn't handle the error returned in err it will be automatically propagated to the calling function.

First impressions from the Go programming language

I spent the last week or so learning the new programming language release from Google called Go. The first program I written this a simple text processing tool. That is the kind of tools I've previously written in Python and Ruby. I would say that Python is still better suited for this kind of job. However that is mainly due to less functional regular expressions and string libraries found in Go. Although it is unavoidable that when using a statically typed language there is a bit more overhead. In particular with respect to typing.

Compared to regular statically typed languages

However for a statically typed language I can't find anything that can compare. I could write code in a manner to remind me a lot of how it feels to write code and script language. Other languages which I'm familiar with like C++, Objective-C, Java are much more verbose and clunky to use. Those are languages which encourage much more planning and feels better suited for larger applications.

C is a simple language but it lack so much features that it becomes cumbersome to do string processing. No string class and a bit too code spent managing memory.

Compared to Haskell and C#

Of course there are other statically typed languages like Haskell and C#. Now Haskell is probably a more innovative and elegant language then Go. But it is also the language requires much more understanding before it can be used productively. Most developers are not intimate with the functional languages. Especially pure functional languages like Haskell. With Go on the other hand I could use the skills I had developed while using languages like Python, C++ and C. That meant I could be productive quite quickly. With a sharp unafraid to comment because so much has happened without language to last year's and I haven't used in years. I know at least that the C# that I used to use could not compete with Go in ease-of-use.

Compared to Scheme

I have written text processing utility and scheme previously. The whole development process is nicer than most other languages I think. Mainly because of the interactive style development that scheme allows. I could quickly and easily test segments of my code in the interactive shell because everything in scheme is an expression. In this respect go is as cumbersome as any other traditional language. You run test your program one file at a time.

Of course came that same problem as Haskell. You can easily reuse programming skills developed while using C and C++ for many years. It's cumbersome to get used to reading scheme code that takes time to get used to what functions are called and how to print special characters like newline etc.

Advantages of C over C++

It has been claimed that C++ is a better C them C. this is being taken to mean that when switching to C++ you can continue to code more or less as she did in C and use a little extra C++ functionality for convenience. The problem with that is that a lot of things which are perfectly safe to do and see are not safe to do while using C++. So here is my list of issues not found in C. You can avoid many of these issues in C++ by limiting what features you use. But you never have any guarantees. You can't pick up random C++ code, look at it and be certain whether it is doing something safe or not when e.g. statically initializing a variable.
  • Static initialize is safe in C but not in C++, because in C++ static initialization can cause code to run, which depends on other variables having been statically initialized. It can also cause cleanup code to run at shutdown which you can't control sequence of (destructors).
  • C gives you better control over what happens when your code is executed. When reading seek out it is fairly straightforward to decipher one code is getting executed and when memory is just restart or primitive operations are performed. In C++ on the other hand your have to deal with several potential problems:
    • A simple variable definition can cause code to run (constructors and instructors)
    • Implicitly generated and called functions. If you didn't define constructors, destructors and operator= you will get them generated for you.
    See hidden cost of C++ or Defective C++
  • C supports variable sized arrays on the stack. Which is much faster to allocate than on the heap. (C99 feature)
  • No name mangling. If you intend to read generated assembly code, this makes that much easier. It can be useful when trying to optimize code.
  • De facto standard application binary interface (ABI). Code produced by different compilers can easily be combined.
  • Much easier to interface with other languages. A lot of languages will let you call C functions directly. Binding to a C++ library is usually a much more elaborate job.
  • Compiling C programs is faster than compiling C++ programs, because parsing C is much easier than parsing C++.
  • Varargs cannot safely be used in C++. They're not entirely safe in in C either. However they're much more so in the C++, to the point that they are prohibited in the C++ coding standards (Sutter, Alexandrescu).
  • C requires less runtime support. Makes it more suitable for low-level environments such as embedded systems or OS components.
  • Standard way in C to do encapsulation is to forward declare a struct and only allow access to its data through functions. This method also creates compile time encapsulation. Compile time encapsulation allows us to change the data structures members without recompilation of client code (other code using our interface). The standard way of doing encapsulation C++ on the other hand (using classes) requires recompilation of client code when adding or removing private member variables.
Disliking C++ is not a fringe thing. It does not mean that one is not capable of understanding complex languages. Quite a lot of respect computer science people and language designers aren't fond of C++. See C++ coders

Thursday, September 10, 2009

Grand Central Dispatch versus Qt Concurrent

Lately we have been provided with several different solutions to how we can utilize multicore CPUs. Previously we had few other options besides creating multithreaded applications explicitly. By explicitly I mean the developer had to create and manage threats manually.

Both Grand Central dispatch and Qt Concurrent is based on the idea that the developer submits chunks of work to a library which will distribute the chunks of work onto several different threads which can be running on several different cores.

Below is a code example showing Qt's approach to distributing chunks of work to different threads. To use the right terminology each chunk of work is called a task. The code below shows how a strain is split by running the splitting method in a separate thread.

// call 'QStringList QString::split(const QString &sep,
//                                  SplitBehavior behavior,
//                                  Qt::CaseSensitivity cs) const'
// in a separate thread
QString str = "comma, separated, text";
QFuture<QStringList> future = QtConcurrent::run(str,
                                               &QString::split,
                                               QString(", "),
                                               QString::KeepEmptyParts,
                                               Qt::CaseSensitive);
// Do some more processing
cout << "str may or may not have been split at this point" << endl;
QStringList result = future.result();

// Output split elements on new lines
foreach (QString s, result)
  cout << s << endl;

Future objects

Run, is an asynchronous call. It will hand over its task to a separate thread, return and continue execution of the main thread. Qt uses the concept of a future object to store results from asynchronous method calls. The QFuture object won't actually contain the results of this split method until it's queried for the results. It's a separate thread has finished processing one the future objects is queried it simply returns the results. If it hasn't, the main thread will be blocked until separate thread finishes.

The next piece of code shows Grand Central's approach to the same problem. Instead of using future objects, to synchronize between different threads, Grand Central uses so called dispatch queues. the developer submits tasks to different queues, then Grand Central will dequeue the tasks and place them on to different threads. Tasks in different queues always run concurrently with respect to each other. However task within the same queue might or might not run concurrently with each other, depending on the type of queue. There are two types of cues: serial cues and concurrent queues. In a serial queue a task is not performed until the previously enqueued task has been performed. In the code below we create a serial queue.

// Creates a serial queue for tasks, where the next
// task is performed when the previous  is finished
dispatch_queue_t my_queue;
my_queue = dispatch_queue_create("my queue", NULL);

QString str = "comma, separated, text";
__block QStringList result;
dispatch_async(my_queue, ^{
  result = str.split(", ", QString::KeepEmptyParts, Qt::CaseSensitive);
});
  

// Do some more processing
cout << "str may or may not have been split at this point" << endl;

dispatch_sync(my_queue, ^{
  // Output split elements on new lines
  foreach (QString s, result)
    cout << s << endl;
});

Code blocks

In Grand Central dispatch a task is represented by a code block. Code blocks is an extension by Apple to the C-language and C++. In languages like Ruby and Python code blocks are referred to as closures. Essentially they let you define a function within another function. This function has access to all variables defined outside its scope and any variable referred to in the code block will continue to live even after the outer scope no longer exists. But only as read-only variables. If you want to write to a variable outside the scope of the block, then you have to prefix variable with __block.

Asynchronous dispatch

dispatch_async() is similar to the run method in Qt. The provided code block is passed on to a separate thread amber function call returns immediately to the main thread. The code splitting the string will run in parallel to all the code it follows after the asynchronous dispatch. But since we don't have a future object, how can we safely read the results variable in the main thread? Normally one would have solved for these kind of thread issues with semaphores.

Synchronous dispatch

There are two ways to read the result variable safely. One can dispatch a task either asynchronous or synchronous to the same queue, which reads the result variable. Since the queue we have created is a serial queue, the reading task would not be executed until all previously and queued tasks have been finished. In this case we have chosen to call dispatch_sync(). It will block the main thread until a submitted task has been executed. Thus, in this case we know that after the dispatch_sync() call the only running thread is the main thread.

Conclusions

The metaphor used by queue might seem simpler to understand and deal with, but it trades and simplicity for flexibility. The biggest problem is that there is no obvious way to control access to shared resources without using semaphores. With Grand Central's approach one can take code that used to be in a critical section, plays in a code block and do a dispatch to a queue. Instead of protecting the access in to share resource with the same semaphore, one can protect the access by submitting tasks to the same serial queue. This will make sure that all code that accesses a share resource does so in strict sequence. This is a clear benefit over using semaphores, because with semaphores one does not know in which sequence the threads access a shared resource.